【数据结构】交换排序——冒泡排序 和 快速排序

一、冒泡排序

冒泡排序是我们初学 c 语言绕不开的排序
假设我们要排一个升序的数组
冒泡排序的原理是
前一个数与后一个数比较
将大的数与小的数交换
然后再往后面进行比较，遍历整个数组

动图演示：

代码整体：

//冒泡排序
void BubbleSort(int* a, int n)
{for (int j = n - 1; j > 0; j--){//单次排序for (int i = 0; i < j; i++){if (a[i] > a[i + 1]){Swap(&a[i], &a[i + 1]);}}}
}

冒泡排序的最坏情况
整个数组为降序
时间复杂度：O(N ^ 2)

冒泡排序的最好情况
整个数组为升序
时间复杂度：O(N)

二、快速排序

2.1 不同版本的快速排序

<1>霍尔版本

先看下面的动图：

目标：
选取一个值做 key
key 的左边为比 key 小的数
key 的右边为比 key 大的数

实现：

让右边先走，右边找小
再让左边走，左边找大
再让左右两边进行交换

当左右两边相遇时
将 key 插入到左右两边相遇的位置

下面是代码：

开区间：

//快速排序1(霍尔版本)
void hQuickSort1(int* a, int left, int right)
{//判断递归条件if (left > (right - 1)){return;}//先确定 key 的值int key = left;//进行单次循环int begin = left;int end = right - 1;while (begin < end){//让右边先找小while (begin < end && a[end] >= a[key]){end--;}//左边找大while (begin < end && a[begin] <= a[key]){begin++;}//将 begin 和 end 进行交换Swap(&a[begin], &a[end]);}//将 key 位置的数与两数相遇位置的数交换Swap(&a[key], &a[begin]);key = begin;//将剩余部分一分为二，进行递归//[left, key) key [key + 1, right)hQuickSort1(a, left, key);hQuickSort1(a, key + 1, right);
}

闭区间：

//快速排序2(霍尔版本)
void hQuickSort2(int* a, int left, int right)
{//判断递归条件if (left > right){return;}//先确定 key 的位置int key = left;//进行单次循环int begin = left;int end = right;while (begin < end){//让右边先找小while (begin < end && a[end] >= a[key]){end--;}//左边找大while (begin < end && a[begin] <= a[key]){begin++;}//将 begin 和 end 进行交换Swap(&a[begin], &a[end]);}//将 key 位置的数与两数相遇位置的数交换Swap(&a[key], &a[begin]);key = begin;//将剩余部分一分为二，进行递归//[left, key - 1] key [key + 1, right]hQuickSort2(a, left, key - 1);hQuickSort2(a, key + 1, right);
}

1> 开闭区间

这里面开闭区间的意思是，我们输入端输入时候的数据是开区间还是闭区间

size 的值是数组元素的个数
因为数组下标是从 0 开始的
当 right = size - 1 时就是闭区间
当 right = size 时就是开区间
所以我们输入端是开区间还是闭区间就是影响递归时的区间取值
为了后面的代码方便我都将取闭区间

2> key 的取值

在这里我们的 key 取值可以是第一个，也可以是最后一个
但是最后都要移到第一个的位置
key的取值最好是整个数组数字的中间值
这样数组的时间复杂度就是完美的 O(N * logN)
所以 key 的取值可以优化，后面会讲到
后面的方法都是先默认取第一个

3> 单次循环的筛选条件

先说 >=
这样取的目的是跳过与 a[key] 相同的值
因为我们的目的是将数组分为两部分
左边是比 a[key] 小的数
右边是比 a[key] 大的数

但是这样就会造成相同的数它的顺序改变了
那数字 6 举例
就是前面的 6 可能会因为我们最后一步插入
而插入到原先在它后面 6 的后面

我们说这样的排序是不稳定的

再说 begin < end
如果不加上这个条件
就是造成最后 begin 的位置会向后移一位
因为我们是右边先走
当右边停下时就是比 a[key] 小的数
而左边停下条件时找比 a[key] 大的数
所以 begin 还会向后一位

4> 为什么要先右边后左边

先从右边能保证每次都是右边先找到整个数组小值
然后再左边找大值
若找到了就交换
若没找到就会和右边相遇停止循环
保证每次停止的位置都比 a[key] 小

那我们要想排一个降序数组
我们就可以左边先走找大值，右边再走找小值
或者右边先走找小值，左边再走找大值
这个是很灵活的

5> 递归停止条件

为什么不是 == ，而是 >

假设递归到这种程度
此时 key = 1
那么递归后 left = 2 而 right = 1

<2>挖坑版本

先看下面动图：

挖坑法顾名思义
我们先将 key 位置的数作为一个坑位
右边先走遇到比 keyi 小的就入坑
然后右边就形成了新的坑位
然后左边再走，找比 keyi 大的入坑
如此往复当左边与右边相遇时就将 keyi 入坑

当然在代码实现过程不会真的挖空，会将值直接覆盖``
代码如下：

//快速排序3(挖坑版本)
void wQuickSort(int* a, int left, int right)
{//判断递归条件if (left > right){return;}//确定 key 位置int key = left;//进行单次排序int begin = left;int end = right;//将 key 位置数保存起来//将 key 位置先当作一个坑位int keyi = a[key];while (begin < end){//右边找小，找到小的填到坑位中while (begin < end && a[end] >= keyi){end--;}a[begin] = a[end];//左边找大，找到大的值填到坑位中while (begin < end && a[begin] <= keyi){begin++;}a[end] = a[begin];}//将 keyi 值填入坑位中a[begin] = keyi;key = begin;//将剩余位置进行递归//[left, key - 1] key [key + 1, right]wQuickSort(a, left, key - 1);wQuickSort(a, key + 1, right);
}

与上面霍尔方法有很多相同，而且效率也一样
这个方法是后来人根据霍尔的方法改进来的
但是这个方法的优点是不容易出错
好实现没有那么多弯弯绕绕

<3>前后指针版本

这个方法有点不好理解
这个方法的运行原理：
在初始化时 pcur 是 prev 的前面一个
然后进行判断若 pcur 下是比 key 小的数
就将 prev++
并且将 pcur++
再将 prev 与 pcur 交换
当相等时我们可以设定条件不让两者交换
然后当 pcur 下是比 key 大的值
将 pcur++
最后当 pcur 超出数组大小时
将 key 与 prev 进行交换

代码实现：

//快速排序4(前后指针版本)
void pQuickSort(int* a, int left, int right)
{//判断递归条件if (left > right){return;}//确定key的位置int key = left;//进行单次排序int prev = left;int pcur = prev + 1;//保存 key 的值int keyi = a[key];while (pcur <= right){if (a[pcur] < a[key] && ++prev != pcur)Swap(&a[pcur], &a[prev]);pcur++;}//将 key 位置的数与两数相遇位置的数交换Swap(&a[key], &a[prev]);key = prev;//将剩余部分一分为二，进行递归//[left, key - 1] key [key + 1, right]pQuickSort(a, left, key - 1);pQuickSort(a, key + 1, right);
}

这个方法也是后人从霍尔那边改进的
优点是代码简洁，代码量少
但其实时间复杂度一样

2.2 快速排序的优化

<1> 三数取中

我们假设一种情况
原数组已经是升序排列好的数组
那每次递归的左边都不存在，右边为剩下的数
这种情况比较极端
但这时的时间复杂度就到惊人的 O(N ^ 2)

当然这种情况就不可能有
更多的情况是我们取到的是数组中较大的数或者较小的数
这时 key 的位置并不是靠近中间
递归时就会降低效率

这是我们可以采用三数取中的方式
我们将左右下标的数与数组中间的数进行比较
我们选出那个中间值
这样可以尽可能避免取到极端值的机率
当然也有可能正好三个都为最大值，那就没办法
但这种机率很小

三数取中的目的就是将取到极端值的概率降低

代码如下：

int The_Mid(int* a, int left, int right)
{int mid = (right + left) / 2;if (a[left] < a[mid]){if (a[left] > a[right]){return left;}else if (a[mid] < a[right]){return mid;}else{return right;}}if (a[left] > a[mid]){if (a[mid] > a[right]){return mid;}else if (a[right] > a[left]){return right;}else{return left;}}
}

我们同时处理一千万个数进行比较：


可以看到优化还是相当明显的

<2> 小区间优化

我们这个快速排序时需要递归的
递归是要在栈开辟空间的
而递归深度太深有栈溢出的风险

而且如果只有几个数就要递归好几次实在是有些不值当
所以我们可以加入别的排序
在递归到只有几个数的时候就切换，提高效率

选择的是直接插入排序
直接插入排序讲解

//先确定 key 的位置
int key = The_Mid(a, left, right);
Swap(&a[key], &a[left]);
key = left;//小区间优化
if ((right - left + 1) < 10)
{//插入排序InsertSort(a + left, (right - left + 1));return;
}

我们加上小区间优化后，也排一千万个数

这个优化也很多了，除了最后一次可能重复的数太多导致有点慢

三、总结

其实经过学习，快速排序其实在发明之初并不是最快的
但是经过多轮改进快速排序已经被存在了 c 语言库中
就是 qsort 这是 c 语言库中的快排
我讲的那两个优化比较简单

所以这里挖个坑
对于快速排序对重复数据较多的数据排序方法
三路划分
以及防止栈溢出，非递归解决方法
栈模拟递归
这些我后面会陆续发出来的
因为要是一起就篇幅太大了