import java.util.Arrays;
import java.util.Random;

/**
 * 挖坑法实现的快速排序
 */
public class QuickSort {

    public static void main(String[] args) {

        int[] array = {4, 7, 6, 5, 3, 2, 9, 1};

        sort(array, 0, array.length - 1);

        System.out.println(Arrays.toString(array));
    }

    public static void sort(int[] array, int start, int end) {

        if (start >= end) {
            return;
        }
        int pivotIndex = partition(array, start, end);
        sort(array, start, pivotIndex - 1);
        sort(array, pivotIndex + 1, end);
    }

    /**
     * @return int
     * @Author MRC
     * @Description 采用分治法 返回基准元素位置
     * @Date 17:52 2020/5/25
     * @Param [arr 被操作的数组, start 分治法起始位置, end 结束位置]
     **/
    private static int partition(int[] arr, int start, int end) {

        //取首位为基准元素。//也是坑的位置
        int pivotIndex = start;
        //基准元素的值
        int pivot = arr[pivotIndex];
        //左边指针
        int left = start;
        //右边指针
        int right = end;

        /**
         * 大循环用于判断总体循环
         * 在左右指针指向同位置后
         * 结束循环
         */
        while (right >= left) {
            /**
             * 右指针
             */
            while (right >= left) {

                if (arr[right] < pivot) {
                    arr[pivotIndex] = arr[right];
                    pivotIndex = right;
                    left++;
                    break;
                }
                right--;
            }
            /**
             * 左指针
             */
            while (right >= left) {

                if (arr[left] > pivot) {
                    arr[pivotIndex] = arr[left];
                    pivotIndex = left;
                    right--;
                    break;
                }
                left++;
            }
        }
        arr[pivotIndex] = pivot;
        return pivotIndex;
    }

}