希尔排序相当于直接插入排序的升级，它们同属于插入排序类；堆排序相当于简单选择排序的升级，它们同属于选族排序类；而快速排序其实就是我们前面认为最慢的冒泡排序的升级，它们同属于交换排序类；即它是通过不断比较和移动交换来实现排序的，只不过它的实现，增大了记录的比较和移动的距离，将关键字较大的记录从前面直接移动到后面，关键字较小的记录从后面直接移动到前面，从而减少了总的比较次数和移动次数。
快速排序算法的思想
快速排序（Quick Sort）的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。
比如我们要排序{50,10,90,30,70,40,80,60,20}。首先就是选取当中一个关键字，比如选择第一个关键字50，然后想尽办法将它放置到一个位置，使得它左边的值都比它小，右边的值都比它大，我们将这样的关键字称为枢轴（pivot）。这样我们得到两位位于50左和右小数组{20,10,40,30}和{70,80,60,90}。然后继续递归分割进行同样的操作，知道顺序全部正确为止。
然后从数组的两端low、high交替开始扫描，比如从右边到左边开始比较,枢轴为50,小于枢轴则发送交换：
然后从左边到右边，大于50则发生交换：
继续从右边到左边，小于50则发生交换：
如此循环：
代码实现
首先得实现枢轴的选择，下面的程序就是经过一次枢轴选择后的结果：
#include <iostream>
using namespace std;
#define MAXSIZE 10 //用于排序数组个数最大值 可根据需要修改
typedef struct{
int r[MAXSIZE]; //数组
int lengh; //数组的实际长度
}SqList;
void swap(SqList *L,int i,int j){ //对数组的交换操作
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
void print(SqList *L){
for(int i=0;i<L->lengh;i++){
cout<<L->r[i]<<" ";
}
cout<<endl;
}
void getPivot(SqList *L,int low,int high){
int pivot=L->r[low]; //把low到high序列中的第一个元素设置为枢轴
while(low<high){
while(pivot<L->r[high]&&low<high)
high--;
L->r[low]=L->r[high]; //交换数值
L->r[high]=pivot;
while(pivot>L->r[low]&&low<high)
low++;
L->r[high]=L->r[low]; //交换数值
L->r[low]=pivot;
}
}
int main(){
SqList *L=(SqList*)malloc(sizeof(SqList));
L->lengh=9;
L->r[0]=50;
L->r[1]=10;
L->r[2]=90;
L->r[3]=30;
L->r[4]=70;
L->r[5]=40;
L->r[6]=80;
L->r[7]=60;
L->r[8]=20;
print(L);
getPivot(L,0,8);
print(L);
system("pause");
}
得到两位位于50左和右小数组{20,10,40,30}和{70,80,60,90}。然后继续递归分割进行同样的操作，知道顺序全部正确为止。getPivot函数还得修改一下，因为此时high和low的值相等，也就是枢轴的位置，因此要返回枢轴的位置。
#include <iostream>
using namespace std;
#define MAXSIZE 10 //用于排序数组个数最大值 可根据需要修改
typedef struct{
int r[MAXSIZE]; //数组
int lengh; //数组的实际长度
}SqList;
void swap(SqList *L,int i,int j){ //对数组的交换操作
int temp=L->r[i];
L->r[i]=L->r[j];
L->r[j]=temp;
}
void print(SqList *L){
for(int i=0;i<L->lengh;i++){
cout<<L->r[i]<<" ";
}
cout<<endl;
}
int getPivot(SqList *L,int low,int high){
int pivot=L->r[low]; //把low到high序列中的第一个元素设置为枢轴
while(low<high){
while(pivot<L->r[high]&&low<high)
high--;
L->r[low]=L->r[high]; //交换数值
L->r[high]=pivot;
while(pivot>L->r[low]&&low<high)
low++;
L->r[high]=L->r[low]; //交换数值
L->r[low]=pivot;
}
return high;
}
void Quitsort(SqList *L,int low,int high){
if(low<high){
int pivotPos=getPivot(L,low,high);
Quitsort(L,low,pivotPos-1);
Quitsort(L,pivotPos+1,high);
}
}
int main(){
SqList *L=(SqList*)malloc(sizeof(SqList));
L->lengh=9;
L->r[0]=50;
L->r[1]=10;
L->r[2]=90;
L->r[3]=30;
L->r[4]=70;
L->r[5]=40;
L->r[6]=80;
L->r[7]=60;
L->r[8]=20;
print(L);
Quitsort(L,0,8);
print(L);
system("pause");
}