【初阶数据结构与算法】八大排序算法之交换排序（冒泡排序，快速排序---hoare、挖坑法、lomuto双指针3种版本）
文章目录
- 一、冒泡排序
- 二、快速排序简介及其大致框架
- 三、快排hoare版本子函数
- 四、快排挖坑法子函数
- 五、快排lomuto双指针子函数
- 六、冒泡排序与快排的性能分析与比较
一、冒泡排序
冒泡排序的命名是因为它的排序操作就像水平面在冒泡一样，当我们讲完冒泡排序就知道为什么这么说了，接着我们来一起学习一下冒泡排序
冒泡排序的基本思路很简单，就是模拟冒泡的过程，如果我们要排升序，就把当前待排序的元素中，把最大的那个元素看成泡，数组的最后看做水平面，我们通过一趟冒泡排序就要将泡 “冒” 出来，其实就是让最大的那个元素放在数组的最后
如果我们要排降序，就把最小的那个元素看做泡，数组的最后看做水平面，把它 “冒” 出来，也就是把最小的那个元素放在数组的最后，无论是排升序还是排降序，都是不断地把这些特殊的泡泡冒出水面
那么我们如何将泡泡冒出水面呢？其实就是如何把最大或最小的那个元素放到数组最后，在直接选择排序中的策略是，遍历当前的有效元素，找出最大的值的下标，然后和数组有效元素的最后一个元素交换
它的核心思想在于“选择”，而冒泡排序属于交换排序的一种，它的实现是基于元素之间的交换的，具体方法就是：
遍历当前有效的元素，比较当前元素和后一个元素的大小，将大的元素往后挪动，这样遍历完所有有效元素后，最大的那个元素自然就在数组中的最后了，我们画图理解理解，如下：
上图演示的就是一趟冒泡排序，可以将最大或最小的 “泡” 冒出水面，那么我们再多执行几趟冒泡排序是不是就可以将数组排成有序了，那么到底需要几趟这样的排序呢？
由于每趟冒泡排序可以排好一个数，所以排好所有数需要执行n次，但是可以再优化一点点，因为如果我们把n - 1个数排好了，那么第n个数一定会出现在它该在的位置上，所以只需要执行n - 1趟上图的冒泡排序即可
当然，我们还可以再优化一下，因为有可能整个数组已经在某一趟冒泡排序中排好了，那么后面的比较也就没有必要了，具体优化方法我在代码中进行注释讲解，那么有了大致思路，我们就直接上手写代码，如下：
void Swap(int* x, int* y)
{
int tmp = *x;
*x = *y;
*y = tmp;
}
//冒泡排序
void BubbleSort(int* arr, int n)
{
//一共进行n-1趟冒泡排序
for (int i = 0; i < n - 1; i++)
{
//创建一个标志flag，如果在一趟冒泡排序中发生了交换
//那么就改变标志的值，不退出循环
//如果在一趟中没有发生交换，那么就直接退出循环
int flag = 1;
//一趟冒泡排序的逻辑
for (int j = 0; j < n - i - 1; j++)
{
//如果当前元素大于后面的元素，直接交换，并且修改flag的值
if (arr[j] > arr[j + 1])
{
Swap(&arr[j], &arr[j + 1]);
flag = 0;
}
}
//如果没有发生交换flag = 1，退出循环
//发生了交换flag = 0，不会跳出循环
if (flag)
break;
}
}
我们来使用一下冒泡排序，如下：
可以看到冒泡排序很好地完成了排序任务，接下来我们来分析一下它的时间复杂度，套了两层for循环，在最坏情况下，其时间复杂度达到了O(N^2)，悄悄说一句，冒泡排序可以说是八大排序算法中最慢的，具体原因我们后面分析
二、快速排序简介及其大致框架
快速排序是Hoare于1962年提出的⼀种⼆叉树结构的交换排序⽅法，其基本思想为：任取待排序元素序列中的某元素作为基准值，按照该排序码将待排序集合分割成两⼦序列，左⼦序列中所有元素均⼩于基准值，右⼦序列中所有元素均⼤于基准值，然后最左右⼦序列重复该过程，直到所有元素都排列在相应位置上为⽌
大致含义就是，快排的主要思路就是将一个数组按照给定的基准值不断分成两截，然后对它们进行处理，将所有小于基准值的放在在基准值的左边，大于基准值的放在基准值的右边，最好的情况下可以二分进行排序，非常高效
当然，快排在一些特定场景下速度很慢，如数组本来就有序，数组中有大量重复数据，我们后面讲解为什么，以及如何解决
首先第一个问题，这个基准值怎么找呢？这里我们初始快排，主要掌握快排的方法以及它的思路，所以我们就直接选择当前序列中最左边的那个元素作为基准值
那么如何将数组进行划分呢？我们采用的方式就是递归，当然也有非递归版本的快排，那样要难一点，我们先掌握递归版本的快排，后面再来学习非递归版的快排
那么递归什么呢？有点类似于二叉树的前序遍历，我们先对整个数组进行划分，划分方法有多种，我们重点讲3种，现在我们首先要知道这个函数能做什么
具体需求就是，将我们传过去的数组的序列按照基准值划分(基准值就是序列中最左边的元素)，比基准值小的放在基准值左边，比基准值大的放在基准值右边，然后返回调整后的基准值的下标
然后我们根据划分的新的基准值下标，将数组的序列划分成左右分别进行递归，看起来非常类似于二叉树的前序遍历，我们简单画图演示一下：
如上图的操作就像二叉树的前序遍历一样，先对根进行处理，然后对左右进行处理，它的代码也很像二叉树的前序遍历，我们按照上面的思路写出快排的大致框架：
//快速排序
void QuickSort(int* arr, int left, int right)
{
//如果最左边的下标都和右边相等了，说明中间只有一个元素了
//如果左边大于右边，说明中间没有元素了，两种情况都需要直接返回
if (left >= right)
{
return;
}
//接下来就是一个快排的子函数，我们后面会具体讲，我们现在只需要了解作用
//它的作用就是帮我们对给出数组的指定序列进行调整
//调整为：小于基准值的放在基准值的左边，大于基准值的放在基准值右边
//然后将调整后的基准值的下标返回，方便继续对左右进行划分
//这里也可以看成二叉树前序遍历中的“根”的处理
int keyi = _QuickSort1(arr, left, right);
//通过划分好的基准值下标，继续划分成左右两个序列进行递归
//这里就类似于二叉树前序遍历的“左右孩子”的处理
//左序列：[left, keyi - 1], 右序列: [left, keyi + 1]
QuickSort(arr, left, keyi - 1);
QuickSort(arr, keyi + 1, right);
}
在上面的快排大致框架中，我们可以看到快排的参数其实比较特殊，它不是传元素个数，而是传需要排序的序列的下标范围，因为这样才方便递归，当然，也可以想办法弄成传元素个数，只需要再封装一层，这里就不展开说了，可以自己试试
在上面我们主要了解了快排的框架以及排序模式，是类似于二叉树递归的方式，这样可以大大的减少排序所需的时间，我们后面再具体分析
接下来我们就开始学习快排的子函数，一共三个版本，作用都是对给出的序列进行调整，将基准值放到对应的位置，返回调整后基准值的下标，一起来看看吧
三、快排hoare版本子函数
快排由hoare首先提出，他的划分思路非常经典，所以我们首先来学习hoare版本的快排子函数，我们先来说说它的基本思路
hoare版本主要思路就是，将left，也就是最左边的元素定义为基准值，然后从左边第二个位置开始循环的找小于基准值的值，从右边开始循环地找大于基准值的值，最后将它们进行交换
这样循环一次就可以让一个小于基准值的数放在左边，让大于基准值的数放在右边，我们画图演示一下：
如上图，只要循环地进行上面的操作，我们一定可以将小于基准值的元素放在左边，大于基准值的元素放在右边，最后总体的循环结束后，right的位置就是我们基准值的位置，我们交换right位置和keyi位置的值，如图：
此时我们惊讶地发现，right指向的值变成基准值之后，小于基准值的元素在基准值左边，大于基准值的元素在基准值右边，当然这里没有涉及和基准值相等的元素，有的话也不需要管，等于基准值的元素在左边还是在右边并不重要
那么上面就是关于hoare版本的快排子函数的思路，现在有了思路我们就来试着写出它的代码，如下：
//hoare版本
int _QuickSort1(int* arr, int left, int right)
{
//将默认left位置的元素当作基准值，同时left往后走一步
int keyi = left++;
//只要left不大于right就进入循环
while (left <= right)
{
//在保证不越界的情况下，从左往右找大于基准值的元素
//如果小于等于基准值就让left++
while (left <= right && arr[left] <= arr[keyi])
{
left++;
}
//在保证不越界的情况下，从右往左找小于基准值的元素
//如果大于等于基准值就让right--
while (left <= right && arr[right] >= arr[keyi])
{
right--;
}
//到了这个位置，如果left和right没有越界，并且不相等
//因为如果left == right，它们指向同一个元素，就无需交换
//把left指向的大元素和right指向的小元素交换
//这样大元素就到右边去了，小元素就到左边去了
if (left < right)
{
Swap(&arr[left++], &arr[right--]);
}
}
//循环结束后就把keyi和right位置的元素交换
Swap(&arr[keyi], &arr[right]);
//由于right指向的就是调整后的基准值，直接返回即可
return right;
}
接着我们就使用这个版本的快排来排序试试，如图：
可以看到我们的代码没有问题，那么接下来在进入挖坑法的学习前，给大家留下几个问题，我们在挖坑法进行解答：
- 外层循环能不能使用left < right？
- 循环里面的判断 arr[left] <= arr[keyi] 能否替换为arr[left] < arr[keyi]
- left能否不在最开始往后挪动一步？
四、快排挖坑法子函数
挖坑法是三个方法中最抽象的，也是最容易和hoare版本混在一起的方法，但是我已经将所有它们的对比列了出来，以及挖坑法的巧记小故事，学完库库明白，想搞混都难，接下来我们先来介绍一下它的基本思路
它的思路就是，把最开始left的位置的值当作基准值记录下来，然后把它看作坑hole，用右边小于基准值的元素来填，然后再把右边那个元素的位置当作坑，从左边找大于基准值的元素来填，循环结束后hole这个位置就是我们基准值要放的位置
可能听起来很懵，我们来画图演示一下就知道了，如图：
可以看到挖坑法帮我们完成了任务，但是这个方法特别不好记，所以我编了个巧记小故事方便记忆，希望可以帮到大家，如下：
里面红色的字是故事的主体，绿色的字是相应的说明，相信大家看了之后对挖坑法应该有更好的理解了，更方便计了，那么有了相应的思路，我们就开始写代码：
//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
//最开始在左边有一个小坑
int hole = left, key = arr[left];
while (left < right)
{
//坑在左边，是一个小坑，所以从后往前找小石头来填这个小坑
while (left < right && arr[right] >= key)
{
right--;
}
//找到后进行填坑，但是要注意，我们把它拿来填坑后
//right位置上的石头被搬走了，right就是新的坑
arr[hole] = arr[right];
hole = right;
//现在坑在原本right位置上，也就是它是一个大坑
//从左往右找大石头来填这个大坑
while (left < right && arr[left] <= key)
{
left++;
}
//填坑之后不要忘了，把left位置的元素拿去填坑后
//left位置就空了，left就是新的坑
arr[hole] = arr[left];
hole = left;
}
//到最后hole的位置就可以存放基准值key，返回hole即可
arr[hole] = key;
return hole;
}
相信大家现在还是有很多疑问，例如循环的判断条件为什么是left < right，里面的判断是否必须写成arr[left] <= key，为什么left初始情况下不往前走一步，我罗列了所有这些问题，花了一个多小时总结出来，不用担心
但是我们现在先来运行一下代码，看看这个方法是否真的可行，如下：
可以看到挖坑法没有问题，可以正常排序，当然，一定要记得把子函数改成挖坑法的，否则就跟没有测试一样
那么接下来就是重头戏，挖坑法和hoare版本太像了，只是它们的判断方式以及一些细节方面不同，关键是我们要知道为什么不同，我已经为大家总结好了，看这一篇就够了，如图：
好了，以上就是挖坑法和hoare版本的区别，以及为什么有这些区别，全部都讲清楚了，如果还有不懂的欢迎私信询问
五、快排lomuto双指针子函数
lomuto双指针是三个子函数中最简单的，它就类似于我们在顺序表刷题中使用双指针算法的一道题，具体思路就是创建两个下标指针cur和dest
cur在前面探路，找到小于基准值的元素就和dest后面一个位置的元素进行交换，然后它们同时往后走一步，如果cur没有遇到小于基准值的元素就一直往前走，我们画个图演示一下：
可以看到上图已经很好地模拟了lomuto双指针的运行方式，再加上我们之前顺序表又做过类似的题，所以这里我们直接就可以上手写代码了，但是其实上面的思路可以优化一点点，我在代码中的注释进行说明，如下：
//lomuto双指针
int _QuickSort3(int* arr, int left, int right)
{
//定义基准值以及cur和dest
int keyi = left;
int dest = left, cur = left + 1;
while (cur <= right)
{
//如果cur位置的值小于基准值，要和dest后面的元素进行交换
//但是有可能dest后面就是cur，所以我们可以让dest先++，再和cur比较
//如果++dest == cur，说明它们暂时指向同一个元素，无需交换
//如果++dest != cur，说明它们不指向同一个元素，直接交换
if (arr[cur] < arr[keyi] && ++dest != cur)
{
Swap(&arr[cur], &arr[dest]);
}
//无论cur位置的值是否小于基准值，cur都要++，所以留到这里做调整
cur++;
}
//交换dest和keyi位置的值，返回dest即可
Swap(&arr[keyi], &arr[dest]);
return dest;
}
我们来看看代码运行结果，注意记得将我们的子函数换成lomuto双指针的方法，以免测试无效，如图：
最后我们再统一分析一下快排的时间复杂度，首先递归时会对数组进行分段排序，所以时间复杂度为O(log N)，同时再加上子函数中的调整，时间复杂度为O(N)，所以总体下来，快排的时间复杂度大致为O(lN * log N)，属于最快的排序算法之一
六、冒泡排序与快排的性能分析与比较
冒泡排序的时间复杂度大致为O(N^2)，而快排则是O(lN * log N)，所以老规矩，我们造一个测试函数对快排和冒泡排序在同一电脑上进行测试，快排我们就选择最经典的hoare版本，如下：
void TestOP()
{
srand((unsigned int)time(NULL));
const int N = 100000;
int* a1 = (int*)malloc(sizeof(int) * N);
int* a2 = (int*)malloc(sizeof(int) * N);
for (int i = 0; i < N; ++i)
{
a1[i] = rand();
a2[i] = a1[i];
}
int begin1 = clock();
BubbleSort(a1, N);
int end1 = clock();
int begin2 = clock();
QuickSort(a2, 0, N - 1);
int end2 = clock();
printf("BubbleSort:%d\n", end1 - begin1);
printf("QuickSort:%d\n", end2 - begin2);
free(a1);
free(a2);
}
int main()
{
TestOP();
return 0;
}
接着我们来运行一下代码，注意要把模式调为Release，这样才能测试出它们的真实性能，如下：
可以看到10万个随机数，快排4毫秒就排完了，而冒泡排序用了将近9秒，比之前讲过的所有排序方法都慢，而快排则是之前讲过的排序算法中最快之一了
那么今天关于交换排序的讲解就到这里结束了，如果有什么疑问欢迎私信我， 我们后面接着学习排序算法，感谢观看！
bye~