软件开发者能看到手机信息吗,浙江网站建设抖音seo优化,公共货运平台,商品详情页面模板html「前言」文章内容是排序算法之快速排序的讲解。#xff08;所有文章已经分类好#xff0c;放心食用#xff09; 「归属专栏」排序算法 「主页链接」个人主页 「笔者」枫叶先生(fy) 目录 快速排序1.1 原理1.2 Hoare版本#xff08;单趟#xff09;1.3 快速排序完整代码所有文章已经分类好放心食用 「归属专栏」排序算法 「主页链接」个人主页 「笔者」枫叶先生(fy) 目录 快速排序1.1 原理1.2 Hoare版本单趟1.3 快速排序完整代码Hoare版(递归实现)1.4 选择基准数key优化三数取中1.5 挖坑法单趟1.6 快速排序完整代码挖坑法(递归实现)1.7 前后指针版单趟1.8 快速排序完整代码前后指针版(递归实现)1.9 快速排序小区间优化1.9 快速排序非递归实现1.10 特性总结 快速排序
1.1 原理
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法一种高效的排序算法
基本思想是通过一趟排序将待排序的数据分割成独立的两部分其中一部分的所有数据都比另一部分小然后再按照此方法对这两部分数据分别进行快速排序以达到整个数据变成有序序列
具体步骤如下
从数列中挑出一个元素作为基准元素将比基准元素小的元素放在其左边比基准元素大的元素放在其右边基准元素所在位置即为最终位置分别对左右两个子序列递归地进行快速排序
对于如何按照基准值将待排序列分为两个子序列单趟单趟常见的方式有
Hoare版本挖坑法前后指针法
下面先谈Hoare版本的
1.2 Hoare版本单趟
Hoare版本的单趟排序的动图如下
Hoare版本的单趟排序的基本步骤如下
从数组中选出一个key一般是最左边或是最右边的上面动图是选左边的定义一个left: L和一个right: R。如果选的key是左边的则需要R先走然后L从左向右走R从右向左走。注意若选择最右边的数据作为key则需要L先走选左选取最左边的基准值作为keyL和R的任务1L找比key大的2R找比key小的选取最左边的基准值作为key 在走的过程中若R遇到小于key的数则停下L开始走直到L遇到一个大于key的数时将L和R的内容交换R再次开始走如此进行下去直到L和R最终相遇相遇结束。此时将相遇点的内容与key交换即可选右选取最左边的基准值作为keyL和R的任务1L找比key小的2R找比key大的选取最右边的基准值作为key 在走的过程中若L遇到小于key的数则停下R开始走直到R遇到一个大于key的数时将L和R的内容交换L再次开始走如此进行下去直到L和R最终相遇相遇结束。此时将相遇点的内容与key交换即可
经过一次单趟排序最终使得key左边的数据全部都小于keykey右边的数据全部都大于key并且key所在的位置就是最终的位置 相遇位置的值如何保证比key小相遇点直接和key交换会不会出错会不会把较大的值换到了左边 如果选取最左边的基准值作为keyR先走保证相遇位置的值保证比key小如果R停下来L走L撞到R相遇相遇位置的值必定比key小如果L停下来R走R撞到L相遇相遇位置的值必定比key小同理如果选取最右边的基准值作为keyL先走保证相遇位置的值保证比key大
1.3 快速排序完整代码Hoare版(递归实现)
首先经过一次单趟排序然后将key的左序列和右序列再次进行这种单趟排序如此反复操作下去直到左右序列只有一个数据或是左右序列不存在时停止操作此时序列或者子序列已经有序 排序步骤演示 类似于二叉树的前序遍历 代码如下递归Hoare版升序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// Hoare版本单趟
int PartQuickSort(int* arr, int left, int right)
{int keyi left; // key的下标选左边为keywhile (left right) // left right即相遇{// right先走找比key小的值while (left right arr[right] arr[keyi]){--right;}// left后走找比key大的值while (left right arr[left] arr[keyi]){left;}// 找到一组值交换交换arr[left] 和 arr[right]if (left right){Swap(arr[left], arr[right]);}}Swap(arr[keyi], arr[left]); // 交换 keyi 和相遇点位置的值leftrightreturn left; // 返回相遇点的下标
}// 快速排序
void QuickSort(int* arr, int left, int right)
{// 1、区间不存在(left right) 2、只有一个数数不需要再处理(left right)if (left right){return;}// 单趟排序并获取基准值int keyi PartQuickSort(arr, left, right);// 递归处理每一个子序列左、右QuickSort(arr, left , keyi - 1); // keyi 左序列进行排序QuickSort(arr, keyi 1, right); // keyi 右序列进行排序
}1.4 选择基准数key优化三数取中
快速排序的时间复杂度是O(NlogN)是我们在理想情况下计算的结果
在理想情况下我们每次进行完单趟排序后key的左序列与右序列的长度都相同 若每趟排序所选的key都正好是该序列的中间值即单趟排序结束后key位于序列正中间那么快速排序的时间复杂度就是O(NlogN)
可是谁能保证你每次选取的key都是正中间的那个数呢
例如以下数组 如果基准值key是数组中最大或最小的数值假设选左边则快速排序的递归深度会非常深排序效率会很低
若是一个有序数组使用快速排序这种情况下快速排序的时间复杂度退化为O(N^2) 对快速排序效率影响最大的就是选取的key若选取的key越接近中间位置则则效率越高
为了避免这种极端情况的发生于是出现了三数取中 三数取中 三数取中的方法是从待排序数组中选择三个元素分别是左端、右端和中间位置的元素然后取这三个元素的中间值作为基准元素
代码如下
// 三数取中
int GetMidIndex(int* arr, int left, int right)
{int mid left (right - left) / 2;if (arr[left] arr[mid]) {if (arr[mid] arr[right]) {return mid; // [mid]是中间值}else if (arr[left] arr[right]){return left;}else{return right;}}else // arr[left] arr[mid]{if (arr[mid] arr[right]){return mid;}else if (arr[left] arr[right]){return left;}else{return right;}}
}需要注意当大小居中的数不在序列的最左或是最右端时我们不是就以居中数的位置作为key的位置而是将key的值与最左端的值进行交换这样key就还是位于最左端了所写代码就无需改变而只需在单趟排序代码开头加上以下两句代码即可:
如下
// Hoare版本单趟
int PartQuickSort(int* arr, int left, int right)
{// 三数取中int midi GetMidIndex(arr, left, right);Swap(arr[left], arr[midi]);int keyi left; // key的下标选左边为key// ...return left; // 返回相遇点的下标
}1.5 挖坑法单趟
挖坑法是基于Hoare版本改良的Hoare版本代码细节太多
挖坑法的单趟排序的动图如下 挖坑法的单趟排序的基本步骤如下
选出一个数据上图选最左为坑存放在key变量中在该数据位置形成一个坑定义一个left: L和一个right: RL从左向右走R从右向左走若在最左边挖坑则需要R先走若在最右边挖坑则需要L先走选取最左边的作为坑位为例L和R的任务1L找比key大的2R找比key小的R先走在走的过程中若R遇到小于key的数则将该数抛入坑位并在此处形成一个新的坑位这时L再向后走若遇到大于key的数则将其抛入坑位又形成一个坑位如此循环下去直到最终L和R相遇这时将key抛入坑位即可
经过一次单趟排序最终也使得key左边的数据全部都小于keykey右边的数据全部都大于key并且key所在的位置就是最终的位置
挖坑法代码如下升序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// 挖坑法单趟
int PartQuickSort2(int* arr, int left, int right)
{// 三数取中int midi GetMidIndex(arr, left, right);Swap(arr[left], arr[midi]);int key arr[left]; // 在最左形成一个坑位int hole left; // 坑的下标while (left right){// right先走找比key小的while (left right arr[right] key){--right;}arr[hole] arr[right]; // 填坑hole right;// left后走找比key大的while (left right arr[left] key){left;}arr[hole] arr[left]; // 填坑hole left;}arr[hole] key;return hole;
}1.6 快速排序完整代码挖坑法(递归实现)
代码如下递归挖坑法升序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// 挖坑法单趟
int PartQuickSort2(int* arr, int left, int right)
{// 三数取中int midi GetMidIndex(arr, left, right);Swap(arr[left], arr[midi]);int key arr[left]; // 在最左形成一个坑位int hole left; // 坑的下标while (left right){// right先走找比key小的while (left right arr[right] key){--right;}arr[hole] arr[right]; // 填坑hole right;// left后走找比key大的while (left right arr[left] key){left;}arr[hole] arr[left]; // 填坑hole left;}arr[hole] key;return hole; // 返回key的下标
}// 快速排序
void QuickSort(int* arr, int left, int right)
{// 1、区间不存在(left right) 2、只有一个数数不需要再处理(left right)if (left right){return;}// 单趟排序并获取基准值int keyi PartQuickSort2(arr, left, right);// 递归处理每一个子序列左、右QuickSort(arr, left , keyi - 1); // keyi 左序列进行排序QuickSort(arr, keyi 1, right); // keyi 右序列进行排序
}1.7 前后指针版单趟
前后指针版的单趟排序的动图如下 前后指针法的单趟排序的基本步骤如下
选出一个key最左边或是最右边的上图选最左开始时prev指向序列的左边cur指向prev1的位置情况1若cur指向的内容小于key则prev向右后移动一位然后交换prev和cur指针指向的内容然后cur指针情况2若cur指向的内容大于key则cur指针直接。如此进行下去直到cur指针越界此时将key和prev指针指向的内容交换即可
前后指针版代码如下升序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// 前后指针版单趟
int PartQuickSort3(int* arr, int left, int right)
{// 三数取中int midi GetMidIndex(arr, left, right);Swap(arr[left], arr[midi]);int keyi left;int prev left;int cur left 1;while (cur right){if (arr[cur] arr[keyi]) // cur指向的内容小于key{prev;if(prev ! cur)Swap(arr[prev], arr[cur]);}cur;}Swap(arr[keyi], arr[prev]);return prev; // 返回key当前的下标
}1.8 快速排序完整代码前后指针版(递归实现)
代码如下递归前后指针版升序
void Swap(int* p1, int* p2)
{int tmp *p1;*p1 *p2;*p2 tmp;
}// 前后指针版单趟
int PartQuickSort3(int* arr, int left, int right)
{// 三数取中int midi GetMidIndex(arr, left, right);Swap(arr[left], arr[midi]);int keyi left;int prev left;int cur left 1;while (cur right){if (arr[cur] arr[keyi]) // cur指向的内容小于key{prev;if(prev ! cur)Swap(arr[prev], arr[cur]);}cur;}Swap(arr[keyi], arr[prev]);return prev; // 返回key当前的下标
}// 快速排序
void QuickSort(int* arr, int left, int right)
{// 1、区间不存在(left right) 2、只有一个数数不需要再处理(left right)if (left right){return;}// 单趟排序并获取基准值int keyi PartQuickSort3(arr, left, right);// 递归处理每一个子序列左、右QuickSort(arr, left , keyi - 1); // keyi 左序列进行排序QuickSort(arr, keyi 1, right); // keyi 右序列进行排序
}1.9 快速排序小区间优化
快速排序的递归类似于二叉树的形式深度越深待排数组的长度越短但是数量也越多调用函数的次数就越多开辟函数栈帧的消耗越大导致效率下降每一层的递归次数会以2倍的形式快速增长后三层的递归次数占据了总递归次数的70%以上
优化的方式就是设置一个排序序列的长度大小若是数组长度大于这个指定的数则调用快速排序若是数组长度小于这个指定的数不再调用快速排序而是调用插入排序或者其他排序
这个数可自行调整代码如下
// 快速排序优化
void QuickSort2(int* arr, int left, int right)
{// 1、区间不存在(left right) 2、只有一个数数不需要再处理(left right)if (left right){return;}if (right - left 1 8) // 可自行调整{// 单趟排序并获取基准值int keyi PartQuickSort3(arr, left, right);// 递归处理每一个子序列左、右QuickSort(arr, left, keyi - 1); // keyi 左序列进行排序QuickSort(arr, keyi 1, right); // keyi 右序列进行排序}else // 调用其他排序{InsertSort(arr left, right - left 1);}
}1.9 快速排序非递归实现
将一个用递归实现的算法改为非递归时一般需要借用一个数据结构那就是栈
C语言的库没有封装有stack需要自己手搓一个C的STL库则封装有
如果是C语言我就不贴代码了代码链接stack下面简单介绍一下手搓stack的接口
// 初始化
void StackInit(ST* ps);
// 销毁栈
void StackDestroy(ST* ps);
// 入栈
void StackPush(ST* ps, STDataType x);
// 出栈
void StackPop(ST* ps);
// 检测栈是否为空如果为空返回非零结果如果不为空返回0
bool StackEmpty(ST* ps);
// 获取栈顶元素
STDataType StackTop(ST* ps);
// 获取栈中有效元素个数
int StackSize(ST* ps);快速排序的非递归算法基本思路 先将待排序列的第一个元素的下标和最后一个元素的下标入栈当栈不为空时读取栈中的信息一次读取两个一个是left另一个是right然后调用某一版本的单趟排序排完后获得了key的下标然后判断key的左序列和右序列是否还需要排序若还需要排序就将相应序列的left和right入栈若不需排序了序列只有一个元素或是区间不存在就不需要将该序列区间的信息入栈重复执行步骤2直到栈为空为止
C语言代码如下升序
void QuickSort3(int* arr, int left, int right)
{Stack st; // 创建栈StackInit(st); // 初始化栈StackPush(st, left); // 待排序列的leftStackPush(st, right); // 待排序列的rightwhile (!StackEmpty(st)) // 栈为空结束{int right StackTop(st); // 读取rightStackPop(st); // 出栈int left StackTop(st); // 读取leftStackPop(st); // 出栈// 判断左右区间是否合理若不合理则跳过本次循环if (left right){continue;}int keyi PartQuickSort2(arr, left, right); // 调用单趟的方法StackPush(st, left); // 左序列的left入栈StackPush(st, keyi - 1); // 左序列的right入栈StackPush(st, keyi 1); // 右序列的left入栈StackPush(st, right); // 右序列的right入栈}
}C代码如下升序
void QuickSort4(int* arr, int left, int right)
{stackint st; // 创建栈st.push(left); // 待排序列的leftst.push(right); // 待排序列的rightwhile (!st.empty()) // 栈为空结束{int right st.top(); // 读取rightst.pop(); // 出栈int left st.top(); // 读取leftst.pop(); //出栈//判断左右区间是否合理若不合理则跳过本次循环if (left right){continue;}int keyi PartQuickSort2(arr, left, right); // 调用单趟的方法st.push(left); // 左序列的left入栈st.push(keyi - 1); // 左序列的right入栈st.push(keyi 1); // 右序列的left入栈st.push(right); // 右序列的right入栈}
}1.10 特性总结 快速排序的特性总结如下 时间复杂度平均情况下快速排序的时间复杂度为O(nlogn)空间复杂度O(1)稳定性不稳定不适用于小规模数据适用于大规模数据的排序
--------------------- END ----------------------
「 作者 」 枫叶先生
「 更新 」 2024.1.20
「 声明 」 余之才疏学浅故所撰文疏漏难免或有谬误或不准确之处敬请读者批评指正。
