快速排序递归代码（不用递归你还能实现随机快速排序吗）

快速排序（一）荷兰旗问题 快速排序（二）随机快排 学习了随机快排的递归实现，递归方法需要不断地压栈，有没有不需要压栈的方式实现呢？这里就学习了使用循环来实现递归实现。

  递归操作时一个先递进再出来的概念，但是我循环是从头到尾，没有这个概念啊，这里就想到了和这个概念非常相似的数据结构，栈。

  栈，也是一个先进后出的结构，那是不是我只要模拟递归，将数据不断的压入栈不断的弹出栈循环操作是不是就可以实现呢？先画个草图理一下思路

  理论上我只要有个逻辑可以完成，输入数组，以及两个下标值，完成荷兰旗问题，同时生成等于划分值的下标范围，然后返回两组要处理的下标，继续压入栈，循环这个出栈、处理、压栈的操作，一直到栈为空，就可以完成整个快速排序了吧。

  因为我压入栈的是成组的数据，包含两个下标值，那我就创建一个辅助类，就存两个下标。

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}; }

既然栈都可以，那我用队列是不是也可以，用链表实现栈然后应该也可以吧还没想到其他的实现方式，如果大家有更好的方式欢迎评论留言，如果文中有哪些描述错误的地方，也欢迎大家斧正✨