当前位置:网站首页>【c语言】快速排序的三种实现以及优化细节
【c语言】快速排序的三种实现以及优化细节
2022-07-05 19:53:00 【柒海啦】
目录
前言
hello~欢迎你能够点进我的文章(*^▽^*)
这里针对快速排序,要实现其递归版本:hoare版本(最开始的)、 挖坑版本、前后指针版本,然后就是针对于其中的问题进行的一些优化。最后有非递归版本的实现。
一、hoare版本
1.思想
首先,这是一开始的快速排序版本。
同样,我们首先针对一个数进行排序,排序好后排两边的。这就利用了分治的思想,即递归版本。
然后我们针对每一轮,它首先确定最左边的为目标值,定为key,下标为keyi,定义一个储存左边的变量left(在目标值的往前一格),储存右边的变量right 我们针对升序排法,所以右边找小,左边找大(如果定义最右边的就刚好相反,右边边找小,左边找大,看个人喜好)
然后,我们需要找小的先走(right),找到小的或者遇到left停下,然后left在往右移动,找到大的停下或者遇到right停下。如果两者相遇即前述任意哪种遇到left/right就和目标值交换,否则就是right和left所在值进行交换,交换完后该哪步走即可。
*在这期间必须严格保证right>left 除非相遇,否则就会发生left和right两者交叉错过的结果。另外的,判断条件也不能只是大于或者小于,也要等于情况写上,否则会死循环的left和right走不动哦~
这就是一轮的走法,然后就可以靠分治的递归做法将我们一轮排好后的两边进行排版好就好啦~
*将这一轮排好打包一下即可。这样后面三种方法均可打包,分治只需要在一个里面就行,并且加上判断当传进来的尾大于小于等于头结束递归即可。
2.代码
//hoare版本
int PartSort1(int* a, int head, int end)
{
int target = head;
int left = target + 1;
int right = end;
while (right > left)
{
//右边先找,找到比target处的数字小的停下 下面经过画图分析,如果不加等号的话,就会陷入死循环~
while (right > left && a[right] >= a[target])
{
right--;
}
while (right > left && a[left] <= a[target])
{
left++;
}
if (right > left)
Swap(&a[right], &a[left]);
}
if (a[right] < a[target])//防止传入的两个数,一次也不进入循环,然后无法判断和target位置所在数组元素大小的情况
Swap(&a[target], &a[right]);
target = right;
return target;
}
后续版本在分治那里哦~
二、挖坑版本
1.思想
可能是想让hoare版本看起来更加好懂一些,在基本思想不变的情况下,稍微改进了一下将两者交换变成了填坑。left right 和key keyi均不变,即左边移动部分 右边移动部分 目标值 目标下标。
只不过在一开始,保存key值 然后将此时的keyi位置的数组值视为第一个坑,然后右边找小的开始找小,找到小停下或者遇到left停下,左边找也是如此。如果两者相遇,就讲key值填入此时位置。如果没有,一开始的话就是右边找小的位置将其值填入keyi的位置,然后自己形成坑由左边找到大的来填,之后就是左右互填即可,直到两者相遇。
分治的话没有什么可以说的。大致思路如上。
2.代码
//挖坑版本
int PartSort2(int* a, int head, int end)
{
int keyi = head;
int left = head + 1;
int right = end;
int key = a[keyi];
while (right > left)
{
//首先右边找到比key小的值,然后把坑填上产生新坑
while (right > left && a[right] >= key)
right--;
a[keyi] = a[right];
keyi = right;
//左边找到大的然后填坑
while (right > left && a[left] <= key)
left++;
a[keyi] = a[left];
keyi = left;
}
a[keyi] = key;
return keyi;
}
三、前后指针版本
1.思想
首先,此方法在核心操作步骤上已经和上面两种完全不同。
这里采用的是双指针前后移动,前面的指针从第二个开始,第一个为目标值并且也是后面指针的位置,前指针一直往后移动,遇到比目标值低的时候,后指针往后移动一步,(此时一定是比目标值大的,因为前指针并没有停止)然后此时处于两位置的值进行交换。
直到后指针移出数组的边界后,然后此时后指针的位置处于原位置(出生的位置)或者交换小的后的位置,总之就是此时后指针指向的位置要么就是目标值要么就是比其小的值,所以目标值与其交换,一轮就执行好了,剩下的用分治去解决即可。
*注意,可能会遇到前指针还未移动,然后后指针就移动,此时两者重复,可以不用进行交换,写代码时可以加入减少时间复杂度。
2.代码
//前后指针版本
int PartSort3(int* a, int head, int end)
{
int keyi = head;
int prev = head;
int cur = head + 1;
while (cur <= end)
{
if (a[cur] < a[keyi] && ++prev != cur)
Swap(&a[cur], &a[prev]);
cur++;
}
Swap(&a[keyi], &a[prev]);
keyi = prev;
return keyi;
}
四、分治思想:
这里就是执行每一轮,然后最终完成程序的过程:首先进行第一轮,第一轮排完后,在目标值的位置的左即begin 和目标值下标减一,这一段和目标值加一和end这两段即可。之后的递归同意是这样的原理,直到递归到没有元素或者只要一个的时候就停止了。
代码:
//快速排序:
void QuickSort(int* a, int head, int end)
{
//结束标志
if (head >= end)
return;
assert(a);
int target = PartSort(a, head, end);
//进入递归,分而治之的思想
//左边
QuickSort(a, head, target - 1);
//右边
QuickSort(a, target + 1, end);
}
五、两种优化
经过上面的几种方法介绍,相信你已经对快排有一定的了解了。那么现在提出一种场景,来看看我们快排的表现。(注 上述三种方法实现的快排均一样的效果)
1.三数取中
比如排 1 2 3 4 5 6 7....n 和 3 2 5 1 4 6 7....
排第一个时快排排了 大概是N*N 而第二种是正常的时间复杂度,这是为什么呢?原因就是根据快速排序的特性,快速排序的快慢取决于目标值的位置 一开始要是就排到中间,那么就可以演变为二分法,但是像这种越接近于有序,那么每次目标值都是最边缘的位置,然后分治里面另一端就会没有用处,永远处理一边,效率自然低下。
所以,这就说明了目标值取得好坏。为了避免这种情况的发生,我们可以针对选目标值做上一点手脚,有随机取值,三数取中等.....但是比较好用的是三数取中,随机值毕竟是有一定的随机性的,说不清楚。下面介绍一下三数取中:
传进原始数组,取头,尾,中三个值,然后三个值分别比较,选出中间值,返回。代码很简答,如下:
//三数取中优化key
int TakeMiddle(int* a, int head, int end)
{
int middle = (head + end) / 2;
if (a[head] < a[middle])
{
if (a[end] > a[middle])
return middle;
else if (a[end] > a[head])
return end;
else
return head;
}
else
{
if (a[middle] > a[end]) //head > middle
return middle;
else if (a[end] > a[head])
return head;
else
return end;
}
}
之后操作就是选取目标值,在进行循环之前不变(三种方法均是),然后得出下标后,与其交换即可,就可以不用动下面写好的代码了:
int keyi = TakeMiddle(a, head, end);
Swap(&a[target], &a[keyi]);
2.小区间优化
当递归到要排的数比较少的时候,这个时候在进行递归会发现迭代的层数有点多,此时相较于普通的方法比如(插入排序)效率会有那么一点低下,所以,针对分治里面每次传入的head和end,在一定区间内进行划分即可:
//小区间使用插入排序缓解最后几层递归过多的问题
if (head - end > 10)
{
//进入递归,分而治之的思想
//左边
QuickSort(a, head, target - 1);
//右边
QuickSort(a, target + 1, end);
}
else
{
//微量数据利用插入排序即可
InsertSort(a, end - head + 1);
}
六、非递归实现快速排序
1.思想
实际上,非递归实现排序理论上和递归排序没有任何区别,只是在分治或者是在储存区间,在分区间进行每一轮的操作时候发生了变化。
首先,这个问题的提出就是因为递归非常容易造成栈溢出,栈的内存很小。所以,这个时候我们能不能不使用递归来进行区间的划分呢? 其实,我们发现递归实际上也是相当于每次传进去的区间不同,那么我们使用非递归的时候,就是每次循环进去不同的区间就好了。
那么如何实现每次循环的区间不同呢?
这就需要一个储存的机制。储存?回顾之前的基础数据结构知识,我们只带栈,队列,堆等数据结构。那么栈和队列用到这个里面是不是刚刚好呢?
对的,在实现栈和队列的时候,使用的是堆内存,堆内存很大,不用担心溢出问题。然后利用栈的先进后出,队列的先进先出原则,每次循环就把区间存进去,一轮弄完后就进行存储,这样就可以解决我们的问题。
具体实现的时候,首先将头和尾插入栈或者队列,栈的话先插尾,然后在头,队列正好相反,然后进入循环,先将本次的区间元素弹出,进入一轮循环,循环完后,在目标值的左右两区间均按照上述步骤即可。
注意在循环里插入的时候判断入栈或者入列条件,即区间的左右必须右大于左,否则不进。条件就是栈、队列空间的元素有无进行判断就好了。
2.实现:
//快速排序的非递归版本(递归的问题,深度太深,容易栈溢出)
//之前是利用递归的方法使其控制对应的区间,那么现在利用栈来储存要改变的区间
void QuickSortNonR(int* a, int begin, int end)
{
ST st;
StackInit(&st);
StackPush(&st, end);
StackPush(&st, begin);
//当栈内元素为空时停止循环即可
while (!StackEmpty(&st))
{
int left = StackTop(&st);
StackPop(&st);
int right = StackTop(&st);
StackPop(&st);
int keyi = PartSort(a, left, right);//PartSort用上述三种方法任意一种均可
if (left < keyi - 1)
{
StackPush(&st, keyi - 1);
StackPush(&st, left);
}
if (keyi + 1 < right)
{
StackPush(&st, right);
StackPush(&st, keyi + 1);
}
}
//StackDestroy(&st);
}
上面是用栈来进行实验的,也可以利用队列哦~
边栏推荐
- id选择器和类选择器的区别
- 【无标题】
- XaaS 陷阱:万物皆服务(可能)并不是IT真正需要的东西
- 【硬核干货】数据分析哪家强?选Pandas还是选SQL
- Reinforcement learning - learning notes 4 | actor critical
- Build your own website (16)
- Thread pool parameters and reasonable settings
- Go language | 02 for loop and the use of common functions
- Reptile exercises (II)
- 14. Users, groups, and permissions (14)
猜你喜欢
Two pits exported using easyexcel template (map empty data columns are disordered and nested objects are not supported)
2023年深圳市绿色低碳产业扶持计划申报指南
Go language | 01 wsl+vscode environment construction pit avoidance Guide
[Collection - industry solutions] how to build a high-performance data acceleration and data editing platform
leetcode刷题:二叉树13(相同的树)
aggregate
[untitled]
建议收藏,我的腾讯Android面试经历分享
Go language | 02 for loop and the use of common functions
Force buckle 1200 Minimum absolute difference
随机推荐
手机股票开户安全吗?靠不靠谱啊?
Debezium series: PostgreSQL loads the correct last submission LSN from the offset
[Collection - industry solutions] how to build a high-performance data acceleration and data editing platform
S7-200SMART利用V90 MODBUS通信控制库控制V90伺服的具体方法和步骤
国信证券在网上开户安全吗?
软件测试是干什么的?学习有啥要求?
third-party dynamic library (libcudnn.so) that Paddle depends on is not configured correctl
Using repositoryprovider to simplify the value passing of parent-child components
What do software test engineers do? How about the prospect of treatment?
After 95, Alibaba P7 published the payroll: it's really fragrant to make up this
Float. The specific meaning of the return value of floattorawintbits is to convert float into byte array
Postman core function analysis - parameterization and test report
Let's talk about threadlocalinsecurerandom
Relationship between floating elements and parent and brother boxes
Debezium series: parsing the default value character set
[hard core dry goods] which company is better in data analysis? Choose pandas or SQL
40000 word Wenshuo operator new & operator delete
acm入门day1
Is the education of caiqiantang reliable and safe?
Is it safe to open a mobile stock account? Is it reliable?