网站策划建设方法,企业网站建设问题研究,广东省网站免备案,网站开发分为几个方向引言
快速排序作为交换排序的一种#xff0c;在排序界的影响力毋庸置疑#xff0c;我们C语言中用的qsort#xff0c;C中用的sort#xff0c;底层的排序方式都是快速排序。相比于同为交换排序的冒泡#xff0c;其效率和性能就要差的多了#xff0c;本篇博客就是要重点介绍…
引言
快速排序作为交换排序的一种在排序界的影响力毋庸置疑我们C语言中用的qsortC中用的sort底层的排序方式都是快速排序。相比于同为交换排序的冒泡其效率和性能就要差的多了本篇博客就是要重点介绍快速排序的实现以及其代码和效率的优化。 话不多说开始我们今天的内容。
快速排序的基本逻辑
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列使左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
用通俗的语言讲
从一组元素序列中称这个序列为A0随机取出一个数我们可以称这个数为k将比k元素小的数放在k的左边比k元素大的数放在k的右边此时分别将K左右两边边的元素拿出来各成一个序列称为A1和A2同样用处理A的方式处理A1A2序列
最后序列中所有左边的数都会比右边的小完成快速排序。
可以先来处理第一步和第二步也就是快速排序的第一层排序。
快速排序的第一层
这里有一张gif动图大家可以先预热一下如果看懂了可以跳过一部分的讲解。 第一步取第一个元素下标为key为基准值我们的目的是使基准值左边的数都比基准值小基准值右边的数都比基准值大。
第二步定义两个下标变量一个变量从右往左走R一个变量左往右走L。首先从R开始往左走走的时候左边的L保持不动每走一步都与基准值相比较。
让 R 停下来的条件有两个① R 位置的值比基准值小。 ② R 与 L 相遇。
第三步如果让R停下来的条件为①则L开始往右一步步走每走一步也都与基准值比较。
让 L 停下来的条件也有两个① L 位置的值比基准值大。 ② R 与 L 相遇。
第四步如果让 L 停下来的条件为①则交换 L 和 R 两位置所存的值回到第二步 R 开始往左移动重复此过程直到 L 和 R 相遇。
在整个四步过程中一旦出现 R 和 L 相遇则第一层数据遍历结束交换 L 和基准值key存的值并进入下一层的排序。 注在第二步的时候要统一由 R 先开始移动这样可以保证在L和R相遇时一定会是比key小的数。这是因为R先移动在找到比基准值小的数前是不会停止的而L移动的前提条件是R找到了比基准值小的数这一特性使R静止的位置一定会是比基准值key小的数。 故L和R静止一方的值必定比基准值key小。 关于L和R相遇时一定会是比key小的数这个问题如果还没搞懂可以拿张纸来画一画。
上面就是一层快速排序的全过程在这一层排序过后可以找到一个基准值的真正位置也让基准值左边的数都小右边的数都大。
接下来是这一层排序的代码实现
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}int left 0, right n - 1;
int keyi 0;
while (left right) {while (right left a[right] a[keyi]) {right--;}while (right left a[left] a[keyi]){left;}Swap(a[left], a[right]);
}
Swap(a[keyi], a[left]);
递归版快速排序的实现
Hoare版快速排序
写完了第一层之后其他的工作就轻松多了就是运用递归每层递归时需要调整left和right的值。这个过程和二叉树的前序遍历非常相似以下就是完整的hoare版的快速排序
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void QuickSort1(int* a, int left, int right)
{//当leftright时递归结束if (left right)return;int begin left, end right;int keyi left;while (left right) {while (right left a[right] a[keyi]) {right--;}while (right left a[left] a[keyi]) {left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left 1, end);
}
在递归的过程中递归的第一个区间是[begin , left - 1(left - 1即相遇的前一个位置) ]递归的第二个区间[left 1(left 1即相遇的后一个位置) , end] 在快速排序的递归实现中除了发明快速排序的大佬hoare的原版排序方式。还有两种方式虽然底层原理都是一样的但这两种方式也有各自的特点。
挖坑法快速排序
什么是挖坑法顾名思义就是挖一个坑。在理解了hoare版本快速排序的基础上理解这个方式并不困难下面来看看挖坑法的gif格式动图 第一步将基准值挖出存在key中基准值位置下标用一个变量hole位记录相当于一个坑位
第二步首先从R开始往左走走的时候左边的L保持不动每走一步都与基准值相比较。
让 R 停下来的条件有两个① R 位置的值比基准值小。 ② R 与 L 相遇。
第三步如果使R停下来的条件为①则将R下标位置的值放入坑位hole中同时将R下标赋给hole这时候坑位变成R的位置。
第四步如果让R停下来的条件为①则L开始往右一步步走每走一步也都与基准值比较。
让 L 停下来的条件也有两个① L 位置的值比基准值大。 ② R 与 L 相遇。
第五步如果使L停下来的条件为①则将L下标的值放入hole中同时将L下标赋给hole这时候坑位变成L的位置。
这里遍历停止的标志也同样是L和R相遇相遇的位置也是一个坑位直接把key的值放到坑位中第一层整个数据处理就结束了。
下面是挖坑法的实现代码
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void QuickSort2(int* a, int left, int right)
{if (left right)return;int begin left, end right;int valk a[left]; int holei left;while (left right) {while (right left a[right] valk) {right--;}a[holei] a[right]; holei right;while (right left a[left] valk) {left;}a[holei] a[left];holei left;}a[holei] valk;QuickSort2(a, begin, left - 1);QuickSort2(a, left 1, end);
}
挖坑法的优势在于好理解就是保持一个坑位不断往里面填数字然后变换坑位的过程。
前后指针版快速排序
前后指针版本的快速排序不好理解但是代码量出奇的少先看一下gif动图了解大致思路 规则很简单
cur key curcur key prev 交换prev和cur的值结束条件cur end结束后交换prev和key的值
在整个过程中prev的位置之前的数据都小于基准值key而prev和cur之间的值都保证大于基准值key在prev和cur的值交换的过程中相当于把大的数字往后甩把cur找到的小的值往前插入。在cur遍历到最后比基准值小的数字也就成功都插入到了前面而比基准值大的数字也都被甩到了后面。这时交换prev和key的值也就达到了快速排序第一层遍历后的效果。
下面是前后针法的实现代码
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void QuickSort3(int* a, int left, int right)
{if (right left)return;int pcur left 1, prev left, keyi left;while (pcur right) { if (a[pcur] a[keyi] prev ! pcur) Swap(a[pcur], a[prev]);pcur;}Swap(a[keyi], a[prev]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev 1, right);
}
建议大家可以把前后指针法的实现理解后背下来后期Hr面试问的时候搓起来会很爽。
避免最坏时间复杂度的两种解决方案
快速排序排起来是很快但我们上面所写的快排真的就没有缺陷吗
现在你可以试想一种场景如果用上面所写的代码去排一个有序数组会如何。 这时候的复杂度将会是一场灾难。基准值如果每次都是数组的第一个值那么这种情况就很有可能会出现。对于这种由于顺序引起的最坏时间复杂度问题这里提供两种解决方案。
1.随机选key
既然害怕数组顺序无法选出随机数那么让选的基准值下标值为随机取的不就能解决问题了吗就是我们所说的随机选key。
这里随机数需要用到rand()函数头文件stdlib.h
int randi rand();
randi % (right - left 1);
randi left;
Swap(a[randi], a[left]);
以上就是随机key的取法(right - left 1) 是为了控制范围防止越界对随机数做的一个处理。 把这种处理方式放入快排代码中就是这个样子以Hoare版为例
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void QuickSort1(int* a, int left, int right)
{//当leftright时递归结束if (left right)return;int begin left, end right;int keyi left;//取随机key部分int randi rand();randi % (right - left 1);randi left;Swap(a[randi], a[left]);//-----------while (left right) {while (right left a[right] a[keyi]) {right--;}while (right left a[left] a[keyi]) {left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left 1, end);
}
2.三数取中
具体思路是找三个下标leftright mid对应的数取三个数中处于中间位置的作为key基准值其中 mid (left right) / 2 。
这里我们专们写一个三数取中的函数这一过程相对比较复杂
//三数取中函数
int GetMid(int* a, int left, int right)
{int mid (left right) / 2;if (a[left] a[mid]) {if (a[mid] a[right])return mid;else if (a[left] a[right])return left;else return right;}else {if (a[mid] a[right])return mid;else if (a[left] a[right])return left;else return right;}
}
与上述随机取key时放置的位置一样
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void QuickSort1(int* a, int left, int right)
{//当leftright时递归结束if (left right)return;int begin left, end right;int keyi left;//三数取中部分int midi GetMid(a, left, right);Swap(a[midi], a[left]);//-----------while (left right) {while (right left a[right] a[keyi]) {right--;}while (right left a[left] a[keyi]) {left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left 1, end);
}
到这里避免最坏时间复杂度的两种方案就介绍完了。
小区间优化
什么是小区间优化
你是否考虑过这样一个问题当快排递归到最后几层时会产生多少小区间。 这里出现了一个很明显的问题待排序的数很少但是走递归的消耗较大最后几层的递归占整个递归的80%~90%。
这里给出的小区间优化方式就是当递归进入待排序数字只剩10个左右的时候使用直接插入排序的方式对小区间进行排序。
//小区间优化方式
if(right - left 1 10)
{//插入排序减少90%的递归InsertSort(a left, right - left 1);
}
放到hoare版快排中就是这样的可以省去if判断return。
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}void QuickSort1(int* a, int left, int right)
{//小区间优化方式if(right - left 1 10){//插入排序减少90%的递归InsertSort(a left, right - left 1);}//-------------int begin left, end right;int keyi left;while (left right) {while (right left a[right] a[keyi]) {right--;}while (right left a[left] a[keyi]) {left;}Swap(a[left], a[right]);}Swap(a[keyi], a[left]);QuickSort1(a, begin, left - 1);QuickSort1(a, left 1, end);
}
此方式优化了大部分的递归但得益于计算机对递归的处理这种优化和原版的效率比起来就没有那么明显了。
快速排序的非递归实现
讲了这么多总算是到了咱们的最后一个问题快速排序非递归的实现。既然不让递归咱们可以换个思路用栈模拟个递归不就行了。在栈中存放左右区间可以和递归达到同一个效果。
你问我栈是什么emm我之前写了一遍关于栈的博客供参考
初阶数据结构之---栈和队列C语言
取区间的方式 先插入总区间进入一个大循环中循环结束的条件为栈为空每次取栈顶弹栈处理区间后再次往栈中插入被分割出来的有效区间继续循环。
主体思路就是用栈模拟一个递归的过程栈本来应该是构建一个结构体存左右区间不过这里我就直默认顺序接插入右区间和左区间取的时候依次就是是左区间和右区间不再麻烦造个结构体了。
以下是非递归实现快速排序复用上次栈的代码
typedef int STDataType;
typedef struct stack
{STDataType* a;int top;int capacity;
}ST;void STInit(ST* ps)
{assert(ps);ps-a NULL;ps-top ps-capacity 0;
}void STDestory(ST* ps)
{assert(ps);free(ps-a);ps-a NULL;ps-top ps-capacity 0;
}void STPush(ST* ps, STDataType x)
{assert(ps);if (ps-top ps-capacity) {int newcapacity ps-capacity 0 ? 4 : 2 * ps-capacity;STDataType* tmp (STDataType*)realloc(ps-a, newcapacity * sizeof(STDataType));if (tmp NULL) {perror(realloc tmp fail:);exit(1);}ps-a tmp;ps-capacity newcapacity;}ps-a[ps-top] x;ps-top;
}bool STEmpty(ST* ps)
{assert(ps);return ps-top 0;
}void STPop(ST* ps)
{assert(ps);assert(!STEmpty(ps));ps-top--;
}STDataType STTop(ST* ps)
{assert(ps);assert(!STEmpty(ps));return ps-a[ps-top - 1];
}int STSize(ST* ps)
{assert(ps);return ps-top;
}// 快速排序 非递归实现
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(st);STPush(st, right);STPush(st, left);while (!STEmpty(st)) {int begin STTop(st); STPop(st);int end STTop(st); STPop(st);if (begin end)continue;int keyi begin, prev begin, pcur begin 1;while (pcur end) {if (a[pcur] a[keyi] prev ! pcur)Swap(a[prev], a[pcur]);pcur;}Swap(a[prev], a[keyi]);STPush(st, prev - 1); STPush(st, begin);STPush(st, end); STPush(st, prev 1);}
}结语
以上就是快速排序的所有内容本篇博客关于快排的内容讲到了Hoare原版快速排序挖坑法和双指针法避免快排最坏时间复杂度的两种解决方案小区间优化非递归的快排等内容希望能帮助大家快速理解和学会快速排序。
感谢大家的支持
