充值网站怎么做,wordpress自定义文章类型标签,制作企业网站得多长时间,居众装饰集团有限公司快速排序#xff08;下#xff09; 前言
在上一篇文章中我们了解了快速排序算法#xff0c;但那是Hoare的版本#xff0c;其实还有别的版本#xff1a;一种是挖坑法#xff0c;它们的区别主要在于如何找基准值。霍尔的版本思路难理解但代码好理解#xff0c;挖坑法则是…快速排序下 前言
在上一篇文章中我们了解了快速排序算法但那是Hoare的版本其实还有别的版本一种是挖坑法它们的区别主要在于如何找基准值。霍尔的版本思路难理解但代码好理解挖坑法则是思路好理解但代码不好理解还有一种是lomuto的前后指针法。 此外还有不使用递归的快排方法找基准值还是用的三种方法之一。
本文就来讲解这几种不同的快排方法。
正文
挖坑法
实现思路 创建左右指针。首先从右向左找出比基准值小的数据找到后立即放入左边坑中当前位置变为新的“坑”然后从左向右找出比基准值大的数据找到后立即放入右边坑中当前位置变为新的“坑”结束循环后将最开始存储的分界值放入当前的“坑”中返回当前“坑”的下标即分界值下标。 画图理解一下什么是“坑”。 这就是整个“挖坑”然后“填坑”直到left和right重叠时将基准值放到该位置它该待的位置的过程。
现在我们可以来写一下挖坑法的代码
//挖坑法
int _QuickSort(int* arr, int left, int right)
{int hole left;int key arr[hole];while (left right)//注意和霍尔版区别{//这里同样需要限制且不能是arr[right] key否则可能无法“二分”最终效率低下while (left right arr[right] key){--right;}arr[hole] arr[right];hole right;while (left right arr[left] key){left;}arr[hole] arr[left];hole left;}arr[hole] key;return hole;
}排序效果
我们在main函数中写这样的代码 int a[] { 5, 3, 9, 6, 2, 4, 7, 1, 8 };int n sizeof(a) / sizeof(int);printf(排序前: );PrintArr(a, n);//代码不具体展示QuickSort(a, 0, n-1);printf(排序后: );PrintArr(a, n);执行结果 可以看到我们就成功排序了。 lomuto前后指针法
实现思路 创建前后指针从左往右找比基准值小的进行交换使得小的都排在基准值的左边。 其实前后指针对于很多学过数据结构的人来说应该已经不陌生了但是快排也能用到前后指针法我们看看具体怎么做
定义两个变量prev和cur让cur指向位置的数据和key值比较 若arr[cur]arr[key]prev向后走一步并和cur交换若arr[cur]arr[key]cur继续往后 退出循环后将prev与key值交换找到基准值
同样不变的思路也是要找基准值也就是要让基准值左侧的数据都小于基准值让基准值右侧的数据都大于基准值。
那么两个变量的作用是什么可以说prev是用来占坑的而cur用来找小找到小后就让prev加一后和cur交换。退出循环后将prev与key值交换就找到了基准值。
代码
//lomuto前后指针法
int _QuickSort(int* arr, int left, int right)
{int prev left, cur left 1;int key left;while (curright){if (arr[cur] arr[key] prev !cur)//prev和cur相同就不交换//写为arr[cur] arr[key]加上等号也是殊途同归{Swap(arr[cur], arr[prev]);}cur;//进不进循环cur都要往后走}Swap(arr[key], arr[prev]);return prev;
}执行效果 也一样成功排序完了。
可以发现这一种方法比起前面的Hoare版本和挖坑法在取不取等号的探讨上少了很多麻烦。 注意 在循环内的if语句中arr[cur] arr[key]如果写为arr[cur] arr[key]并不能解决无法”二分“子序列的问题所以加不加都无所谓。 这也就是前后指针法的一个**缺陷如果数组中数据都相等**效率就会很低。 快排的非递归版本
所以现在已经知道了三种版本的快排其实也就是三种找基准值的方法。
既然我们的快排使用的是递归就难免有空间上的缺陷。其实快排还有非递归版本。但是要借助数据结构栈。
那么现在问题是左右区间再分左右区间时我们怎么找区间呢因为找基准值时没有使用递归而是在找区间时使用的递归所以找基准值使用前面说的三种方法的任意一种都行。 (先将5和0入栈然后出栈left0,right5找到基准值为3)
我们知道keyi基准值也就能区分左区间和右区间这两个区间任意哪一个入栈都行。
现在我们还是一样要现将right入栈再将left入栈先入右区间然后再入另一个区间。 此时栈不为空我们出栈先出的两个就是左区间然后去找它的基准值。
然后这样找下去直到right小于left或等于left时也就是没有数据或者只有一个数据时构不成有效区间就不入栈。
左区间所有基准值找完后就像二叉树一样开始走右区间。
开始走右区间时也就是刚好栈里剩的两个数据为右区间时。
所以可以看出我们取栈顶元素就是在模拟递归。
代码参考
现在我们通过代码来看看怎么使用栈进行快排。
//非递归版快排
//借助数据结构——栈
void QuickSortNonR(int* arr, int left, int right)
{ST st;STInit(st);StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)){//取两次栈顶int begin StackTop(st);StackPop(st);int end StackTop(st);StackPop(st);//找基准值——用双指针法int prev begin;int cur begin 1;int keyi begin;while (cur end){if (arr[cur] arr[keyi] prev!cur){Swap(arr[cur], arr[prev]); }cur;}Swap(arr[keyi], arr[prev]);keyi prev;//根据基准值划分左右区间//左区间[begin,keyi-1]//右区间[keyi1,end]if (keyi 1 end)//控制区间有效{StackPush(st, end);StackPush(st, keyi 1);} if (keyi-1begin)//控制区间有效{StackPush(st, keyi - 1);StackPush(st, begin);}}STDestroy(st);
}那么到此本文就结束了祝学习愉快_
