非递归快排

非递归快排

Description

快速排序的核心思想是使用元素的值对数组进行划分。实现其非递归方案。

Input

输入的每一行表示一个元素为正整数的数组，所有值用空格隔开，第一个值为数值长度，其余为数组元素值。(题目错误，所有值为数组元素值）

Output

输出的每一行为排序结果，用空格隔开，末尾不要空格。

Solution

public class QuickSort {

    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            String arrLine = in.nextLine();
            String[] arrStr = arrLine.split(" ");
            int[] arr = new int[arrStr.length];
            for(int i = 0; i < arr.length; i++){
                arr[i] = Integer.parseInt(arrStr[i]);
            }
            quickSort(arr);
        }
    }

    public static void quickSort(int[] arr){
        Stack<Integer> stack = new Stack<>();
        int left = 0;
        int right = arr.length - 1;
        stack.push(right);
        stack.push(left);

        while(!stack.isEmpty()){
            left = stack.pop();
            right = stack.pop();
            int pivotPos = partition(arr, left, right);
            if(left < pivotPos - 1){
                stack.push(pivotPos - 1);
                stack.push(left);
            }
            if(right > pivotPos + 1){
                stack.push(right);
                stack.push(pivotPos + 1);
            }
        }

        System.out.print(arr[0]);
        for(int i = 1; i < arr.length; i++){
            System.out.print(" " + arr[i]);
        }
        System.out.println();
    }

    public static int partition(int[] arr, int left, int right){
        int leftPos = left;
        int rightPos = right;
        int pivot = arr[left];

        while(leftPos != rightPos) {
            while (arr[rightPos] >= pivot && leftPos < rightPos) {
                rightPos--;
            }
            if (leftPos < rightPos) {
                int temp = arr[leftPos];
                arr[leftPos] = arr[rightPos];
                arr[rightPos] = temp;
            }
            while (arr[leftPos] <= pivot && leftPos < rightPos) {
                leftPos++;
            }
            if (leftPos < rightPos) {
                int temp = arr[leftPos];
                arr[leftPos] = arr[rightPos];
                arr[rightPos] = temp;
            }
        }
        return leftPos;
    }
}