快速排列
(一)、快速排列的基本原理:
关于快速排序，它的基本思想就是选取一个基准，一趟排序确定两个区间，一个区间全部比基准值小，另一个区间全部比基准值大，接着再选取一个基准值进行排序，依次类推，最后得到一个有序的数列.
(二)、运用快速排列的注意事项:
切记在while 循环中，时是右边的先动，然后左边的后动，前后位置可不能整反.
(三)、基本思想和思路:
首先我们要进行函数调用设置：把数组的地址，起始位置、终点位置都要传送给回调函数，然后我们要在回调函数中进行一下操作，判断左边位置是否要小于右边位置，假如说小于进行: while循环，进行i++，j–操作，当就遇到的数字比基准值小的时候就停止，i遇到比基准值大的数值时停止，假如说此时此刻的位置是i<j的，那么就让他俩交换数据.如果时i>j的那么就要i的值和基准值进行交换。退出while循环，然后再重新定义一个基准值进行交换，然后再递归两次函数即可.
(四)、实战项目:
1.升序代码展现:
#include <iostream>
#include <string.h>
using namespace std;
void Qicklysort(int arry[],int left, int right)
{
if (left >= right)return; //假如说左边大于等于右边 退出这个结构体
int l = left;
int r = right;
int base = arry[left];
while (l < r)
{
while (l < r && arry[r] >= base) //从右向左开始移动直到遇到小于base的值为止
{
r--;
}
while (l < r && arry[l] <= base) //从左向右开始移动直到遇到大于base的值为止。
{
l++;
}
if (l < r) //停止后是为了交换位置:
{
int temp;
temp = arry[l];
arry[l] = arry[r];
arry[r] = temp;
}
}
base = arry[left];
arry[left] = arry[l]; //目的是为了让基准数和最左边的数据交换换
arry[l] = base;
Qicklysort(arry, left, l - 1); //判断从0到l的项目 ，不包括l
Qicklysort(arry, l+1, right);
}
int main()
{
int n, a[100];
cout << "请输入你要排序的个数:" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "请输入第" << i + 1 << "个数:" << endl;
cin >> a[i];
}
Qicklysort(a, 0, n - 1);
cout << "排序后为:" << endl;
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
2.升序效果展现:
3.降序代码展现:
#include <iostream>
#include <string.h>
using namespace std;
void Qicklysort(int arry[],int left, int right)
{
if (left >= right)return;
int l = left;
int r = right;
int base = arry[left];
while (l < r)
{
while (l < r && arry[r] <= base) //改变
{
r--;
}
while (l < r && arry[l] >= base) //改变
{
l++;
}
if (l < r)
{
int temp;
temp = arry[l];
arry[l] = arry[r];
arry[r] = temp;
}
}
base = arry[left];
arry[left] = arry[l];
arry[l] = base;
Qicklysort(arry, left, l - 1);
Qicklysort(arry, l+1, right);
}
int main()
{
int n, a[100];
cout << "请输入你要排序的个数:" << endl;
cin >> n;
for (int i = 0; i < n; i++)
{
cout << "请输入第" << i + 1 << "个数:" << endl;
cin >> a[i];
}
Qicklysort(a, 0, n - 1);
cout << "排序后为:" << endl;
for (int i = 0; i < n; i++)
{
cout << a[i] << " ";
}
}
4.降序效果展现:
(五)、if（表达式）return； 介绍
1.简单介绍:
if()return；表示假如表达式为真，那么后面的就不再执行了。为假就继续执行.
2.代码展示:
切记主函数可能为 int 只能为void
#include <iostream>
using namespace std;
void main()
{
int a = 3;
cout << "a1=" << a << endl;
if (a < 4) return;
cout << "a2=" << a << endl;
cout << "a3=" << a << endl;
}
3.效果展示:
(六)、EOF介绍:
1.简单说明:
2.代码展示:
3.效果展示:
（七）、三分取中法
1.什么是三分取中？
为了提高快速排序的时间效率，使用三分取中的方法，可以降低时间复杂度。三分区中的基本概念就是：取第一个值，中间值，最后值。然后取三个值的中位数作为基准，进行运算.
2.三分取中的思想和基本思路？
首先我们要确定我们想要进行排序的数目，然后设置一个回调函数Quickly（），然后进行轴的位置确定，然后将基准值放在最后一位。代入partition()函数，目的是为了进行初步排序，然后再进行基准值的改定，其余思路和普快一样.
3.降序实战项目：
代码展示:
#include<iostream>
using namespace std;
int partition(int* P, int l, int r, int& pivot) {
int temp;
while (l < r) {
while (P[l] >= pivot && l < r) // l右移直到l对应的值小于轴值
l++;
while (P[r] <= pivot && l < r) // r左移直到r对应的值大于于轴值
r--;
temp = P[l]; // 交换l和r对应的值
P[l] = P[r];
P[r] = temp;
}
return l;
}
void Quick_sort(int* P, int i, int j) {
if (j <= i) return; // 判断元素个数为0或1时不进行排序直接返回
int temp;
int pivotindex = (i + j) / 2; // 确定轴值的位置
temp = P[j]; // 将轴值调放在最后
P[j] = P[pivotindex];
P[pivotindex] = temp;
int k = partition(P, i, j, P[j]); // 将右边的第一个位置放在k中
temp = P[k]; // 将轴值放到r和l相遇的位置
P[k] = P[j];
P[j] = temp;
Quick_sort(P, i, k - 1); // 递归调用将序列分段排序
Quick_sort(P, k + 1, j);
}
int main() {
int A[10];
for (int i = 0; i < 5; i++)
cin >> A[i];
Quick_sort(A, 0, 4);
for (int i = 0; i < 5; i++)
cout << A[i] << " ";
system("pause");
}
效果展示：
1.升序实战项目：
代码展示：
#include<iostream>
using namespace std;
int partition(int* P, int l, int r, int& pivot) {
int temp;
while (l < r) {
while (P[l] <= pivot && l < r) // l右移直到l对应的值小于轴值
l++;
while (P[r] >= pivot && l < r) // r左移直到r对应的值大于于轴值
r--;
temp = P[l]; // 交换l和r对应的值
P[l] = P[r];
P[r] = temp;
}
return l;
}
void Quick_sort(int* P, int i, int j) {
if (j <= i) return; // 判断元素个数为0或1时不进行排序直接返回
int temp;
int pivotindex = (i + j) / 2; // 确定轴值的位置
temp = P[j]; // 将轴值调放在最后
P[j] = P[pivotindex];
P[pivotindex] = temp;
int k = partition(P, i, j, P[j]); // 将右边的第一个位置放在k中
temp = P[k]; // 将轴值放到r和l相遇的位置
P[k] = P[j];
P[j] = temp;
Quick_sort(P, i, k - 1); // 递归调用将序列分段排序
Quick_sort(P, k + 1, j);
}
int main() {
int A[10];
for (int i = 0; i < 5; i++)
cin >> A[i];
Quick_sort(A, 0, 4);
for (int i = 0; i < 5; i++)
cout << A[i] << " ";
system("pause");
}
效果展示：
本文含有隐藏内容，请 开通VIP 后查看