数据结构|谁才是排序王中王（快？归？希？）数据结构|数据结构

为啥我们要学习排序呢？
首先，学会排序我们可以整理数据方便我们更好地管理数据，再有就是我们做题时常常会用到排序，反正排序随处可见，那么我们就应该了解一下几种常用且高效的排序方法，如果只会调用库里现成的东西而毫不清楚其核心，那么这种学习是质量不过关的。下面就快速排序，希尔排序，归并排序展开详解。（其他的简单的排序就不详细介绍了）

话不多说，我们直接进入主题
一、快排说到快排很多小伙伴可能都跃跃欲试了，纷纷迫不及待地喊着 “我会！我会！这不就二十行代码就能搞定嘛”。
但是你真的了解快排嘛，你知道快排有多种写法吗？快排是怎么优化的？非递归的快排怎么写？
如果你能对答如流，我只能说一句："膜拜大佬，让我抱你的大腿好吗？”
如果对以上问题还有少许疑问，那就往下看吧。
第一种：hoare写法制作了个动图供各位看官们理解：

文章图片

hoare（霍尔)是快排的发明者，所以有hoare写法，那么这种方法是怎么实现的呢？

思想：给定一组无序的数据，我们取该组数据的最左边的数或者最右边的数作为一个我们要排的第一个数（基准），找好这个数后，如果是取的最左边的数，那么就从右边开始（用下标来模拟左右两边）去找比它小的数，找到后就再从左边开始（用下标来模拟左右两边）去找比它大的数，然后就交换这两个数（如果开始是取得最右边的数，就是先从左边找大，再从右边找小），然后继续重复上述步骤，直到左右两边的下标相遇了就把开始选的数和相遇的位置的数进行交换。然后我们最开始选的数就会被放到它正确的位置上。这只是一个数到了正确的位置上，要想每个数都被放到正确的位置上，就要递归（分治)相遇位置以左和以右的区间。

说明一下：这里为什么是从右边找比选定的数小的数，左边找比选定的数大的数，然后进行交换呢？
因为如果我们要把一个数放到其正确的位置上（有序状态的位置），那么它左边肯定都是比它小的数，它右边都是比它大的数，所以我们要做的就是把右边比选定的数小的数往左边挪，把左边比选定的数大的数往右边挪，这样才能实现有序。
代码实现：

//hoare版本取左为key右边先走，找小，然后左边再走，找大，然后交换，继续此步骤直到left与right相遇 int partSort(int* a, int left, int right) { int key = left; while (left < right) {while (left < right&&a[right] >= a[key]) { --right; }while (left < right&&a[left] <= a[key])//这里有两个细节，内循环也要保证left小于right还有就是a[left]<=a[key]不能却等于号否则特殊情况死循环 { ++left; } swap(&a[left], &a[right]); } swap(&a[key], &a[left]); return left; }void Qsort(int* a, int begin, int end) { if (begin >= end)//要有限制条件让递归返回程序停下来 { return; } //这是个优化后边会提 /*if (end - begin + 1 < 13) { InsertSort(a+begin, end - begin + 1); return; }*/ int key=partSort3(a, begin, end); Qsort(a, begin, key - 1); //再递归去排好key左边和右边的区间才能实现排序 Qsort(a, key + 1, end); }

第二种：挖坑法

文章图片

挖坑法其实跟上面的hoare法差不了太多，差别就是hoare法是先左右都分别找到了比选的数（基准）大或小的数后再进行交换，而挖坑法就不同了，它是先保存我们选好的数，这个位置就可以被其他数覆盖，相当于是一个坑位，然后先让一边去找小或者找大找到了就把找到的数放到坑位里，然后找到的数的位置就形成了新的坑位，然后让另一边去找大或找小，找到了还是放到坑位，最后左右两边相遇就停止，把最开始保存的选的数（基准）放到相遇的位置即可，然后递归去排序相遇位置的左边和右边就可以实现整组数据的有序。

代码实现：

void Qsort(int* a, int begin, int end) { if (begin >= end)//要有限制条件让递归返回程序停下来 {return; } int key=partSort3(a, begin, end); Qsort(a, begin, key - 1); Qsort(a, key + 1, end); } //挖坑法 int partSort1(int* a, int left, int right) { int pit = a[left]; //记录坑位 while (left < right) { while (left < right && a[right] >= pit)//左边找到了小的就丢到右边的坑里右边形成新坑 { --right; } a[left] = a[right]; //右边找到小的就丢到左边的坑里左边形成了新的坑 while (left < right && a[left] <= pit) { ++left; } a[right] = a[left]; } a[left] = pit; //把最开始的坑里的数据，赋值给左边的位置 return left; }//更高级的双指针法 int partSort3(int* a, int begin, int end) { /*int mid = getMidIndx(a, begin, end); swap(&a[mid], &a[begin]); */ //针对给定数据有序或接近有序的优化 int key = begin; int prev = begin; int cur = begin + 1; while ( cur<=end ) { if (a[cur] < a[key] && a[++prev] != a[cur])//后面的条件是为了当prev加加后和cur指向的同一元素就不用交换，没有意义 { swap(&a[cur], &a[prev]); } cur++; } swap(&a[prev], &a[key]); return prev; }

第三种：前后指针法

文章图片

这种写法就比较新颖了，是定义两个指针prev 和
cur（prev最开始指向的是该组数据的第一个元素），一前一后，cur去遍历数据（就要一直往前走），如果cur指向的值比prev指向的值大就让cur一直往下走（cur的目的是找小于基准的数往左边挪），当cur指向的值小于prev指向的数就让prev往后走一步（prev++)，然后交换prev和cur所指向的值，一直重复此步骤直到cur遍历完了数组，最后交换prev和第一个元素的值，这样选的基准就到了正确的位置上，再递归prev的左边和右边就可以实现整个有序

。
代码实现：

//前后指针法（开始prev和cur一前一后，然后开始往后cur找小，找到了就让prev加加，交换cur和prev位置的值， //然后继续找小，当cur越界后就交换key和prev位置的值即可) int partSort2(int* a,int left,int right) { int key = left; //记录下标，不要记录值，因为key是局部变量出来作用域被销毁，记录值没有用 int prev = left; int cur = left + 1; while (cur <= right) { while (cur<= right&&a[cur] >= a[key])//跟key相等的可以放在左边也可以放在右边，如果也交换就是白交换的没有意义，做无用功 { ++cur; } if (cur <= right) { ++prev; swap(&a[prev], &a[cur]); //++cur; //这里要在交换了prev和cur后让cur往后走一步，否则如果后面的值一直都是比key下标对应的值小的话那么prev就会超过cur就会造成越界错误 } cur++; //就是cur必须是一直往后走的 } swap(&a[prev], &a[key]); return prev; }

快排针对有序或解近有序数据的优化

了解了快排的思想后，我么知道它是从左边或者右边选出一个基准，然后把它放到正确的位置上，再分治处理未有序的区间。那么如果我们给一个有序的数组给快排排序就会出现选的第一个数是最大或者最小的数，那么把它放到正确的位置后，就要递归其正确位置的左右区间，然后再分区间递归，此时就只会是一边的区间有效，另一边的区间是无效的，相当于我们每次递归只是让需要排序的区间缩小了1，说明要实现N个数的有序，就要递归N次，如果N是上千万甚至更大，就会一直递归开辟栈帧，最终就会导致栈爆了（满了，不够用了），这就要针对性地优化。

文章图片

文章图片

优化方法：对区间进行左右中三数取中作为基准就可以保证每次选的基准都不可能是这段区间的最大值或者最小值了，就不会出现每次递归都只有一边区间有效的情况了，效率就会被提升了。
代码：

//优化防止左边或者右边是最大或者最小值，就写一个左右中三数取中的函数，返回三者中中间的那个值， //就可以防止数据有序带来的快排调用栈，崩溃的情况了 //这个方法也可以用三目操作符来写就会很简洁 int getMidIndx(int* a, int left, int right) { assert(a); int mid = (left + right) / 2; if (a[left] > a[right]) { if (a[right] > a[mid]) { return right; } else if (a[mid] > a[left]) { return left; } else { return mid; } } else//a[left] { if (a[right] < a[mid]) { return right; } else if (a[mid] < a[left]) { return left; } else { return mid; } } }//这样就可以再partsort中把key和mid交换就保证了选的基准不是最大也不是最小 int partSort3(int* a, int begin, int end) { int mid = getMidIndx(a, begin, end); swap(&a[mid], &a[begin]); //针对给定数据有序或接近有序的优化三数取中 int key = begin; int prev = begin; int cur = begin + 1; while ( cur<=end ) { if (a[cur] < a[key] && a[++prev] != a[cur])//后面的条件是为了当prev加加后和cur指向的同一元素就不用交换，没有意义 { swap(&a[cur], &a[prev]); } cur++; } swap(&a[prev], &a[key]); return prev; }

快排的小区间优化
递归法的快排如果对于数据量很大就会有很深的递归，尤其是区间越小递归的次数还不少，所以可以针对小区间的排序可以进行优化，把递归改成插入排序即可避免多次的递归，数据太少还进行递归有些浪费栈帧。把小数量的数据有序的方法改成插入排序，就可以很好的避免不必要的栈帧的开辟，提高了效率。

文章图片

非递归如何实现快排

可以利用栈和队列进行存储每次需要排序的区间，用partsort对该区间进行排序，该区间排好了序就出栈或队列，直到栈或者队列为空了就完成了排序。

1.用栈（因为栈具备后进先出特性，所以用栈存储区间来实现快排是先把一边区间的数据排好序，再对另一边的数据排序）

//快排的非递归写法（调用的是栈） void unrecursionQsort1(int* a, int begin, int end) { stack st; st.push(begin); st.push(end); while (!st.empty()) { int right = st.top(); st.pop(); int left = st.top(); st.pop(); int key=partSort2(a, left, right); //既然是用的左边为key那么就不要用有三数取中的partsort否则就不一定是取的左边为key了 if (key - 1 > left)//如果这个区间是是大于1的就要继续把区间压入到栈知道区间是等于1或者是小于1就停止 { st.push(left); st.push(key - 1); } if (key + 1 < right)//同上 { st.push(key + 1); st.push(right); } } }

2.用队列（因为队列具备先进先出特性，所以用队列来存储区间来实现快排是左右交替着进行排序的）

//用队列实现 void unrecursionQsort2(int* a, int begin, int end) { queue q; q.push(begin); q.push(end); while (!q.empty()) { int left = q.front(); q.pop(); int right = q.front(); q.pop(); int key = partSort2(a, left, right); if (left < key - 1) { q.push(left); q.push(key - 1); } if (key + 1 < right) { q.push(key + 1); q.push(right); } }}

二、希尔排序希尔排序
希尔排序法又称缩小增量法。它是针对直接插入排序算法的改进，它通过比较相距一定间隔的元素来进行，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。

文章图片

代码其实就是插入排序的改良版：

//2.希尔排序 void shellSort(int* a, int n) { int gap = n; while (gap > 1) { gap = (gap / 3) + 1; //gap每次缩小3倍，但要保证最后一次是1，才能实现整组数据有序 int end = gap; for(int i=0; i= 0) { if (tmp < a[end]) { a[end + gap] = a[end]; end-=gap; } else { break; } } a[end + gap] = tmp; } } }

三、归并排序归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

文章图片

递归法是先将区间的中间mid算出来，以mid为准将区间分成[begin,mid]和[mid+1,end]这两个闭区间，然后分别递归这两个区间，当begin>=end的时候就结束，这样一个大区间就会被分割成一个一个的区间为1的单位区间，就实现了割的目的。
接下来就是合并，这里是借用了一个长度和原数组相同的数组tmp,最开始遍历两个单位为1的子区间，优先取小的放到tmp数组中，这样最开始合并好的区间（长度为2），就是有序的了，然后又会合并两个长度为2的有序的子区间，形成一个长度为4的有序的区间，两个这样的长度为4的区间又可以当作子区间，去形成长度为8的区间，以此类推，一直递归就可以实现排序的功能。

//归并排序 //递归写法 void _mergeSort(int* a, int begin, int end,int* tmp) { if (begin >= end) { return; } //分离区间 int mid = (begin + end) / 2; _mergeSort(a, begin, mid, tmp); _mergeSort(a, mid + 1, end, tmp); //分离好区间后，开始归并区间 int i = begin; int begin1 = begin; int end1 = mid; int begin2 = mid + 1; int end2 = end; //printf("归并区间[%d,%d],[%d,%d]\n", begin1, end1, begin2, end2); while (begin1 <= end1 && begin2 <= end2)//闭区间，要加等号 { if (a[begin1] < a[begin2]) { tmp[i++] = a[begin1++]; //拷贝到对应的位置 } else { tmp[i++] = a[begin2++]; } } while (begin1 <= end1)//因为这里是闭区间，所以要加上等号 { tmp[i++] = a[begin1++]; } while (begin2 <= end2) { tmp[i++] = a[begin2++]; } //把tmp拷贝到a中要对应位置拷贝要用a+begin表示拷贝到a数组的起始位置细节 memcpy(a+begin, tmp+begin,(end-begin+1)*sizeof(int)); //借用tmp这块空间把数据调整好了顺序之后在拷贝回到a数组中就实现了有序的归并了 }

非递归写法（要注意控制边界）
根据规律我们可能会想到这归并的过程都是跟2有关的，分割是对半分（除2）直到区间只有一个数，合并也是11合并，两个小区间合并成1个大区间，就可以用循环来进行控制要排序的区间。
这里就直接给出循环控制区间的代码了

for (int i = 0; i < n; i+=2*gap) { int begin1 = i; //左区间的开始 int end1 = i+gap-1; //左区间的结束 int begin2 = i + gap; //右区间的开始 int end2 = i + 2 * gap - 1; //右区间的结束 }

知道了区间就可以用用while循环来把两个子区间的数据优先取小，依次往tmp数组里放，让tmp里存的是两个子数组元素集合的有序集合。（就是把这两个子区间排序放到tmp中），之后再把tmp数组拷贝到对于的a数组（传过来的排序数组）的对应位置。
根据上面的思路写代码：
下面是初级版本（有漏洞）

//非递归写法 void unrecursionmergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); int gap = 1; //开始是gap为1，使得1+1=2的效果，即把两个为1的区间合并 while (gap < n) { for (int i = 0; i < n; i+=2*gap) { int begin1 = i; int end1 = i+gap-1; int begin2 = i + gap; int end2 = i + 2 * gap - 1; int indx = begin1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[indx++] = a[begin1++]; } else { tmp[indx++] = a[begin2++]; } } while (begin1 <= end1) { tmp[indx++] = a[begin1++]; } while (begin2 <= end2) { tmp[indx++] = a[begin2++]; }} memcpy(a, tmp, n * sizeof(int)); gap *= 2; //每合并好一次，子区间范围就扩大一倍下一次合并的子区间就要相对应的扩大 } free(tmp); }

文章图片

再每次开始归并的时候打印归并的区间如上图
看起来或许很好理解，但是上面的例子是8个数据是2的次幂，想想如果数据个数不是二的次幂会怎样呢？

文章图片

会出现不合法的范围（数组长度为9，有效范围是0-8）
但是这里出现了10、11、12、15 等超过范围的区间，对应的四个begin1 end1 begin2 end2begin1是等于i的，而i又是小于n的，所以begin1是无论如何都不会超出范围的，剩下的三个都是和mid有关的，都有超过范围的风险。所以要控制这三个变量的范围不能超过范围。

文章图片

正确的非递归归并代码：

//非递归写法 void unrecursionmergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); int gap = 1; while (gap < n) { for (int i = 0; i < n; i+=2*gap) { int begin1 = i; int end1 = i+gap-1; int begin2 = i + gap; int end2 = i + 2 * gap - 1; //printf("归并区间[%d,%d],[%d,%d]\n", begin1, end1, begin2, end2); //这里如果是数据个数满足二的次方就没有问题但是如果是奇数就会出现问题所以要进行特殊判断 // 因为begin1是直接等于i的，并且i是小于n的，所以begin1是不会越界的 // 那么要考虑的就是剩下的三个与gap有关的 end1 begin2 end2 了 // 如果是直接对着三个进行判断如果越界就让其等于边界，就可能会有重复的数被放到a数组里,造成越界 // 所以这里要分三种情况判断 // 1.如果end1 越界了说明后面都是越界了，就让其都为无效的区间 // 2.如过end1 没有越界，begin2 越界了就说明前面的区间有效直接让后面的区间无效即可 // 3.如果begin2 没有越界 end2 越界了就直接让end2 等于边界即可 // 这样就针对不是2的次方个数据也能很好的处理了 if (end1 >= n) { end1 = n - 1; begin2 = n; //让begin2 大于end2 就是无效区间了会被跳过 end2 = n - 1; } if (begin2 >= n) { begin2 = n; end2 = n - 1; } if (begin2= n) { end2 = n - 1; } int indx = begin1; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] < a[begin2]) { tmp[indx++] = a[begin1++]; } else { tmp[indx++] = a[begin2++]; } } while (begin1 <= end1) { tmp[indx++] = a[begin1++]; } while (begin2 <= end2) { tmp[indx++] = a[begin2++]; }} memcpy(a, tmp, n * sizeof(int)); printarray(a, 9); gap *= 2; } free(tmp); }

到了这里本文就结束了
综合而言，优化后的快排，适应各种情况的排序，就是是上亿的数据进行排序，都能很快。但是归并排序才是排序王中王，是大哥！
此图为证：
对于1一个的随机数据，希尔36秒，快排28秒，大哥只用了18秒。大哥牛逼！！！