​

​📝个人主页：@Sherry的成长之路
🏠学习社区：Sherry的成长之路（个人社区）
📖专栏链接：数据结构
🎯长路漫漫浩浩，万事皆有期待

上一篇博客：【排序算法(二)】选择排序（直接选择排序&&堆排序）

1、冒泡排序

1.1 排序思路

冒泡排序属于交换排序，所谓交换排序就是就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置，交换排序的特点是：将键值较大的记录向序列的尾部移动，键值较小的记录向序列的前部移动。

这个排序像水面冒气泡一样，从底部(数组开头)冒到水面上(数组结尾)，一次冒一个数据，所以被形象的称为“冒泡排序”。

看一下动图：

1.2 代码实现

冒泡排序的单趟排序会把前(n-j)个元素中的最大值交换到(n-j-1)的位置(增加数组的有序后缀长度)

 // 单趟排序int j = 0;	//记录排序的趟数 for (int i = j; i < n - j - 1; i++){	//交换次数随着趟数减少if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);flag = 0;}}

排n 个数，那么就需要冒泡n−1 趟，将数据冒到结尾，在每趟冒泡排序中，比较相邻两个元素，如果满足条件，则交换，交换到其最终应该出现的位置(比如将第n大的数交换到数组下标为N-n的位置)

void BubbleSort(int* a, int n)
{//n个元素排 n - 1 趟for (int j = 0; j < n - 1; j++) {int flag = 1;//flag用于标记数组是否已经有序// 单趟排序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 2 4 6
在一趟冒泡排序中始终满足 a [ i ] ≤ a [ i + 1 ] ，没有发生交换，说明它本身是有序的，所以无需排序了，直接退出。

1.3 特性及复杂度

冒泡排序的时间复杂度为O(N^2)，可能会感到疑惑，冒泡排序不是优化过了吗？为什么时间复杂度为 O(N^2)？

因为冒泡排序每次的比较次数，是随着趟数而减少的，找一下规律，其实可以发现，它的总执行次数是一个公差为 −1 的等差数列：(n - 1) + (n - 2) + … + 1 ，根据等差数列求和公式得：(n−1+1)×(n−1)2( n − 1 + 1 ) × ( n − 1 )\\over22(n−1+1)×(n−1)​ ，化简得 n22n^2\\over22n2​ − n2n\\over22n​，根据时间复杂度规律，最终为 O(N^2) 。

而我们的优化是只对 数组前半部分有序 或 整体几乎有序 才有优化作用，如果有序的部分在后半段，每趟排序还是要从头开始一一比较，相当于还是重新排序。

其实数组前半部分有序的优化程度也不大，最好情况是 优化后 在 整体有序 的情况下，遍历一遍数组，通过 break 退出，这时 最好时间复杂度为O(N) 。

综上，取最坏情况，时间复杂度为O(N^2)。

空间复杂度为 O(1) 。

冒泡排序虽然效率不高，但他有特殊的意义：教学意义(bushi)

特性：冒泡排序是一种非常容易理解的排序。
时间复杂度：O(N^2) 。
空间复杂度：O(1) 。
稳定性：稳定。

2、快速排序

2.1 算法思想

快速排序是Hoare 于1962年提出的一种二叉树结构的交换排序方法，其 基本思想 为任取待排序元素序列中的某元素作为基准值key，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

2.2 快排递归版本

快排为交换排序的一种。用更详细的方式来讲，快排在开始时，会选择一个 key 做基准值，并设定 给定，然后进行单趟排序，单趟排序后，当排序停止，会把 key 的索引或 key 值本身与边界某一值交换，形成区间划分。

这个区间划分通常为 key 左边的值都小于 key ，key 右边的值都大于 key ，这样就使得区间被划分了。中间的 key 值不用管，当前 key 值已经到了正确的位置。那么现在排序就变为：对左区间和右区间的排序。

那么每次排序后都会确定一个元素的位置，确定位置后继续划分区间…这样的过程实际上就是递归，通过递归，对设定的基准值分割开的左右区间完成排序。

递归的返回条件为begin >= end ，此刻说明区间只有 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);
}

上述为快速排序递归实现的主思路，我们可以发现与这个思路与二叉树前序遍历非常像，在写递归框架时可回想一下二叉树前序遍历规则，最后我们只要分析如何按照 基准值key 来对区间中数据进行划分即可。

而按照基准值划分区间的方法有三种，分别为 hoare 版本、挖坑法、双指针版本 ，接下来我们一一学习。

2.2.1 hoare 版本

hoare 大佬是快速排序发明者，但是在实现这个版本时很容易踩坑。

快速排序的单趟排序要达到的目的:
1.将数组中某个元素(key元素)交换到其在有序序列中最终应该出现的位置,即:
单趟排序结束后要保证key元素之前的元素都比key元素小
单趟排序结束后要保证key元素之后的元素都比key元素大
2.单趟排序接口返回key元素最后的位置下标(作为数组分割点)

先看动图：

hoare 版本的思路：
1.首先取左边界为基准值 key ，定义两个指针left、right 分别指向最左边和最右边的元素。
2.right 先走，如果right 指向的元素大于 key 指向的元素，则right−− ，如果指向元素小于 key 指向的元素，则停止；
3.停止之后，left 开始走，如果 left 指向的元素小于key 指向的元素，则left++ ，如果指向元素大于key 指向的元素，则停止；
4.当 left 和right 都停下后，交换left 和 right 位置的值。
5.直到left≥right ，循环停止。

上面过程就保证了 left 和 right 相遇的位置的值是小于key 的， 此刻交换 a[left]（或a[right]）和a[key] ，令key=left（或right） ，此刻左右区间就已经被划分好了，key 就是分割点。

规定:如果取左边作为key 就要保证左边比 key 小，右边比key 大；如果取右边作为key 则右边比 key 小，左边比key 大。

一些相关的问题 ：

问题1：为什么 left 和 right 相遇的位置是小于 key或直接就是key的位置(序列为升序) 的？是巧合还是必然？

这是必然的，接下来分析一下，一共有两种情况：

第一种是 right 停住，left 遇到right ，相遇位置就是right 停住的位置。
当前情况就是right 在走时，遇到比 a[key] 小的元素停住了，然后 left 走时，和right 位置是小于key 。

第二种是left 停止，right 遇到left ，相遇位置是 left 停住的位置。
left 和right 已经交换过一次元素，所以left 的位置必定小于key ，left 停住了，之后right 走，直到和left 相遇，相遇位置是小于key 的。

还有一种特殊情况，就是right 先走，右边的数字都比 a[key] 大，right−− ，right 一直走到与 left 重合，a[key] 和 a[left] 交换后不变。

否则，当key在左，L先走的时候，就会出现问题

问题2：开头说过hoare 大佬的版本很容易踩坑，坑在哪里？如何解决？

其实这里容易引起的错误还是很多的，比如：

1.左右两边都有和 key 相等的值，导致左右两边卡死。

举个例子：

例如这种情况，a[key]=6 ，右边先走时，由于 a[right]=a[key] ，不走；左边走时，由于 a[left]=a[key] ，也不走。这样就死循环了！

所以，我们一开始的思路是需要 改进 的，当a[right]≥a[key] 时，right−−；在 a [ left ] < = a[left]<=a[key] 时，left++。这样就解决了 死循环的问题 。

2.但是修好了这个 bug 另一个 bug 就冒出来了，一旦加上上面的条件，如果 key 右边的值都大于key ，且循环内部不加限制，right 就会一直 −− ，由于没有限制，right 就 停不下来了。

所以在 right 和left 每次走的时候需要加上限制 left<right 。

3.但还是存在问题，由于一开始的时候++left，导致最后交换的时候没有考虑到最开始keyi的值的比较

如何解决呢？去掉++left

由此，我们就可以写出代码：

// 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;
}

2.2.2 挖坑法

由于hoare 大佬版本存在的 “坑” 比较多，后面就有一些未留名的大佬在 hoare 版本的基础上，对快排做出了一些改良，比如我们的 挖坑法 。

优点：不需要左边作key，右边先走等要求，且排出来顺序一般与hoare的版本不一样

单趟排序算法实现思想:
1.选择arr[left]作为key(key变量存储key元素的值)
2.以初始left指向的位置作为初始坑位(坑位下标用hole变量来记录)
3.right指针向前遍历寻找比key小的数,找到后将right指向的元素赋值到坑位上,将right下标值赋给hole(更新坑位)
4.left指针向后遍历寻找比key大的数,找到后将left指向的元素赋值到坑位上,将left下标值赋给hole(更新坑位)
5.重复上述迭代过程直到left指针和right指针相遇

先看动图：

挖坑法的思路：
1.挖坑法多了一个hole ，也就是坑位。我们将 key = a[left] ，将 key 保存到一个临时变量中，假设 key 这个位置的值被挖掉了，形成一个坑位。此时 hole 就是坑位的下标。
2.依然是右边先走，循环条件为left<right 并且right 指向的元素大于等于key ，一旦 right 停下来，那么就把 a[hole]=a[right] ，把right 指向的值填到坑中，此刻right 作为新的坑。
3.而 right 之前的值也被转移到了别的地方，这个位置就被看做为空，变成坑。
4.左边则是相同的思路，同理左边停下后，让 a[hole]=a[left] ，让 left 作为新的坑。
5.直到left≥right 停止。
6.最后的hole 就是key 值该去的地方，把这个地方填上 key ，此刻 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;
}

2.2.3 前后指针版本

1962年Hoare大神运用双指针算法重新设计了交换排序的单趟排序,并运用分治递归实现代替了嵌套循环实现,完成了交换排序的终极优化

单趟排序算法实现思想:
1.选取arr[left]作为key(key变量作为下标指向key元素)
2.slow初值为left,fast指针从left+1位置开始遍历数组
3.若fast指针找到了比key小的元素,则令slow指针向后走一步,并交换slow和fast指针指向的元素
4.若fast指针找到了比key大的元素,slow指针不动,fast指针继续向后遍历数组
5.重复上述过程直到fast指针完成数组的遍历,最后再将key元素交换到slow最终指向的位置
6.最终从left位置到slow位置的所有元素就是整个数组中比key小的所有元素.

先看动图：

前后指针法的思路：
定义三个变量，prev=begin，cur=begin+1,key=begin，主要使用 cur 来遍历数组。
1.如果cur 指向的元素比key 小，此刻停下来，++prev ，交换调整后的prev 位置和 cur 位置的值，之后 cur++ 。
2.如果cur 指向的元素大于等于key ，cur++ ，其他啥也不干。
3.就这样循环往复，直到cur>end ，此刻交换prev 和 key 位置的值。
当前的 prev 作为新的key ，为分割点。

这里的 prev 和cur 有两种状况：
1.紧跟cur ，这时 a[cur]<a[key] ，它俩同步往后走
2.指向比 key 大的位置的前一个，pprev 和 cur 之间就是 ≥ a [ key ]个值。

每当 a[cur]<a[key] ，cur 位置小于a[key] 的值总是会被推到前面。循环的过程相当于是将小于a[key] 的值往前翻，大于 a[key] 的值往后像“翻跟头”一样推着走。

最后prev 的位置指向比 a[key] 大的位置的前一个，那么交换a[prev] 和 a[key] ，让key=prev ，此刻key 为分割点。

优化思路：
实际上我们发现当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)//a[cur] < a[key] 小才执行++prev，否则不++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;
}

2.3 缺陷分析及优化

缺陷1：有序或接近有序序列时间复杂度过高

其实对于快排来说，它的时间复杂度是不稳定的，比如上方三个版本，在乱序的序列中，效率可能还可以，因为选取的 key 值是随机的。

但是对于有序序列，比如要排正序(逆序)，但是序列是逆序(正序)。如果每次选 key 还是按照之前的选法，那么每次可能就会选中最边上的一个，选中最大或最小的数，假设序列长度为N ，每次选取一个极端值，就会选取 N 次，就会递归 N 层，每一层中的时间复杂度为 O ( N ) ，那么最终时间复杂度为O(N^2) 。且栈会溢出，递归 N 层，建立N个栈帧。

改进方法：
1.随机选K，会优化很多，但若刚好随机到最左边，所以不是很推荐

2.我们能否每次选 key 作为一段区间的中位数 ，让每段区间被二分，那么最终就只会递归 logN 层，每层时间复杂度为 O(N) ，总时间复杂度为O(N×logN) 。就像下图，像一棵二叉树一样。

所以这边就引申出了第一个优化：三数取中

所谓三数取中，就是不取最大，不取最小，在begin , end,(begin+end)/2 中选取一个中间值，尽量让key 可以命中每段区间中点。

代码：

int GetMidNum(int* a, int begin, int end)
{int mid = (begin + end) >> 1;//   /2if (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 个数，那么这种情况采用递归是不是浪费空间，是不是多此一举？

所以当 end−begin+1<10 时，可以采用插入排序优化，这样子就不用开太多层函数栈帧。

对于一棵满二叉树，最后一层的节点数占总结点数的 121\\over221​ ，倒数第二、三层分别为141\\over441​ 、181\\over881​ ，我们就假定快排递归展开后，最后形态为完全二叉树。

假设当前有10个节点，那么对于下图中红色箭头标出的点来说就无须递归，因为再细分也就是一个数：

大约可以节省下三层的递归，下三层的节点数占总结点数的 87.5 % ，省去了大部分的递归

所以这边就引申出了 第二个优化：小区间优化

但区间不能太大，不然也没有意义了，建议end−begin+1< 10左右

void QuickSort(int* a, int begin, int end)
{if (begin >= end){return;}// 小于一定数目使用 直接插入排序if ((end - begin + 1) < 10){// 数组位置：a + begin  ,  直接写a就始终是前几个数// 元素个数：end - beghin + 1InsertSort(a + begin, end - begin + 1);}else{int key = partion3(a, begin, end);// 递归左右区间QuickSort(a, begin, key - 1);QuickSort(a, key + 1, end);}
}

缺陷3：对于相同数据来说，三数取中无效，时间复杂度过高

像 2 2 2 2 2 2 2 2 这个序列来说三数取中是完全无效的，特别数据量一大，不仅容易超时，还容易栈溢出。

这就引申出了第三个优化：三路划分。

之前我们是主要将区间划分为两段，[begin,key−1] 和[key+1,end] 。 左区间值小于key ，右区间值大于key ，可以称为 两路划分 。

现在我们需要进行三路划分，就是将区间分割为左区间小于key ，中间区间等于 key ，右区间大于 key 。

思路：
1.设定一个 cur=begin+1，left = begin, right = end, key = a[left]，将区间分割为左区间小于key ，中间区间等于 key ，右区间大于key 。
2.给定一个循环，循环中如果a[cur]<key ，此刻交换 cur 和left 指向的元素，使 left++ ，cur++ (如果一开始这个条件就满足，则会把 key 逐渐往中间推)
3.如果a[cur]>key ，此刻right 这个位置的值比 key 大，也有可能比 key 小。交换cur 和right 指向元素后，若cur++可能该位置元素就不满足最终区间划分条件，所以这里只能right−−.
4.如果a[cur]==key ，那么只需要 cur++。
5.当cur>right 时，right 后的元素都是大于key 的，区间也都调整好了，这时候循环也就停止了。

实际上这一过程就像把和 key 相等的值往中间推，把比 key小的值往左边推，把比 key 大的值往右边推，最后等于key 的就在中间。

最后分割成的区间就是[begin,left−1],[left,right],[right+1,end]，这时等于 key 的区间不用递归，只需要递归排序左右区间即可。

代码：

// 三路划分 处理重复数据量大的情况，处理完中间区间就是 22222222222
void QuickSortT(int* a, int begin, int end)
{if (begin >= end){return;}// 三数取中一下int mid = GetMidNum(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);
}

2.4 快排递归版本完整代码

这边调用的 partion3 是 前后指针版 的代码：

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);}
}

2.5 快排非递归版本

由于递归版本存在缺陷：
1.效率
2.深度太深，会栈溢出

所以我们要具备一个能力：把递归改成非递归
1.直接该成循环。eg.斐波那契数
2.使用栈辅助改循环

非递归的好处就是不需要多次递归开辟多层函数栈帧，在空间消耗上略有优势。
快排的非递归需要借助数据结构 - 栈 来完成。

快排递归的过程相当于对每一段区间进行处理，那非递归可以用两个变量来模拟各个区间

思路：
1.开始，我们将 begin 和 end 分别入栈。给定一个循环，如果栈不为空就继续循环。
2.由于栈是后进先出，所以先用right 接收end 右区间，再用 left 接收左区间，在接收完之后，将这两个元素分别出栈。
3.得到了区间后，对区间进行单趟排序(可以调用上面的 hoare 等)，用 key 接收分隔点。
4先处理左区间[left,key−1] ，再处理 [key+1,right] 。由于栈先进后出，所以要先入右区间，在入左区间。
5.每次循环只会取出两个值，那么就是一小段区间，在取出左区间后，会先处理左区间，然后不断分割小区间，每次取出两个值一直对栈顶上的两个元素的区间进行处理，这样就模拟了快排的过程。

优化思路：
如果区间内只有 1 个元素，就无需处理了，所以可以加个条件判断一下，举个例子，对于右区间来说， key 是分割点， key+1 则是右区间的起始位置，如果key+1<right ，那么说明区间中不止一个元素，这种情况就入栈处理。类比左边也是一样的道理。

// 快排非递归
void QuickSortNorR(int* a, int begin, int end)
{ST st;StackInit(&st);// 压栈StackPush(&st, begin);StackPush(&st, end);while (!StackEmpty(&st)){// 后进先出，先出 rightint right = StackTop(&st);StackPop(&st);int left = StackTop(&st);StackPop(&st);//单趟排 int key = partion3(a, left , right);//[left,key−1] key [key+1,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);
}

2.6 特性及复杂度

对于快排的时间复杂度，本来是不太稳定的，因为处理有序序列或者序列中元素相同的情况下，可能会造成O(N^2) 的时间复杂度。

但是当我们使用 三数取中 或者 三路划分 后，时间复杂度就相对稳定了。
加上这两个功能之后，如果画出每层的元素情况，就像下图一样，像一棵完全二叉树。
由于每次每一块都是被二分，一共 N 个节点，所以这边大约就是logN 层。

对于递归的版本，需要开 logN 层栈帧；对于非递归的版本，原理和递归类似，也认为处理logN 次。每次单趟递归处理中，时间复杂度为 O(N) 。所以快排的时间复杂度为O(N*logN)

空间复杂度也因为优化的原因，几乎不会出现极端情况，我们认为最佳情况就是像二叉树一样，最多开辟logN 层栈帧

递归版本空间复杂度的计算公式：递归深度×每次递归中额外空间消耗，每次递归消耗空间为O(1) ，一共 logN 层，所以空间复杂度为 O(logN) ，非递归同理

特性：快速排序整体的综合性能和使用场景都是比较好的，故称快速排序。
时间复杂度：O(N*logN) 。快速排序的过程类似于高度为 logN 的二叉树，且每层约有 N
空间复杂度：O(logN) 。
稳定性：不稳定。

3.总结：

今天我们认识并具体学习了交换排序算法中的冒泡排序和快速排序，通过这次的学习，我们也感受到了快速排序的魅力。下一篇博客，我们将继续学习排序算法中的归并排序。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~