快速排序的基本思想：任取待排序序列的一个元素作为中心元素(可以用第一个，最后一个，也可以是中间任何一个)，习惯将其称为pivotkey，即枢轴元素。将所有比枢轴元素小的放在其左边，将所有比它大的放在其右边，形成左右两个子表，然后对左右两个子表再按照前面的算法进行排序(递归)，直到每个子表的元素只剩下一个。
举例说明一下：
arr 为 [39 , 28 , 55 , 87 , 66 , 3 ,17 ,39*]为了区别两个相同元素，将最后一个加上 * 。
初始状态如下图：
定义一枢轴元素pivotkey，初始化为第一个元素的值，即39；
查询左边的元素的变量为left即low，初始值为第一个元素的索引,0;
查询右边的元素的变量为right即hight，初始值为第一个元素的索引,7。
如下图：
演示第一轮排序过程
从右边开始，从右边找到一个比枢轴元素小的，如果没找到right即high一直自减1；
然后把当前left即low所在元素赋值为该值；
这里right即hight所指元素并没有空，只是为了好演示，设置为空（下同）；
然后从左边开始找一个比枢轴元素pivotkey大的元素；如果没找到left一直自增1；
将当前right所指元素设为该值；
然后从右边找到一个比枢轴元素小的，如果没找到right一直自减1；
将当前left所指元素设为该值；
然后从左边开始找一个比枢轴元素pivotkey大的元素；如果没找到left一直自增1；
将当前right所指元素设为该值；
然后从右边找到一个比枢轴元素小的，如果没找到right一直自减1；
这时left和right相遇了，将枢轴元素赋值给当前位置。
第一轮排序动态过程：
然后将数组分成了[17,28,3] 与 [66, 87, 55, 39*]两部分,再对这两部分进行上述环节即可,反反复复,直到只剩下一个元素。
排序全过程
完整代码如下：
#include<bits/stdc++.h> //万能头
using namespace std;
const int Max=100;
//顺序表的定义
typedef struct
{
int key;
}ordNode;
typedef struct
{
ordNode a[Max];
int len;
}Sqlist;
//对顺序表L中的子表r[low..high]进行一趟排序,返回枢轴位置
int Partition(Sqlist &L,int low,int high)
{
L.a[0]=L.a[low]; //用子表的第一个记录做枢轴记录
int pivotkey=L.a[low].key; //枢轴记录关键字记录到pivotkey中
while(low<high)
{
while(low<high&&L.a[high].key>=pivotkey)
high--;
L.a[low]=L.a[high]; //将比枢轴记录小的记录移到低端
while(low<high&&L.a[low].key<=pivotkey)
low++;
L.a[high]=L.a[low]; //将比枢轴记录大的记录移到高端
}
L.a[low]=L.a[0];//枢轴记录到位
return low; //返回枢轴位置
}
//调用前置初值:low=1, high=L.length
void QSort(Sqlist &L,int low,int high)
{
int pivotloc;
if(low<high)
{
pivotloc=Partition(L,low,high);
QSort(L,low,pivotloc-1); //递归调用
QSort(L,pivotloc+1,high);
}
}
//对顺序表L做快速排序
void QuickSort(Sqlist &L)
{
QSort(L,1,L.len);
}
int main(){
Sqlist L;
printf("请输入待排序数的个数:");
scanf("%d",&L.len);
printf("请输入待排序的数:");
for(int i=1;i<=L.len;i++)
scanf("%d",&L.a[i]);
int pivotkey=L.a[1].key;
QSort(L , L.a[1].key , L.a[L.len].key);
QuickSort(L);
printf("请输出排好序的数列:");
for(int i=1;i<=L.len;i++)
printf("%d ",L.a[i]);
return 0;
}
测试用例如下：
请输入待排序数的个数:8
请输入待排序的数:39 28 55 87 66 3 17 39
请输出排好序的数列:3 17 28 39 39 55 66 87稳定性分析：
如下面的数组，相同元素用 * 标出[ 3 , 4 , 2, 2* ]
第一次排序为[2* , 2, 3, 4]
第二次为[2* , 2 , 3 , 4]
相对顺序发生了变化，所以是不稳定的。
图片讲解参考详解快速排序算法 - code随笔 - 博客园
希望可以帮到你哦！^_^