【数据结构】交换排序——冒泡排序 和 快速排序
交换排序——冒泡排序 和 快速排序
一、冒泡排序
冒泡排序是我们初学 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 语言库中的快排
我讲的那两个优化比较简单
所以这里挖个坑
对于快速排序对重复数据较多的数据排序方法
三路划分
以及防止栈溢出，非递归解决方法
栈模拟递归
这些我后面会陆续发出来的
因为要是一起就篇幅太大了
原文地址：https://blog.csdn.net/2302_79968411/article/details/143607245
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！