快速排序（quick sort）是冒泡排序改进而来的，基本思想是在待排序的n个元素中，取第一个元素作为基准，将该元素放在适当的位置，将这个数据序列分为两部分，到这里称为一趟排序。此时基准数左边的数都比它小，基准数右边的数都比大。接下来便用同样的方法分别对左右两边的数据进行排序，直到序列中没有元素或只有一个元素。
快速排序每趟仅将一个元素归位。
接下来看一趟划分的代码，原理就是设置两个指示器i和j分别指向序列的第一个和最后一个元素。先是j从右往左扫描，当扫描到比基数小的元素就将该元素赋值到i指向的元素。然后便拍到i从左往右扫，当扫描到比基数大的元素就将该元素赋值给j指向的元素。如此循环直到i和j相遇，便将基数赋值给两个指针同时指向的这个元素。此时便是一趟排序完成。
一趟划分
int partition(int R[], int s, int t)//一趟划分
{
int i = s, j = t;
int tmp = R[i];//以第一个数为基准
while (i<j)//两端交替向中间扫描，直到i=j为止
{
while (j>i&&R[j]>=tmp)//从右向左扫描
{
j--;
}
R[i] = R[j];//右边扫描结束
while (i<j&&R[i]<=tmp)
{
i++;
}
R[j] = R[i];//左边扫描结束
}
R[i] = tmp;
//输出每趟划分后的序列
for (int i = 0; i <= 6; i++)
{
cout << R[i]<<" ";
}
cout << endl;
return i;
}
快读排序其实是一个递归的过程，递归出口为当序列中没有元素或只有一个元素。下面的代码便是递归先对左区间序列进行排序，再对右区间序列进行排序。
递归调用
void QuickSort(int R[], int s, int t)
{
int i;
if (s < t)//区间内至少存在两个元素的情况
{
i = partition(R, s, t);
QuickSort(R, s, i - 1);//对左区间递归排序，二趟排序
QuickSort(R, i + 1, t);//对右区间递归排序，三趟排序
}
}
最后我们可以随便给一个数组进行排序测试
int main()
{
int R[] = { 6,10,10,3,7,1,8 };
QuickSort(R, 0, 6);//后面两个参数为下标
return 0;
}
完整代码如下
#include <iostream>
using namespace std;
int partition(int R[], int s, int t)//一趟划分
{
int i = s, j = t;
int tmp = R[i];//以第一个数为基准
while (i<j)//两端交替向中间扫描，直到i=j为止
{
while (j>i&&R[j]>=tmp)//从右向左扫描
{
j--;
}
R[i] = R[j];//右边扫描结束
while (i<j&&R[i]<=tmp)
{
i++;
}
R[j] = R[i];//左边扫描结束
}
R[i] = tmp;
//输出每趟划分后的序列
for (int i = 0; i <= 6; i++)
{
cout << R[i]<<" ";
}
cout << endl;
return i;
}
void QuickSort(int R[], int s, int t)
{
int i;
if (s < t)//区间内至少存在两个元素的情况
{
i = partition(R, s, t);
QuickSort(R, s, i - 1);//对左区间递归排序，二趟排序
QuickSort(R, i + 1, t);//对右区间递归排序，三趟排序
}
}
int main()
{
int R[] = { 6,10,10,3,7,1,8 };
QuickSort(R, 0, 6);//后面两个参数为下标
return 0;
}
最终输出采用快速排序后4趟排序结果
image.png
网友评论