💓博主CSDN主页:杭电码农-NEO💓
⏩专栏分类:八大排序专栏⏪
🚚代码仓库:NEO的学习日记🚚
🌹关注我🫵带你学习排序知识
🔝🔝
1. 前情回顾
在学习快排非递归版前
我们要先了解快排的思想和栈的结构
可以跳转快排初阶和栈详解复习一下
非递归版的快排只是优化了递归函数
然而单趟快排所用的思想还是不变的
只不过将递归过程转化为了循环
注:本章单趟快排使用最左边做为基准值
2. 快排非递归基本思路
我们先定义一个无序数组:
int a[]={6,1,2,7,9,3,4,5,10,8};
一共十个元素,下标范围:0 ~ 9
基本思路:
- 第一次快排要遍历下标0~9的元素
- 将 0 和 9入栈后使用完再出栈
- 假设第一趟快排分了两个子区间为
- 0~ 4和6~ 9.将6,9入栈后再将0,4入栈
- 栈顶为0,4,单趟快排就遍历下标为0~4
- 使用完后0,4出栈,并且将子区间入栈
- 以此类推直到栈中没有元素
画图理解:
3. 对非递归思路的解释
思考:
- 非递归的优势是什么?
- 为什么要用栈结构?
- 为什么右子区间要先入栈?
- 怎么判断左右子区间的小标范围?
解释:
非递归的优势是无论预排序数组多长
都不会产生栈溢出问题.
而递归层数太深,系统栈帧空间不足
就会发生栈溢出的错误
使用栈结构是由于栈的特殊性质:
栈后进先出的特性可以使数组:
左子区间全部排好序再排右子区间.
这和递归的过程保持一致.
如果入栈顺序乱来,也可以排好序
只不过代码和思想不容易被理解
我们设计每一次单趟排序返回
基准值所在位置对应的下标
而下标加一为右子区间的开始
下标减一为左子区间的截至
(注:单趟快排可以使用任意方法)
方法详解:
4. 单趟快排代码实现
我们假设这里使用指针法做单趟快排
前后指针法:
//单趟快排(前后指针版本) int Partion3(int* a, int left, int right) { //三数取中--面对有序的情况不会栈溢出(key不会选到最大或者最小的数) int mini = GetMidIndex(a, left, right); swap(&a[left], &a[mini]); int key = left; int prev = left; int cur = left + 1; while (cur <= right) { while (a[cur] >= a[key] && cur <= right)//cur指针找小于key的 { ++cur; } if (cur <= right) { swap(&a[++prev], &a[cur]); cur++;//交换完后,cur要再往后走一步 } } swap(&a[key], &a[prev]);// 最后交换prev和key的值 return prev;//返回基准值的位置,方便下次递归 }
5. 快排非递归代码实现
非递归代码:
//快速排序(非递归) void QuickSortNonR(int* a, int left, int right) { ST st; StackInit(&st); StackPush(&st, left); StackPush(&st, right); while (!StackEmpty(&st))//当栈不为空时就继续 { int end = StackTop(&st);//将栈顶元素赋值给下标遍历的尾 StackPop(&st);//删除栈顶元素 int begin = StackTop(&st);//再将新的栈顶元素给下标遍历的头 StackPop(&st);//再把这个值删除 int key = Partion3(a, begin, end);//单趟快排返回基准值对应位置下标 if (key < end) { StackPush(&st, key + 1); StackPush(&st, end); } if (begin < key - 1) { StackPush(&st, begin); StackPush(&st, key); } } StackDestroy(&st); }
6. 总结思考
总的来说,学计算机专业的同学
掌握快速排序是必须的.
但是大部分人都只会递归版本的快排
如果在面试的时候你现场给面试官
手撕一个非递归的快速排序
那么你一定会在人群中脱颖而出!
🔎 下期预告:归并排序初级篇 🔍
