交换排序——冒泡排序 和 快速排序
- 一、冒泡排序
- 二、快速排序
- 2.1 不同版本的快速排序
- <1>霍尔版本
- **1> 开闭区间**
- **2> key 的取值**
- **3> 单次循环的筛选条件**
- **4> 为什么要先右边后左边**
- **5> 递归停止条件**
- <2>挖坑版本
- <3>前后指针版本
- 2.2 快速排序的优化
- <1> 三数取中
- <2> 小区间优化
- <3> 三路划分
- 三、总结
一、冒泡排序
冒泡排序是我们初学 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;
}
我们加上小区间优化后,也排一千万个数
这个优化也很多了,除了最后一次可能重复的数太多导致有点慢
<3> 三路划分
上面那些代码对于 key 相同的数我们采取的是不处理
不管他们是在左边还是右边
若是重复的数少还好
但如果重复的数据多时就会影响效率
int a1[] = { 2,3,2,2,3,2,2,3 };
int a2[] = { 6,6,6,6,6,7,8,9,6};
如果我们极端一些,整个数组都是相同的数
int a3[] = { 2,2,2,2,2,2,2,2 };
以前后指针法为例
当遇见相同的数时
pcur 就会一直向后走
直到遇到 right 时就停止
如上面动图,如果重复的数很多
每次递归时传递的左右区间
会出现左边没有,右边是原区间减一
效率很低
就比如我们统计我国人民的年龄
并进行排序时
十三亿人几乎都在 0 - 100 岁区间
那如果还按照上面那样排就很慢
所以我们用三路划分的方法
所谓三路划分就是将数据分为
比 key 小,与 key 相等,比 key 大三个区间
具体操作先看下面动图:
来说一下这个排序的过程
begin = left
end = right
cur = left + 1
当 cur 的数比 keyi 小时
将 cur 与 begin 交换,cur++ , begin++
当 cur 的数比 keyi 大时
将 cur 与 begin 交换,end - -
当 cur 与 keyi 相等时
cur++
当 cur > end 时结束
代码如下:
//快速排序(三路划分)
void QuickSort3(int* a, int left, int right)
{//判断递归条件if (left > right){return;}/*int key = left;*///先确定 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;}//保存 key 的值int keyi = a[key];//保存区间int begin = left;int end = right;int cur = left + 1;//单次排序while (cur <= end){if (a[cur] < keyi){Swap(&a[cur], &a[begin]);cur++;begin++;}else if(a[cur] > keyi){Swap(&a[cur], &a[end]);end--;}else{cur++;}}//将剩余部分一分为二,进行递归//[left, begin - 1] [begin, end] [end + 1, right]QuickSort3(a, left, begin - 1);QuickSort3(a, end + 1, right);
}
但这样排序在重复数不多时效率会低一些
下面是我们生成随机数的方式
rand 生成的随机数是有限的
所以会生成一些重复的数
当我们将 rand + i 就可以降低重复数的量
我们同样生成一千万个数
(1)重复数多时,有三路划分和无三路划分
(1)重复数不多多时,有三路划分和无三路划分
可以看到当重复数据多时,三路划分的方法是很快的
但是当重复数据不多时,三路划分就慢了很多
所以在不同的情况,我们要用不同的方法
三、总结
其实经过学习,快速排序其实在发明之初并不是最快的
但是经过多轮改进快速排序已经被存在了 c 语言库中
就是 qsort 这是 c 语言库中的快排
对于快排人们进行了很多研究
当我们要递归的深度过深时
我们可以用自己实现的栈来模拟栈中递归
【数据结构】快速排序——非递归实现快速排序
当然在 c 语言的函数库中不可能搞非递归的方式
于是有人研究出了自省排序
那什么是自省排序呢?
就是它会检查函数递归的深度
当递归的深度到一定程度时,就会转变为别的排序
如堆排,希尔排序
因为假如我们遇到数组中重复数据较多时
上面动图也模拟了
递归会变成一边没有或者很少,一边很多的情况
那么这时我们就将程序转变为堆排,或者希尔排序
当然肯定不如三路划分
但是重在稳定,打造六边形战士,哪种情况都不会很慢