快速排序算法的思想和几种实现方式
分类：快速排序算法是基于分治策略的另一个排序算法。
该方法的基本思想是：
1．先从数列中取出一个数作为基准数，记为x。
2．分区过程，将不小于x的数全放到它的右边，不大于x的数全放到它的左边。（这样key的位置左边的没有大于key的，右边的没有小于key的，只需对左右区间排序即可）
3．再对左右区间重复第二步，直到各区间只有一个数
快排目前有两类实现算法，第一种是标准算法，第二种是两头交换法。总的思想与上面三步一样，在细节处理上有一些差异。
标准算法思想及实现
标准算算法采用的思想是挖坑填坑的思想：
以一个数组作为示例，取区间第一个数为基准数。
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
72 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
48 |
85 |
初始时，i = 0; j = 9; X = a[i] = 72
由于已经将a[0]中的数保存到X中，可以理解成在数组a[0]上挖了个坑，可以将其它数据填充到这来。
从j开始向前找一个比X小或等于X的数。当j=8，符合条件，将a[8]挖出再填到上一个坑a[0]中。a[0]=a[8]; i++; 这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎么办了？简单，再找数字来填a[8]这个坑。这次从i开始向后找一个大于X的数，当i=3，符合条件，将a[3]挖出再填到上一个坑中a[8]=a[3]; j–;
数组变为：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
48 |
6 |
57 |
88 |
60 |
42 |
83 |
73 |
88 |
85 |
i = 3; j = 7; X=72
再重复上面的步骤，先从后向前找，再从前向后找。
从j开始向前找，当j=5，符合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
从i开始向后找，当i=5时，由于i==j退出。
此时，i = j = 5，而a[5]刚好又是上次挖的坑，因此将X填入a[5]。
数组变为：
|
0 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
48 |
6 |
57 |
42 |
60 |
72 |
83 |
73 |
88 |
85 |
可以看出a[5]前面的数字都小于它，a[5]后面的数字都大于它。因此再对a[0…4]和a[6…9]这二个子区间重复上述步骤就可以了。
对挖坑填数进行总结
1．i =L; j = R; 将基准数挖出形成第一个坑a[i]。
2．j–由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
3．i++由前向后找比它大的数，找到后也挖出此数填到前一个坑a[j]中。
4．再重复执行2，3二步，直到i==j，将基准数填入a[i]中。
代码实现如下：
- #include <iostream>
- using namespace std;
- void quick_sort(int s[],int l, int r){
- int i = l,j = r, x = s[l];
- while(i < j){
- while(i < j && s[j] > x) j–;
- if(i < j)
- s[i++] = s[j];
- while(i < j && s[i] < x) i++;
- if(i < j)
- s[j–] = s[i];
- }
- //此时i==j,下面s[i]或者s[j]都可以，j-1,j+1也ok
- s[j] = x;
- if (l<i) quick_sort(s,l, i – 1);
- if (r>i) quick_sort(s,i + 1, r);
- };
- int main()
- {
- int test[] = {34,5,4,5,3,2,6,90,5};
- quick_sort(test,0,8);
- for(auto c : test){
- cout<<c<<” “;
- }
- cout<<endl;
- return 0;
- }
两头交换法思想及实现
两头交换法与标准算法思想的差异是，先从左边开始找到大于基准值的那个数，再从右边找到小于基准值的那个数，将两个数交换(这样比基准值小的都在左边，比基准值大的都在右边)。直到数列分成大于基准值和小于基准值的两个区间，以这两个区间进行同样的排序操作。
代码实现如下：
- #include <iostream>
- using namespace std;
- void quickSort(int a[],int beg,int end){
- //partition非递归实现，官方版
- if(beg >= end) return;
- int i = beg, j = end, x = a[(i + j)>>1],tmp =0;//这里基准值选了中间的值
- while(i <= j){//取等号，确保分成两个不相交区间
- while( a[i] < x) i++;
- while(a[j] > x) j–;
- if(i <= j ){
- tmp = a[i];
- a[i] = a[j];
- a[j] = tmp;
- i++;
- j–;
- }
- }
- quickSort(a,beg,j);
- quickSort(a,i,end);
- };
- int main()
- {
- int test[] = {34,6,4,5,1,2,6,90,7};
- quickSort(test,0,8);
- for(auto c : test){
- cout<<c<<” “;
- }
- cout<<endl;
- return 0;}
上面的算法是两头交换法官方的版本，边界情况较少，比较健壮。
两头交换法还有另一个实现方式，这种实现方式，基准值只能选区间第一个值或最后一个值。基准值不参与交换，将除基准值之外的所有值按照与基准值的大小关系分成两部分，然后将区间分界点的值填到基准值的坑里，将基准值放在区间分界点。对于基准值左右的区间进行再次排序。
代码实现：
- #include <iostream>
- using namespace std;
- //两点交换法，固定轴点的实现，基准点不参与排序
- //基准点选第一个值，中间交换点选j,
- //基准点选第一个值，中间交换点选i
- //不然，会出现死循环
- //将除第一个值之外的其他值交换使得小于基准值的在前，大于的在后，然后最中间点较小的j位置的值的与第一个值交换，交换后前面的小于基准值，后面的大于基准值
- int partition(int b[],int first,int last){
- int x = b[first],temp = 0;
- int i = first,j = last + 1;//因为后面判断是–j
- while(true){
- while(b[++i] < x && i <= last);
- while(b[–j] > x);
- if(i >= j){
- break;
- }
- temp = b[i];
- b[i] = b[j];
- b[j] = temp;
- }
- b[first] = b[j];
- b[j] = x;
- return j;
- };
- void quickSort(int a[],int beg,int end){
- if(beg < end){
- int q = partition(a,beg,end);
- quickSort(a,beg,q-1);
- quickSort(a,q+1,end);
- }
- };
- int main()
- {
- int test[] = {34,5,4,5,3,2,6,90,5};
- quickSort(test,0,8);
- for(auto c : test){
- cout<<c<<” “;
- }
- cout<<endl;
- return 0;
- }
注意：两头交换法，最后填坑点的选择与基准值的选择有关系，当基准值在区间前半部分则填坑点选值较小的j,反之则选i.