6.6 缺陷分析及优化
缺陷1：有序或接近有序序列时间复杂度过高
其实对于快排来说，它的时间复杂度是不稳定的，比如上方三个版本，在乱序的序列中，效率可能还可以，因为选取的 k e y key key 值是随机的。
但是对于有序序列，比如要排正序，但是序列是逆序。如果每次选 k e y key key 还是按照之前的选法，那么每次可能就会选中最边上的一个，选中最大或最小的数，假设序列长度为 N N N ，每次选取一个极端值，就会选取 N N N 次，就会递归 N N N 层，每一层中的时间复杂度为 O ( N ) O(N) O(N) ，那么最终时间复杂度为 O ( N 2 ) O(N^{2}) O(N2) 。
但是这速度对于快排来说，是不是说不过去，我们能否每次选 k e y key key 都 命中一段区间的中位数 ，让每段区间被二分，那么最终就只会递归 l o g N log N logN 层，每层时间复杂度为 O ( N ) O(N) O(N) ，总时间复杂度为 O ( N × l o g N ) O(N \times log N) O(N×logN) 。就像下图，像一棵二叉树一样。
所以这边就引申出了第一个优化：三数取中
所谓三数取中，就是不取最大，不取最小，在 b e g i n , e n d , （ b e g i n + e n d ） / 2 begin, end, （begin + end） / 2 begin,end,（begin+end）/2 中选取一个中间值，尽量让 k e y key key 可以命中每段区间中点。
而这段逻辑的话，其实也并不复杂，直接上代码：
int GetIndexMid(int* a, int begin, int end) { int mid = (begin + end) >> 1; if (a[begin] < a[mid]) { if (a[mid] < a[end]) { return mid; } else if (a[begin] > a[end]) { return begin; } else { return end; } } else // a[begin] >= a[mid] { if (a[mid] > a[end]) { return mid; } else if (a[end] > a[begin]) { return begin; } else { return end; } } }
缺陷2：不必要的递归层数太多，空间浪费
假设我们只有 10 10 10 个数，那么这种情况采用递归是不是浪费空间，是不是多此一举？
所以当 e n d − b e g i n + 1 < 10 end - begin + 1 < 10 end−begin+1<10 时，可以采用插入排序优化，这样子就没必要开那么多层函数栈帧。
对于一棵满二叉树，最后一层的节点数占总结点数的 1 2 \frac{1}{2} 21 ，倒数第二、三层分别为 1 4 、 1 8 \frac{1}{4}、\frac{1}{8} 41、81 ，我们就假定快排递归展开后，最后形态为完全二叉树。
假设当前有10个节点，那么对于下图中红色箭头标出的点来说就无须递归，因为再细分也就是一个数：
那么大约就可以节省下三层的递归，下三层的节点数占总结点数的 87.5 % 87.5\% 87.5% ，省去了大部分的递归。
所以这边就引申出了 第二个优化：小区间优化
这边我们范围给大一点，当 e n d − b e g i n + 1 < 15 end - begin + 1 < 15 end−begin+1<15 时，就采用直接插入排序优化。
递归框架中发生的变化：
void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } // 小于一定数目使用 直接插入排序 if ((end - begin + 1) < 15) { // 数组位置：a + begin // 元素个数：end - beghin + 1 InsertSort(a + begin, end - begin + 1); } else { int key = partion(a, begin, end); // 递归左右区间 QuickSort(a, begin, key - 1); QuickSort(a, key + 1, end); } }
缺陷3(最致命的一点)：对于相同数据来说，三数取中无效，时间复杂度过高
比如 2 2 2 2 2 2 2 2 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 \ 2 2 2 2 2 2 2 2 2 这个序列来说三数取中是完全无效的，特别数据量一大，不仅容易超时，还容易爆栈。
所以就需要优化，这就引申出了第三个优化：三路划分。
之前的我们是主要将区间划分为两段， [ b e g i n , k e y − 1 ] [begin, key - 1] [begin,key−1] 和 [ k e y + 1 , e n d ] [key + 1, end] [key+1,end] 。 左区间值小于 k e y key key ，右区间值大于 k e y key key ，可以称为 两路划分 。
现在我们需要进行三路划分，就是将区间分割为左区间小于 k e y key key ，中间区间等于 k e y key key ，右区间大于 k e y key key 。
其实这个思路更为简单，简单讲一下思路：
设定一个 c u r = b e g i n + 1 cur = begin + 1 cur=begin+1， l e f t = b e g i n , r i g h t = e n d , k e y = a [ l e f t ] left = begin, right = end, key = a[left] left=begin,right=end,key=a[left]。
就是将区间分割为左区间小于 k e y key key ，中间区间等于 k e y key key ，右区间大于 k e y key key 。
给定一个循环，循环中如果 a [ c u r ] < k e y a[cur] < key a[cur]<key ，此刻交换 c u r cur cur 和 l e f t left left 指向的元素，使 l e f t + + left++ left++ ， c u r + + cur++ cur++ 。(如果一开始这个条件就满足，则会把 k e y key key 逐渐往中间推。)
如果 a [ c u r ] > k e y a[cur] > key a[cur]>key ，此刻 r i g h t right right 这个位置的值比 k e y key key 大，也有可能比 k e y key key 小。交换 c u r cur cur 和 r i g h t right right 指向元素后，如果 c u r + + cur++ cur++ 可能该位置元素就不满足最终区间划分条件，所以这里只能 r i g h t − − right-- right−−.
如果 a [ c u r ] = = k e y a[cur] == key a[cur]==key ，那么只需要 c u r + + cur++ cur++。
当 c u r > r i g h t cur > right cur>right 时， r i g h t right right 后的元素都是大于 k e y key key 的，区间也都调整好了，这时候循环也就停止了。
实际上这一过程就像把和 k e y key key 相等的值往中间推，把比 k e y key key小的值往左边甩，把比 k e y key key 大的值往右边甩，最后等于 k e y key key 的就在中间。
最后分割成的区间就是 [ b e g i n , l e f t − 1 ] , [ l e f t , r i g h t ] , [ r i g h t + 1 , e n d ] [begin, left - 1], [left, right], [right + 1, end] [begin,left−1],[left,right],[right+1,end]，这时等于 k e y key key 的区间不用递归，只需要递归排序左右区间即可。
如果不太理解可以画一下草图，这边博主就不带着画了。
这一过程也是挺简单的，我们直接看代码：
// 三路划分 处理重复数据量大的情况，处理完中间区间就是 22222222222 void QuickSortT(int* a, int begin, int end) { if (begin >= end) { return; } // 三数取中一下 int mid = GetIndexMid(a, begin, end); Swap(&a[mid], &a[begin]); int left = begin, right = end; int cur = begin + 1; int key = a[left]; // 跟 key 相等的值，往后推 // 比 key 小的甩到左边 // 比 key 大的甩到右边 // 和 key 相等的就在中间 while (cur <= right) { if (a[cur] < key) { Swap(&a[cur], &a[left]); left++; cur++; } else if (a[cur] > key) // { // r 这个位置有可能比 Key 大，也有可能比 key 小 // 所以 cur 不 ++ // 如果 cur 比 key 大，之后还是得换回去处理 Swap(&a[cur], &a[right]); right--; } else { cur++; } } // 区间被划分为 [begin, left - 1] [left, right] [right + 1, end] QuickSortT(a, begin, left - 1); QuickSortT(a, right + 1, end); }
6.7 快排递归版本完整代码
这边调用的 partion 我们用 前后指针 的(代码少些doge)：
int GetIndexMid(int* a, int begin, int end) { int mid = (begin + end) >> 1; if (a[begin] < a[mid]) { if (a[mid] < a[end]) { return mid; } else if (a[begin] > a[end]) { return begin; } else { return end; } } else // a[begin] >= a[mid] { if (a[mid] > a[end]) { return mid; } else if (a[end] > a[begin]) { return begin; } else { return end; } } } int partion3(int* a, int begin, int end) { // 三数取中 int mid = GetIndexMid(a, begin, end); Swap(&a[begin], &a[mid]); int prev = begin; int cur = begin + 1; int key = begin; while (cur <= end) { // 找到比 key 小的值时，跟 ++prev 位置交换， // 小的往前翻，大的往后翻 // 重复数据不会交换 if (a[cur] < a[key] && ++prev != cur) Swap(&a[cur], &a[prev]); // 重复数据会交换 /*if (a[cur] < a[key]) Swap(&a[++prev], &a[cur]);*/ // cur 必定会走一步 cur++; } Swap(&a[prev], &a[key]); //return prev; key = prev; return key; } void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } // 小于一定数目使用 直接插入排序 if ((end - begin + 1) < 15) { InsertSort(a + begin, end - begin + 1); } else { int key = partion3(a, begin, end); // 递归左右区间 QuickSort(a, begin, key - 1); QuickSort(a, key + 1, end); } }
6.8 快排非递归版本
其实快排不仅能用递归，还是可以使用非递归的，非递归的好处就是不需要多次递归开辟多层函数栈帧，在空间消耗上略有优势。
快排的非递归需要借助数据结构 - 栈 来完成。
快排递归的过程就相当于对每一段区间进行处理，那么非递归我们可以用两个变量来模拟各个区间。
接下来我们开始展开思路：
一开始，我们将 b e g i n begin begin 和 e n d end end 分别入栈。给定一个循环，如果栈不为空就继续循环。
由于栈是后进先出，所以先用 r i g h t right right 接收 e n d end end 右区间，再用 l e f t left left 接收左区间，在接收完之后，将这两个元素分别出栈。
得到了区间之后，就对区间进行单趟排序(可以调用上面的 h o a r e hoare hoare 等)，用 k e y key key 接收分隔点。
我们再想想处理完一次完整区间后，下一次要如何处理？
先处理左区间 [ l e f t , k e y − 1 ] [left, key - 1] [left,key−1] ，再处理 [ k e y + 1 , r i g h t ] [key + 1, right] [key+1,right] 。由于栈先进后出，所以要先入右区间，在入左区间。
每次循环只会取出两个值，那么就是一小段区间，在取出左区间后，会先处理左区间，然后不断分割小区间，每次取出两个值一直对栈顶上的两个元素的区间进行处理，这样就模拟除了快排的过程。
优化思路：
如果区间内只有 1 1 1 个元素，就无需处理了，所以可以加个条件判断一下，举个例子，对于右区间来说， k e y key key 是分割点， k e y + 1 key + 1 key+1 则是右区间的起始位置，如果 k e y + 1 < r i g h t key + 1 < right key+1<right ，那么说明区间中不止一个元素，这种情况就入栈处理。类比左边也是一样的道理。
// 快排非递归 void QuickSortNorR(int* a, int begin, int end) { ST st; StackInit(&st); // 压栈 StackPush(&st, begin); StackPush(&st, end); while (!StackEmpty(&st)) { // 后进先出，先出 right int right = StackTop(&st); StackPop(&st); int left = StackTop(&st); StackPop(&st); // 先取左区间，后取右区间 // 所以先入右区间再入左区间 int key = partion3(a, left , right); // 如果区间内只有1个元素，则无需入栈 if (key + 1 < right) { StackPush(&st, key + 1); StackPush(&st, right); } if (left < key - 1) { StackPush(&st, left); StackPush(&st, key - 1); } } StackDestroy(&st); }
6.9 时空复杂度
对于快排的时间复杂度，本来是不太稳定的，因为处理有序序列或者序列中元素相同的情况下，可能会造成 O ( N 2 ) O(N^{2}) O(N2) 的时间复杂度。
但是当我们 三数取中 或者 三路划分 后，时间复杂度就相对稳定了。
加上这两个功能之后，如果画出每层的元素情况，就像下图一样，像一棵完全二叉树。
由于每次每一块都是被二分，一共 N N N 个节点，所以这边大约就是 l o g N log N logN 层。
样图：
那么对于递归的版本，就需要开 l o g N log N logN 层栈帧；对于非递归的版本，原理和递归类似，也认为处理 l o g N log N logN 次。
每次递归/处理中，时间复杂度为 O ( N ) O(N) O(N) 。所以快排的时间复杂度为 O ( N × l o g N ) O(N \times log N) O(N×logN) 。
而对于时间复杂度也因为优化的原因，几乎不会出现极端情况，我们认为最佳情况就是像二叉树一样，最多开辟 l o g N log N logN 层栈帧，根据递归版本根据空间复杂度的计算公式： 递归深度 × 每次递归中额外空间消耗 递归深度 \times 每次递归中额外空间消耗 递归深度×每次递归中额外空间消耗，每次递归消耗空间为 O ( 1 ) O(1) O(1) ，一共 l o g N log N logN 层，所以空间复杂度为 O ( l o g N ) O(log N) O(logN) 。对于非递归的也是一个道理，推一下就明白了~
7、归并排序⭐️
7.1 算法思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
如果说快排是前序，那么归并恰巧就是它的对立面，归并排序相当于是二叉树的后序遍历，我们看一张图：
归并排序是逐个分解为一个个小区间，直到不能分割为止，然后一步步 归并起来 ，逐层返回。
而这一过程需要借助一个辅助数组 tmp 来完成归并过程。
对于归并的详细过程可以参考下图：
7.2 归并递归版本
学习过之前我们算法笔记的同学们相信已经对归并有一些了解了，兼顾没怎么了解过的同学，我在这边简单梳理一下思路：
对于归并排序来说，首先开辟一个辅助数组 t m p tmp tmp 。我们每一次取一个中间点 m i d mid mid 。
然后按照后序遍历的方式，分别递归左右区间： [ b e g i n , m i d ] [begin, mid] [begin,mid] ， [ m i d + 1 , e n d ] [mid + 1, end] [mid+1,end] 一直递归到底部，递归的返回条件为 b e g i n > = e n d begin >= end begin>=end 。
然后开始归并，设定相关变量，然后将两区间内对应元素由小到大放置到 t m p tmp tmp 数组对应位置处。
如果放置过程结束，一个数组没有放置完，则需要在循环结束后，将数组的数据全部倒入 tmp 数组中。
在上面的过程完毕之后，再把 t m p tmp tmp 数组中的数据拷贝回原数组。
最终，递归逐层返回后，就完成了归并过程。
过程不难，注意点我也都在注释部分标注了：
void _MergeSort(int* a, int begin, int end, int* tmp) { if (begin >= end) { return; } int mid = (begin + end) >> 1; // 递归到底部 _MergeSort(a, begin, mid, tmp); _MergeSort(a, mid + 1, end, tmp); int begin1 = begin, end1 = mid; int begin2 = mid + 1, end2 = end; /* * 第一种拷贝回原数组的方式 - memset * 此种做法 cnt 从 begin 开始 * memset 从 begin 位置开始，一共拷贝 end - begin + 1 个元素 * 和下面做法道理相同 */ // int cnt = begin; /* * 第二种拷贝回原数组的方式 - 循环拷贝 * 此种做法 cnt 从 0 开始 * 开始拷贝的位置从 begin 开始 * cnt 最终的长度就是 [begin, end] 之间的长度 * 没问题 */ int cnt = 0; while (begin1 <= end1 && begin2 <= end2) { // 保持稳定性 if (a[begin1] <= a[begin2]) { tmp[cnt++] = a[begin1++]; } else { tmp[cnt++] = a[begin2++]; } } while (begin1 <= end1) tmp[cnt++] = a[begin1++]; while (begin2 <= end2) tmp[cnt++] = a[begin2++]; // 方法1 // memcpy(a + begin, tmp + begin, sizeof(int) * (end - begin + 1)); // 方法2 for (int i = begin, j = 0; i <= end; i++, j++) { a[i] = tmp[j]; } } void MergeSort(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("mallol fail"); return; } _MergeSort(a, 0, n - 1, tmp); }
7.3 归并排序非递归版本
归并排序的非递归版本在这一块是一个难点，因为这个本身就不容易想到。
我们先想一下，对于归并排序来说，能不能借助辅助数据结构实现？
如果用栈，那是不太行的。因为归并是一种类似二叉树后序遍历的排序，当将区间入栈后，把区间拿出来处理，之后要继续分割时，一段区间可能就不见了，所以借助辅助数据结构时不太行的。
所以我们可以不借助数据结构，用一种相对简单的方法完成。
我们可以设定一个 r a n g e N rangeN rangeN ，控制我们的区间大小， r a n g e N rangeN rangeN 就是归并时每组的数据个数。由于我们是类似二叉树后序遍历的方式，所以我们一开始的归并实际上就是 r a n g e N rangeN rangeN 为 1 1 1 情况。
如下图：
通过每次改变 r a n g e N rangeN rangeN 实际上也就是改变了区间大小，就模拟除了归并递归到底，从小区间合并逐渐到大区间合并的过程。所以我们就让 r a n g e N rangeN rangeN 每次 × 2 \times 2 ×2 ，这样子就是归并每次扩大区间的过程。
但是上面的方法只能解决数组长度恰巧被整除的情况，对于无法被整除的情况可能就会造成越界。
比如 n = 13 n = 13 n=13 。在 r a n g e N = 4 rangeN = 4 rangeN=4 时，最后一段区间 [ 13 , 16 ] [13, 16] [13,16] 越界，所以这里是需要做出一下调整的。
我们设置四个点 b e g i n 1 = i , e n d 1 = i + r a n g e N − 1 , b e g i n 2 = i + r a n g e N , e n d 2 = i + 2 ∗ r a n g e N − 1 begin1 = i, end1 = i + rangeN - 1, begin2 = i + rangeN, end2 = i + 2 * rangeN - 1 begin1=i,end1=i+rangeN−1,begin2=i+rangeN,end2=i+2∗rangeN−1 四个点来规定两段区间。
列举一下，这四个点的越界情况，我们可以分为三种情况：
e n d 1 , b e g i n 2 , e n d 2 end1, begin2, end2 end1,begin2,end2 越界
begin2,end2 越界
end2 越界
以上就是三种越界情况，我们需要分别处理：
处理方式分为 修正区间 和 不修正区间 ：
修正区间 ：
第一种越界情况，实际上就是 e n d 1 ≥ n end1 \ge n end1≥n ，那么这种情况修正区间的话，这时将 e n d 1 = n − 1 end1 = n - 1 end1=n−1 ，之后将没有越界的部分拷贝到 t m p tmp tmp 数组中，然后将 [ b e g i n 2 , e n d 2 ] [begin2, end2] [begin2,end2] 修正为一个不存在的区间。
第二种越界情况，就是 b e g i n 2 ≥ n begin2 \ge n begin2≥n ，这种情况下直接将 [ b e g i n 2 , e n d 2 ] [begin2, end2] [begin2,end2] 修正为不存在的区间即可。
第三种越界情况，就是 e n d 2 ≥ n end2 \ge n end2≥n，这种情况将 e n d 2 = n − 1 end2 = n - 1 end2=n−1 ，让两端区间正常归并。
这种情况可以边归并边拷贝，也可以一组归并完了拷贝。
不修正区间 ：
第一种越界情况，修正区间之后实际上就是拷贝的原数组的数据，所以没必要修正， break 掉。
第二种越界情况，实际上也是拷贝原数据，也可以 break 。
但是第三种越界情况，就需要修正一下，否则这次归并无法完成，之后的归并也都错误了，让 e n d 2 = n − 1 end2 = n - 1 end2=n−1 。
这种情况只能边归并边拷贝，因为有些区间是未处理的，如果贸然进行拷贝会把随机值，或者错误数据拷贝进来。
好了，到这边，归并非递归的思路我们就理完了，接下来我把两个版本都写下来 ：
修正区间：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int rangeN = 1; while (rangeN < n) { // 一组归并的跨距为 2 * rangeN for (int i = 0; i < n; i += 2 * rangeN) { int begin1 = i, end1 = i + rangeN - 1; int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1; int j = i; // 修正区间 if (end1 >= n) { end1 = n - 1; // begin2 和 end2 修正为不存在的区间 begin2 = n; end2 = n - 1; } else if (begin2 >= n) { begin2 = n; end2 = n - 1; } else if (end2 >= n) { end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] <= a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) { tmp[j++] = a[begin1++]; } while (begin2 <= end2) { tmp[j++] = a[begin2++]; } // 可以局部拷贝 //memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } memcpy(a, tmp, sizeof(int) * n); rangeN *= 2; } free(tmp); tmp = NULL; }
不修正区间：
void MergeSortNonR(int* a, int n) { int* tmp = (int*)malloc(sizeof(int) * n); if (tmp == NULL) { perror("malloc fail"); exit(-1); } int rangeN = 1; while (rangeN < n) { for (int i = 0; i < n; i += 2 * rangeN) { int begin1 = i, end1 = i + rangeN - 1; int begin2 = i + rangeN, end2 = i + 2 * rangeN - 1; int j = i; if (end1 >= n) { break; } else if (begin2 >= n) { break; } else if (end2 >= n) { end2 = n - 1; //break; } while (begin1 <= end1 && begin2 <= end2) { // 保持稳定性 if (a[begin1] <= a[begin2]) { tmp[j++] = a[begin1++]; } else { tmp[j++] = a[begin2++]; } } while (begin1 <= end1) tmp[j++] = a[begin1++]; while (begin2 <= end2) tmp[j++] = a[begin2++]; memcpy(a + i, tmp + i, sizeof(int) * (end2 - i + 1)); } // 这里不能外部拷贝，因为有些情况是直接 break 出来的，tmp 中不是正确数据 // memcpy(a, tmp, sizeof(int) * n); // 会把错误数据拷入 rangeN *= 2; } free(tmp); tmp = NULL; }
7.4 时空复杂度
对于归并递归版本，每次都是区间二分，然后开始递归的。所以递归层数是严格的 l o g N log N logN ，每次递归中时间复杂度为 O ( N ) O(N) O(N) ，所以总体时间复杂度为 O ( N × l o g N ) O(N \times log N) O(N×logN) ；对于非递归， r a n g e N rangeN rangeN 每次乘 2 2 2 ，每次 r a n g e N rangeN rangeN 处理的时间复杂度为 O ( N ) O(N) O(N) ，时间复杂度也是 O ( N × l o g N ) O(N \times log N) O(N×logN)。
对于归并排序的空间复杂度，递归和非递归有一些计算上的区别，但是结果不影响。
归并排序首先需要一个 t m p tmp tmp 数组，空间复杂度为 O ( N ) O(N) O(N) 。如果对于递归，还会开 l o g N log N logN 层栈帧，所以递归版本消耗的总空间大月为 N + l o g N N + log N N+logN ，当 N N N 足够大时， l o g N log N logN 省略，所以为 O ( N ) O(N) O(N)；对于非递归，那么就仅仅只有 t m p tmp tmp 的消耗。
所以综上所述，归并的空间复杂度为 O ( N ) O(N) O(N)。
