快排的非递归写法

递归写法的思路

递归的写法的思路是，拿到一个标准量，找到它对应的位置，然后调用函数自己去实现左边和右边的更小规模的排序。

非递归写法

栈帧又称 过程活动记录 ，主要用于记录函数调用过程中的一些 局部变量和中间数据 。

递归调用在虚拟机栈中的实现也是不断压栈的操作，栈顶的栈帧是当前活动栈帧，如果再有调用，就继续压栈

那么我们能否使用栈这种数据结构来实现递归过程的模拟呢，答案是肯定的。

对于快排来讲，如上图来讲，每次选取的标准元素位置固定后，我们继续调用下个层次的，或者回溯到之前的层次，需要的仅仅是边界，知道左右边界，我们就知道如何处理，所以栈帧我们仅仅记录调用过程的左右边界即可

非递归代码如下：

import java.util.Stack;

class StackFrame{
    int left;
    int right;
    StackFrame(int left,int right){
        this.left = left;
        this.right = right;
    }
}
public class QuickSort {
    private Stack<StackFrame> stack;

    public static void main(String[] args) {
        //int[] arr = {1,3,2,1,7,9,2,8,3};
        int[] arr = {5,4,3,2,1,0,-1};
        //int[] arr = {1,2,3,4,5,6,7,0};
        new QuickSort().quickSort(arr);
        for (int i : arr) {
            System.out.print(i+" ");
        }
    }

    public void quickSort(int[] arr){
        stack = new Stack<>();
        int len = arr.length;
        stack.add(new StackFrame(0,len-1));
        while(!stack.isEmpty()){
            StackFrame sf = stack.pop();
            int left = sf.left;
            int right = sf.right;
            if(left>=right){
                continue;
            }
            int p1 = left + 1;
            int p2 = right;
            while(p1<=p2){
                if(arr[left]>=arr[p1]){
                    p1 ++;
                }else{
                    swap(arr,p1,p2--);
                }
            }
            swap(arr,left,p2); // 找到第一元素的位置
            stack.add(new StackFrame(left,p2-1));
            stack.add(new StackFrame(p2+1,right));
        }
    }

    private void swap(int[] arr,int i,int j){
        int temp = arr[j];
        arr[j] = arr[i];
        arr[i] = temp;
    }
}