手撕快排(总结)
2021/12/22 23:50:55
本文主要是介绍手撕快排(总结),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
- 快排、堆排、归并排序
- 链表快排(区分允许用值交换和不允许用值交换两种情况)
- 非递归快排要掌握
- 快排时间复杂度的推导过程?
- 写出来后,也要把下面这几个点考虑下 - 时间复杂度计算 - 控件复杂度计算 - 轴点随机取值 - 为什么与轴点相等也要换位置
快排思路
- 随便找一个数作为基准数6
- 初始状态下,数字6在序列的第1位
- 先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。(i和j称为哨兵)
- 首先哨兵j开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵j先出动,这一点非常重要
- 哨兵j的使命就是要找小于基准数的数,而哨兵i的使命就是要找大于基准数的数,直到i和j碰头为止
-哨兵i和哨兵j相遇于3,则将基准数6和3进行交换。 - 现在基准数6已经归位,此时我们已经将 将这个序列中所有比基准数大的数放在6的右边,比基准数小的数放在6的左边,接下来还需要分别处理这两个序列。
复杂度
快速排序的时间复杂度为:
快排实现
递归版本快排
//快速排序(从小到大) void quickSort(int left, int right, vector<int>& arr) { if(left >= right) return; int i, j, base, temp; i = left, j = right; base = arr[left]; //取最左边的数为基准数 while (i < j) { while (arr[j] >= base && i < j) j--; while (arr[i] <= base && i < j) i++; if(i < j) { temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } //基准数归位 arr[left] = arr[i]; arr[i] = base; quickSort(left, i - 1, arr);//递归左边 quickSort(i + 1, right, arr);//递归右边 }
非递归版本快排:
1.用栈集合存放左右下标
2.用一个方法来得出中下标位置
3.判断中下标的左右区间
4.回到步骤1循环这几步操作,知道栈为空,则排序完成。
#include <iostream> #include <stack> using namespace std; //划分算法 int Partition( int a[], int low, int high ) { //假设每次都以第一个元素作为枢轴值,进行一趟划分: int pivot = a[low]; while( low<high ) { while( low<high && a[high]>=pivot ) --high; a[low] = a[high]; //停下来做交换 while( low<high && a[low]<=pivot ) ++low; a[high] = a[low]; //停下来做交换 } a[low] = pivot; //pivot的最终落点 return low; } //非递归快排 void QuickSort(int a[], int left, int right) { //手动利用栈来存储每次分块快排的起始点 //栈非空时循环获取中轴入栈 stack<int> s; if( left<right ) { int boundary = Partition(a,left,right); if( boundary-1>left ) //确保左分区存在 { //将左分区端点入栈 s.push(left); s.push(boundary-1); } if( boundary+1<right ) //确保右分区存在 { s.push(boundary+1); s.push(right); } while( !s.empty() ) { //得到某分区的左右边界 int r = s.top(); s.pop(); int l = s.top(); s.pop(); boundary = Partition(a,l,r); if( boundary-1>l ) //确保左分区存在 { //将左分区端点入栈 s.push(l); s.push(boundary-1); } if( boundary+1<r ) //确保右分区存在 { s.push(boundary+1); s.push(r); } } } } int main() { int a[5] = { 4, 1, 5, 3, 2 }; int left = 0, right = 4; QuickSort(a,left,right); //输出,检验结果 for( int i=0; i<5; ++i ) { cout << a[i] << " "; } cout << endl; }
point1
当基准数选择最左边的数字时,那么就应该先从右边开始搜索;当基准数选择最右边的数字时,那么就应该先从左边开始搜索。不论是从小到大排序还是从大到小排序!
这篇关于手撕快排(总结)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程:从入门到实践
- 2024-10-01Server Component课程入门指南
- 2024-09-30Dnd-Kit学习:新手快速入门指南