//快速排序的非递归版本

//快速排序的非递归版本

package quickSort;
 
import java.util.Stack;
 
/**
 * @author 真他喵的学不动咯
 * @create 2022-08-19--20:52
 */
public class quictwo {   //快速排序的非递归版本
 
    public static class Job{
        public int L;
        public int R;
        public Job(int left,int right){
            L=left;
            R=right;
        }
    }
    //分层【用了递归】
    public static int[] partition(int[] arr, int L, int R){
        /*
        arr[L,...,R]，arr[R做划分值
        L......R
        <  =   >
         */
        int lessR=L-1; //L-1为左边预备区域
        int moreL=R;   //R是右边第一区域
        int index=L;  //L是左边第一轮开始的地方，从L开始遍历
        while (index<moreL){
            if (arr[index]<arr[R]){
                swap(arr,++lessR,index++);
            }
            else if (arr[index]>arr[R]){
                swap(arr,--moreL,index);
            }else{
                index++;
            }
        }
        swap(arr,moreL,R);   //moreL和最后一个数进行了交换，所以下一句直接就是moreL，而不是moreL-1
        return new int[]{lessR+1,moreL};    //lessR+1 是等于区域的第一个，moreL是等于区域的最后一个
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    public static void quicksort2(int[] arr){
        if (arr==null||arr.length<2){
            return;
        }
        Stack<Job> stack=new Stack<>();  //把Job放入栈
        stack.push(new Job(0,arr.length-1));  //在0~N上排序
        while (!stack.isEmpty()){  //栈中不为空，就一直做
            Job cur=stack.pop();
            int L=cur.L;
            int R=cur.R;
            int[] equals=partition(arr,L,R);  //知道左任务、右任务，在栈然后一直做
            //equals返回等于区域
            if (equals[0]>cur.L){   //此时有小于区域
                stack.push(new Job(cur.L,equals[0]-1));
            }
            if (equals[1]<cur.R){      //此时有大于区域
                stack.push(new Job(equals[1]+1,R));
            }
        }
    }
}