快速排序的递归非递归实习java

package com.edu.hpu.sort.swap.quick;

import java.util.Arrays;
import java.util.LinkedList;

import com.edu.hpu.sort.Sort;

public class QuickSort extends Sort {
    
    @Override
    public int[] doSort(int[] arr) {
        return quickSort2(arr, 0, arr.length - 1);
    }
    
    @SuppressWarnings("unused")
    private int [] quickSort(int [] arr, int p, int r){
        // 递归求解
        if(p < r){
            int q = partition(arr, p, r);
            quickSort(arr, p, q - 1);
            quickSort(arr, q + 1, r);
        }
        return arr;
    }
    private int [] quickSort2(int [] arr, int p, int r){
        // 非递归求解
        if(p < r){
            LinkedList<Integer> stack = new LinkedList<Integer>();
            int q = partition(arr, p, r);
            if(p < q - 1){
                stack.push(q - 1);
                stack.push(p);
            }
            if(r > q + 1){
                stack.push(r);
                stack.push(q + 1);
            }
            while(!stack.isEmpty()){
                int l = stack.pop();
                int h = stack.pop();
                int mid = partition(arr, l, h);
                if(l < mid - 1){
                    stack.push(mid - 1);
                    stack.push(l);
                }
                if(h > mid + 1){
                    stack.push(h);
                    stack.push(mid + 1);
                }
            }
        }
        return arr;
    }
    
    private int partition(int []arr, int p, int r){
        int aix = arr[r];
        int i = p -1;
        for(int j = p; j < r; j++){
            if(arr[j] < aix){
                i++;
                swap(arr, i, j);
            }
        }
        swap(arr, i + 1, r);
        System.out.println(Arrays.toString(arr));
        return i + 1;
    }
    public static void main(String[] args) {
        QuickSort quickSort = new QuickSort();
        quickSort.printOrder(new int []{4, 1, 3, 2, 16, 9, 100, 194, 8, 7});
    }
}