4、堆排序
堆排序我们之前的文章已经详细讲解过，详情见这篇博客：【数据结构】堆的拓展延伸 —— 堆排序 和 TopK问题
其中时空复杂度我们也分析过：
时间复杂度： O ( N × l o g N ) O(N \times log N) O(N×logN)，空间复杂度 O ( 1 ) O(1) O(1) 。
5、冒泡排序
5.1 排序思路
冒泡排序属于交换排序，所谓交换排序就是就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。
冒泡排序可能是这篇文章中最”亲切“的排序了。因为这个排序十分形象，并且容易理解。这个排序像水面冒气泡一样，从底部(数组开头)冒到水面上(数组结尾)，一次冒一个数据，所以被形象的称为“冒泡排序”。
我们再看一下动图：
再从代码层面分析一下：
n n n 个数，那么就需要冒泡 n − 1 n - 1 n−1 趟，将数据冒到结尾，在每趟冒泡排序中，比较相邻两个元素，如果满足条件，则交换。
5.2 代码实现
void BubbleSort(int* a, int n) { // n - 1 趟 for (int j = 0; j < n - 1; j++) { int flag = 1; // 交换次数随着趟数减少 for (int i = 0; i < n - j - 1; i++) { if (a[i] > a[i + 1]) { Swap(&a[i], &a[i + 1]); flag = 0; } } if (flag) { break; } } }
仔细看，其实这里我们的代码是优化过的：如果一趟冒泡排序中，没有发生交换，说明有序，那么 break 退出循环。
比如序列：
1 2 5 6 7 ，在一趟冒泡排序中始终满足 a [ i ] ≤ a [ i + 1 ] a[i] \le a[i + 1] a[i]≤a[i+1] ，没有发生交换，说明它本身是有序的，所以无需排序了，直接退出。
5.3 时空复杂度⭐️
冒泡排序的时间复杂度为 O ( N 2 ) O(N^{2}) O(N2) ，大家可能会疑惑，冒泡排序不是优化过了吗？为什么时间复杂度为 O ( N 2 ) O(N^{2}) O(N2) ？
接下来为大家解答，冒泡排序每次的比较次数，是随着趟数而减少的，找一下规律，其实可以发现，它的总执行次数是一个公差为 − 1 -1 −1 的等差数列： ( n − 1 ) + ( n − 2 ) + . . . + 1 (n - 1) + (n - 2) + ... + 1 (n−1)+(n−2)+...+1 ，根据等差数列求和公式得： ( n − 1 + 1 ) × ( n − 1 ) 2 \frac{(n - 1 + 1) \times (n - 1)}{2} 2(n−1+1)×(n−1) ，化简得 n 2 2 − n 2 \frac{n^{2}}{2} - \frac{n}{2} 2n2−2n ，根据时间复杂度规律，最终为 O ( N 2 ) O(N^{2}) O(N2) 。
而我们的优化是只对 数组前半部分有序 或 整体几乎有序 才有优化作用！如果有序的部分在后半段，每趟排序还是要从头开始一一比较，相当于还是重新排序。
而且数组前半部分有序的优化程度也不大，最好情况是 优化后 在 整体有序 的情况下，遍历一遍数组，通过 break 退出，这时 最好时间复杂度为 O ( N ) O(N) O(N) 。
综上，取最坏情况，时间复杂度为 O ( N 2 ) O(N^{2}) O(N2)。
空间复杂度为 O ( 1 ) O(1) O(1) 。
6、快速排序⭐️
6.1 算法思想
快速排序是 H o a r e Hoare Hoare 于1962年提出的一种二叉树结构的交换排序方法，其 基本思想 为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。
6.2 快排递归版本
上方我们已经给出了思想，我们这边再具体解释一下。
快排为交换排序的一种。快排在开始时，会选择一个 key 做基准值，并设定 给定，然后进行单趟排序，单趟排序后，当排序停止，会把 key 的索引或 key 值本身与边界某一值交换，形成区间划分。
这个区间划分通常为 key 左边的值都小于 key ，key 右边的值都大于 key ，这样就使得区间被划分了。
中间的 key 值不用管，当前 key 值已经到了正确的位置。那么现在排序就变为：对左区间和右区间的排序。
那么每次排序后都会确定一个元素的位置，确定位置后继续划分区间…这样的过程实际上就是递归，通过递归，对设定的基准值分割开的左右区间完成排序。
递归的返回条件为 左区间索引 ≥ 右区间索引 左区间索引 \ge 右区间索引 左区间索引≥右区间索引 ，此刻说明区间只有 1 1 1 个元素或无元素。
根据上述解释，我们可以大约写出框架：
void QuickSort(int* a, int begin, int end) { if (begin >= end) { return; } // 对左右区间进行划分 int key = partion(a, begin, end); // 递归左右区间 QuickSort(a, begin, key - 1); QuickSort(a, key + 1, end); }
上述为快速排序递归实现的主框架，我们可以发现与这个框架与二叉树前序遍历非常像，对于认真看完二叉树博客的小伙伴们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，最后我们只要分析如何按照 基准值 来对区间中数据进行划分即可。
而按照基准值划分区间的方法有三种，分别为 h o a r e hoare hoare 版本、挖坑法、双指针版本 ，接下来我们一一讲解。
6.3 hoare 版本
hoare 大佬的这个版本十分惊艳，但是也是遗留 “坑” 最多的一个版本(自认为)。为什么这么说呢，等过会我们就知道了。
先看动图：
hoare 版本的思想是这样的：
首先取左边界为基准索引 k e y key key ，定义两个指针 l e f t 、 r i g h t left、right left、right 分别指向最左边的元素和最右边的元素。
r i g h t right right 先走，如果 r i g h t right right 指向的元素大于 k e y key key 指向的元素，则 r i g h t − − right-- right−− ，如果指向元素小于 k e y key key 指向的元素，则停止；
停止之后， l e f t left left 开始走，如果 l e f t left left 指向的元素小于 k e y key key 指向的元素，则 l e f t + + left++ left++ ，如果指向元素大于 k e y key key 指向的元素，则停止；
当 e f t eft eft 和 r i g h t right right 都停下后，交换 l e f t left left 和 r i g h t right right 位置的值。
直到 l e f t ≥ r i g h t left \ge right left≥right ，循环停止。
上面过程就保证了 l e f t left left 和 r i g h t right right 相遇的位置的值是小于 k e y key key 的！！！ 此刻交换 a [ l e f t ] / a [ r i g h t ] 和 a [ k e y ] a[left] / a[right] 和 a[key] a[left]/a[right]和a[key] ，令 k e y = l e f t 或 r i g h t key = left 或 right key=left或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 则反一下。
下面讲一下细节 ：
细节1：我们有没有想过，为什么 l e f t left left 和 r i g h t right right 相遇的位置是小于 k e y key key 的？是巧合还是必然？
这是必然的，我们分析一下情况，一共有两种情况：
第一种是 r i g h t right right 停住， l e f t left left 遇到 r i g h t right right ，相遇位置就是 r i g h t right right 停住的位置。
当前情况就是 r i g h t right right 在走时，遇到比 a [ k e y ] a[key] a[key] 小的元素停住了，然后 l e f t left left 走时，和 r i g h t right right 位置是小于 k e y key key 。
第二种是 l e f t left left 停止， r i g h t right right 遇到 l e f t left left ，相遇位置是 l e f t left left 停住的位置。
l e f t left left 和 r i g h t right right 已经交换过一次元素，所以 l e f t left left 的位置必定小于 k e y key key ， l e f t left left 停住了，之后 r i g h t right right 走，直到和 l e f t left left 相遇，相遇位置是小于 k e y key key 的。
还有一种特殊情况，就是 r i g h t right right 先走，右边的数字都比 a [ k e y ] a[key] a[key] 大， r i g h t − − right-- right−− ， r i g h t right right 一直走到与 l e f t left left 重合， a [ k e y ] a[key] a[key] 和 a [ l e f t ] a[left] a[left] 交换后不变。
细节2：开头说过 h o a r e hoare hoare 大佬的版本有很多坑，坑在哪里？如何解决？
其实这里容易引起的错误还是很多的，比如：
k e y key key 右边的值都大于 k e y key key ，如果循环内部不加限制， r i g h t right right 就会一直 − − -- −− ，当前还不会越界，但是是一个隐患。
左右两边都有和 k e y key key 相等的值，导致左右两边卡死。
举个例子：
例如这种情况， a [ k e y ] = 6 a[key] = 6 a[key]=6 ，右边先走时，由于 a [ r i g h t ] = a [ k e y ] a[right] = a[key] a[right]=a[key] ，所以不走；左边走时，由于 a [ l e f t ] = a [ k e y ] a[left] = a[key] a[left]=a[key] ，所以不走。这样循环就卡死了！
所以，我们一开始的思路是需要 改进 的，当 a [ r i g h t ] ≥ a [ k e y ] a[right] \ge a[key] a[right]≥a[key] 时， r i g h t − − right-- right−−；在 a [ l e f t ] < = a [ k e y ] a[left] <= a[key] a[left]<=a[key] 时， l e f t + + left++ left++。这样就解决了 死循环的问题 。
但是修好了这个 bug 另一个 bug 就冒出来了，之前说过情况 1 1 1 是有隐患的，现在就显现出来了，一旦加上上面的条件，如果 k e y key key 都大于 k e y key key ，那么这边由于没有限制了， r i g h t right right 就 ”飙“ 出去了。
所以在 r i g h t right right 和 l e f t left left 每次走的时候需要加上限制 l e f t < r i g h t left < right left<right 。
由此，我们就可以写出代码：
// hoare 版本 int partion1(int* a, int begin, int end) { int left = begin, right = end; int key = left; while (left < right) { // 右边先走 // 两个条件一个防止跑出去，找大于 a[key] 的值 while (left < right && a[right] >= a[key]) { right--; } while (left < right && a[left] <= a[key]) { left++; } Swap(&a[left], &a[right]); } // 交换值, key 作为分割点 Swap(&a[left], &a[key]); key = left; return key; }
怎么样，是不是挺 “坑” 的(doge)。
6.4 挖坑法
由于 h o a r e hoare hoare 大佬版本遗留的 “坑” 比较多，所以后面就有一些好心人在 h o a r e hoare hoare 版本的基础上，对快排做出了一些改良，比如我们的 挖坑法 。
虽然名字里带“坑”，但是这个方法其实非常通俗易懂。
先看动图：
挖坑法的思想：
挖坑法多了一个 h o l e hole hole ，也就是坑位。我们将 key = a[left] ，将 k e y key key 保存到一个临时变量中，假设 k e y key key 这个位置的值被挖掉了，形成一个坑位。
此时 h o l e hole hole 就是坑位的下标。
依然是右边先走，循环条件为 l e f t < r i g h t left < right left<right 并且 r i g h t right right 指向的元素大于等于 k e y key key ，一旦 r i g h t right right 停下来，那么就把 a [ h o l e ] = a [ r i g h t ] a[hole] = a[right] a[hole]=a[right] ，把 r i g h t right right 指向的值填到坑中，此刻 r i g h t right right 作为新的坑。而 r i g h t right right 之前的值也被转移到了别的地方，这个位置就被看做为空，变成坑。
左边则是相同的思路，同理左边停下后，让 a [ h o l e ] = a [ l e f t ] a[hole] = a[left] a[hole]=a[left] ，让 l e f t left left 作为新的坑。
直到 l e f t ≥ r i g h t left \ge right left≥right 停止。
最后的 h o l e hole hole 就是 k e y key key 值该去的地方，把这个地方填上 k e y key key ，此刻 h o l e hole hole 为分割点。
代码实现：
int partion2(int* a, int begin, int end) { int left = begin, right = end; int key = a[left]; int hole = left; while (left < right) { // 右边找小，填到左边坑里面 while (left < right && a[right] >= key) { right--; } a[hole] = a[right]; hole = right; // 左边找大，填到右边坑里面 while (left < right && a[left] <= key) { left++; } a[hole] = a[left]; hole = left; } a[hole] = key; // 最后 left 和 right 都在坑上，和 hole 是重合的 return hole; }
6.5 前后指针版本
前后指针版本是最难的，也是“最难”的。
说它最难，是因为它本身思路比较抽象，可能看动图都不太好理解；说它“最难”实际上是反话，因为它在某种程度上，又很简单。
先看动图：
前后指针法的思路：
前后指针法的算法思想如下：
定义三个变量， p r e v = b e g i n ， c u r = b e g i n + 1 , k e y = b e g i n prev = begin，cur = begin + 1, key = begin prev=begin，cur=begin+1,key=begin，主要使用 c u r cur cur 来遍历数组。
如果 c u r cur cur 指向的元素比 k e y key key 小，此刻停下来， + + p r e v ++prev ++prev ，交换调整后的 p r e v prev prev 位置和 c u r cur cur 位置的值，完事之后 c u r + + cur++ cur++ 。
如果 c u r cur cur 指向的元素大于等于 k e y key key ，此刻 c u r + + cur++ cur++ ，其他啥也不干。
就这样循环往复，直到 c u r > e n d cur > end cur>end ，此刻交换 p r e v prev prev 和 k e y key key 位置的值。
当前的 p r e v prev prev 作为新的 k e y key key ，为分割点。
这里的 p r e v prev prev 和 c u r cur cur 有两种状况：
紧跟 c u r cur cur ，这时 a [ c u r ] < a [ k e y ] a[cur] < a[key] a[cur]<a[key] ，它俩同步往后走
指向比 k e y key key 大的位置的前一个， p r e v prev prev 和 c u r cur cur 之间就是 ≥ a [ k e y ] \ge a[key] ≥a[key] 的值。
每当 a [ c u r ] < a [ k e y ] a[cur] < a[key] a[cur]<a[key] ， c u r cur cur 位置小于 a [ k e y ] a[key] a[key] 的值总是会被推到前面。
循环的过程就相当于是将小于 a [ k e y ] a[key] a[key] 的值往前翻，大于 a [ k e y ] a[key] a[key] 的值往后像“翻跟头”一样推着走。
最后 p r e v prev prev 的位置指向比 a [ k e y ] a[key] a[key] 大的位置的前一个，那么交换 a [ p r e v ] a[prev] a[prev] 和 a [ k e y ] a[key] a[key] ，让 k e y = p r e v key = prev key=prev ，此刻 k e y key key 为分割点。
优化思路：
实际上我们发现当 p r e v prev prev 紧跟 c u r cur cur 时，它俩指向的是一个位置的元素，所以这种情况是没必要交换的，所以可以提前判断一下 + + p r e v ! = c u r ++prev != cur ++prev!=cur ，如果不满足这个条件，那么干脆就不要交换了，反正是同一个位置的值。
接着来写一下代码：
int partion3(int* a, int begin, int end) { 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 和 key 是相等的 key = prev; return key; }
