对《大话数据结构》P417~P427—快速排序，进行了自己的理解并完善了代码。
一、快排普通版
基本思想：通过一趟排序，将待排记录分割成以枢轴为分界的独立的两部分，一部分的数都比枢轴小，另一部分的数都比枢轴大。这句话也体现了枢轴的作用。再通过递归，对每部分继续排序。
void QSort(SqList *L,int low,int high)//对顺序表L中的子序列L->r[low..high]作快速排序，包括三部分：
1、int Partition(SqList *L,int low,int high)//找到枢轴，并且让枢轴左边的数都小于枢轴，枢轴右边的数都大于枢轴，返回枢轴值的位置
2、QSort(L,low,pivot-1);//递归，对低子表排序
3、QSort(L,pivot+1,high);//递归，对高子表排序
代码和解释如下（VS2012测试通过）：
1 #include <iostream> 2 using namespace std; 3 #define MAXSIZE 9//用于要排序数组个数最大值，可根据需要修改 4 5 //排序用的顺序表结构 6 typedef struct 7 { 8 int r[MAXSIZE+1];//定义一个数组，用于存储要排序的数，r[0]作为临时变量 9 int length;//用于记录顺序表的长度 10 }SqList; 11 12 //排序表的初始化 13 SqList *InitSqList(SqList *L) 14 { 15 L=new SqList; 16 L->length=MAXSIZE; 17 cout<<"input list"<<endl; 18 for(int i=1;i<=L->length;i++) 19 cin>>L->r[i]; 20 return L; 21 } 22 23 //数组遍历输出 24 void PrintSqList(SqList *L) 25 { 26 for(int i=1;i<=L->length;i++) 27 cout<<L->r[i]<<" "; 28 cout<<endl; 29 } 30 31 //交换r[i]和r[j] 32 void swap(SqList *L,int i,int j) 33 { 34 int temp=L->r[i]; 35 L->r[i]=L->r[j]; 36 L->r[j]=temp; 37 } 38 39 //找到枢轴，并且让枢轴左边的数都小于枢轴，枢轴右边的数都大于枢轴，返回枢轴值的位置 40 int Partition(SqList *L,int low,int high) 41 { 42 int pivotkey; 43 pivotkey=L->r[low];//用子表的第一个记录作枢轴值 44 while(low<high)//从表的两端交替地向中间扫描 45 { 46 while(low<high&&L->r[high]>=pivotkey) 47 high--; 48 swap(L,low,high);//将比枢轴值小的数交换到低端 49 //能执行到这一步，说明high位置的值小于枢轴，而low是大于等于枢轴的值，交换之后正好low位置的值小于枢轴，high位置的值大于等于枢轴 50 while(low<high&&L->r[low]<=pivotkey) 51 low++; 52 swap(L,low,high);//将比枢轴值大的数交换到高端 53 //能执行到这一步，说明low位置的值大于枢轴，而high位置的值大于等于枢轴，交换，感觉这一步算法效率不高，50一直在变位置，不知道快排优化版会不会优化这一步 54 } 55 return low;//返回枢轴所在位置 56 } 57 58 //对顺序表L中的子序列L->r[low..high]作快速排序 59 void QSort(SqList *L,int low,int high) 60 { 61 int pivot;//枢轴，左边的值都比它小，右边的值都比它大 62 if(low<high) 63 { 64 pivot=Partition(L,low,high);//将L->r[low..high]一分为二，使枢轴左右分别有序，并小于和大于枢轴值，并返回枢轴值pivot 65 PrintSqList(L);cout<<"pivot="<<pivot<<endl; 66 QSort(L,low,pivot-1);//递归，对低子表排序 67 QSort(L,pivot+1,high);//递归，对高子表排序 68 } 69 } 70 71 //对顺序表L作快速排序 72 void QuickSort(SqList *L) 73 { 74 QSort(L,1,L->length); 75 } 76 77 int main() 78 { 79 SqList *p=NULL; 80 p=InitSqList(p);//初始化 81 QuickSort(p);//排序 82 cout<<"after sort"<<endl; 83 PrintSqList(p);//输出 84 }
运行结果：
1、以50为枢轴，50左边都小于50,50右边都大于50。
2、对50左边序列递归。
50左边序列10 20 40 30，再一分为二。
10 20归位。
30 40归位。
3、对50右边序列递归。
50右边序列70 80 60 90，再一分为二。
60 70归位。
80 90归位。
时间复杂度：
二、快排优化版
有4个地方可以优化（代码中有注明）：
1、优化第一次选取的枢轴
pivotkey=L->r[low];存在潜在的性能瓶颈。r[1]如果是最大或者最小数，就彻底变成斜树了。比如上一个例子，50是中间数，递归数是平衡的（有点完全二叉树的意思，但不是完全二叉树）。如果排序n个数，递归树的深度就是log2n(向下取整)+1。所以r[1]在整个序列的位置很重要，r[1]不能太大或者太小。书上介绍了三数取中。在左端，中间，右端，三个数中间选中间数，作为第一个枢轴。保证递归树相对平衡，不要变成斜树。
2、优化不必要的交换
这是最难理解的一步优化，把交换改成替换。我在看普通版的快排时候也考虑到这个问题，还在代码中注释了这个疑问，但是当时不知道怎么优化。
high指到小于枢轴的数时，把high位置的数赋值给当前low位置的数。
low指到大于枢轴的数时，把low位置的数赋值给当前high位置的数。
为什么赋值给当前的数，它原来的数不会丢，对第一步，它的数在哨兵。第二步开始，被替换的数，是上一步已经替换给其它位置的数，所以永远不会丢失掉数。
3、快排用到了递归操作，在大量数据排序时，性能好。但如果数组只有几个数，还不如用直接插入排序（简单排序中性能最好）。增加判断，当high-low不大于7，就用直接插入排序。
4、优化递归
递归对性能有一定影响。QSort函数在尾部有两次递归操作。如果待排序的序列划分不平衡，递归深度接近于n（斜树），而不是平衡时的log2n(向下取整)。
代码和解释如下（VS2012测试通过）：
1 #include <iostream> 2 using namespace std; 3 #define MAXSIZE 9//用于要排序数组个数最大值，可根据需要修改 4 #define MAX_LENGTH_INSERT_SORT 7//用于快速排序时判断是否选用插入排序阙值 5 6 //排序用的顺序表结构 7 typedef struct 8 { 9 int r[MAXSIZE+1];//定义一个数组，用于存储要排序的数，r[0]作为临时变量 10 int length;//用于记录顺序表的长度 11 }SqList; 12 13 //排序表的初始化 14 SqList *InitSqList(SqList *L) 15 { 16 L=new SqList; 17 L->length=MAXSIZE; 18 cout<<"input list"<<endl; 19 for(int i=1;i<=L->length;i++) 20 cin>>L->r[i]; 21 return L; 22 } 23 24 //数组遍历输出 25 void PrintSqList(SqList *L) 26 { 27 for(int i=1;i<=L->length;i++) 28 cout<<L->r[i]<<" "; 29 cout<<endl; 30 } 31 32 //交换r[i]和r[j] 33 void swap(SqList *L,int i,int j) 34 { 35 int temp=L->r[i]; 36 L->r[i]=L->r[j]; 37 L->r[j]=temp; 38 } 39 40 //直接插入排序 41 void InsertSort(SqList *L) 42 { 43 for(int i=2;i<=L->length;i++) 44 { 45 if(L->r[i]<L->r[i-1])//如果r[i]比排在它前面的数小 46 { 47 int j; 48 L->r[0]=L->r[i];//把r[i]移动到哨兵位置 49 for(j=i-1;L->r[j]>L->r[0];j--)//从r[i-1]开始，与哨兵比较，如果比它大 50 L->r[j+1]=L->r[j];//把该元素依次右移一位，直至r[j]比哨兵小，结束循环 51 //因为有j--，结束循环后，r[j]是比r[0]小的 52 L->r[j+1]=L->r[0];//所以把哨兵插入到r[j+1] 53 cout<<"after one sort"<<endl; 54 PrintSqList(L); 55 } 56 } 57 } 58 59 //找到枢轴，并且让枢轴左边的数都小于枢轴，枢轴右边的数都大于枢轴，返回枢轴值的位置 60 int Partition1(SqList *L,int low,int high) 61 { 62 int pivotkey; 63 //优化1，三数取中，3个if之后，左端是中间值 64 int m = low + (high - low) / 2; //计算数组中间的元素的下标 65 if (L->r[low]>L->r[high]) 66 swap(L,low,high);//交换左端与右端数据，保证左端较小 67 if (L->r[m]>L->r[high]) 68 swap(L,high,m);//交换中间与右端数据，保证中间较小 69 if (L->r[m]>L->r[low]) 70 swap(L,m,low);//交换中间与左端数据，保证左端较大，即左端是中间值 71 72 pivotkey=L->r[low];//用左中右，三个数中的中间值作枢轴记录 73 //优化2，优化不必要的交换，把交换改为替换，这一步挺神奇的 74 L->r[0]=pivotkey;//将枢轴关键字备份到L->r[0] 75 while(low<high) //从表的两端交替地向中间扫描 76 { 77 while(low<high&&L->r[high]>=pivotkey) 78 high--; 79 L->r[low]=L->r[high]; 80 while(low<high&&L->r[low]<=pivotkey) 81 low++; 82 L->r[high]=L->r[low]; 83 } 84 L->r[low]=L->r[0]; 85 return low;//返回枢轴所在位置 86 } 87 88 //优化后的快排 89 void QSort1(SqList *L,int low,int high) 90 { 91 int pivot; 92 if((high-low)>MAX_LENGTH_INSERT_SORT)//优化3，当high-low不大于7时，用直接插入排序 93 { 94 while(low<high) 95 { 96 pivot=Partition1(L,low,high);//将L->r[low..high]一分为二，使枢轴左右分别有序，并小于和大于枢轴值，并返回枢轴值pivot 97 QSort1(L,low,pivot-1);//递归，对低子表排序 98 low=pivot+1;//优化4，优化递归操作， 99 //第一次递归后，变量low就没有用处了，将pivot+1赋值给low，下次循环的Partition1(L,low,high)等价于QSort1(L,pivot+1,high) 100 //因采用迭代而不是递归，可以缩小堆栈深度，提高整理性能 101 } 102 } 103 else 104 InsertSort(L); 105 } 106 107 //对顺序表L作优化后的快速排序 108 void QuickSort1(SqList *L) 109 { 110 QSort1(L,1,L->length); 111 } 112 113 int main() 114 { 115 SqList *p=NULL; 116 p=InitSqList(p);//初始化 117 QuickSort1(p);//排序 118 cout<<"after sort"<<endl; 119 PrintSqList(p);//输出 120 }
运行结果：
原文：http://www.cnblogs.com/hslzju/p/5432686.html