快速排序（三）非递归实现随机快排
前言
前面学习了随机快排的递归实现，递归方法需要不断的压栈，有没有不需要压栈的方式实现呢？这里就学习了使用循环来实现递归实现。
🤔思考👇
递归操作时一个先递进再出来的概念，但是我循环是从头到尾，没有这个概念啊，这里就想到了和这个概念非常相似的数据结构，栈。
栈，也是一个先进后出的结构，那是不是我只要模拟递归，将数据不断的压入栈不断的弹出栈循环操作是不是就可以实现呢？先画个草图理一下思路
image.png
理论上我只要有个逻辑可以完成，输入数组，以及两个下标值，完成荷兰旗问题，同时生成等于划分值的下标范围，然后返回两组要处理的下标，继续压入栈，循环这个出栈、处理、压栈的操作，一直到栈为空，就可以完成整个快速排序了吧。
❤️代码👇
因为我压入栈的是成组的数据，包含两个下标值，那我就创建一个辅助类，就存两个下标。
static class 范围{
int 左;
int 右;
范围(int 左,int 右){
this.左 = 左;
this.右 = 右;
}
}
接下来我就不写解析了，具体每行代码代表啥意思我都写上去了😊
static class 范围{
int 左;
int 右;
范围(int 左,int 右){
this.左 = 左;
this.右 = 右;
}
}
/**
* 随机快排3
* @param arr
* @param L
* @param R
*/
public static void kspxrk3(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
// 先随机row一个值作为划分值
int rowValue = (int) (Math.random() * arr.length);
// 划分值 和 最右值交换
swap(arr, rowValue, arr.length - 1);
// 算出第一次划分出来的下标
int[] 边界 = hlqcz(arr, 0, arr.length - 1);
// 创建一个栈
Stack<范围> stack = new Stack<>();
// 往栈里压入数据
stack.push(new 范围(0, 边界[0] - 1));// 左组，是0到左边界-1
stack.push(new 范围(边界[1] + 1, arr.length - 1));// 右组，是右边界+1到数组结束
// 处理栈中的数据,结束条件为栈为空
while (!stack.isEmpty()) {
// 弹出要处理的数
范围 f = stack.pop();
// 考虑边界
if (f.左 < f.右) {
// 继续划分的逻辑
// 先随机一个row作为划分值，然后和最右值交换
swap(arr, (int) (Math.random() * (f.右 - f.左 + 1)), f.右);
// 算出这次划分出来的下标
边界 = hlqcz(arr, f.左, f.右);
// 再次将边界下标压入栈
stack.push(new 范围(f.左, 边界[0] - 1));// 左组，是0到左边界-1
stack.push(new 范围(边界[1] + 1, f.右));// 右组，是右边界+1到数组结束
}
}
}
public static int[] hlqcz(int[] arr , int L ,int R ) {
// L大于R 的时候，越界了
if(L>R) {
return new int[] {-1,-1};
}
//L == R 的时候，左边结束，右边也结束了
if(L==R) {
return new int[] {L,R};
}
//左边界
int less = L - 1;
//右边界
int more = R;
//当前下标,从左开始
int index = L;
//当前下标，碰触右边界结束
while (index<more) {
if(arr[index]==arr[R]) {
//如果当前值 和 最右位置值相等，最右位置值作为划分值，当前下标+1，数据不动
index++;
}else if(arr[index]<arr[R]) {
//如果当前值 小于 划分值，当前值和左边界+1的值交换，然后左边界+1，当前下标+1
swap(arr, index++, ++less);
}else {
//如果当前值 大于 划分值，当前值和右边界-1的值交换，然后有边界-1，当前下标不动
swap(arr, index, --more);
}
}
//当前下标碰到右边界了
//当前位置的值和R位置的值进行交换，R位置的值是划分值，也就是说它一定在中间
swap(arr, more, R);
//返回中间的值的下标
return new int[] {less+1,more};
}
总结
既然栈都可以，那我用队列是不是也可以，用链表实现栈然后应该也可以吧还没想到其他的实现方式，如果大家有更好的方式欢迎评论留言，如果文中有哪些描述错误的地方，也欢迎大家斧正✨
