算法 - 快速排序

给定一个无序数组，使用快速排序法对数组进行从小到大排序。

原理： 定义一个基准值，同时遍历数组高、低位，并与之比较。

当高位比基准值大的时候，高位索引 j 往低位移动，也就是j--，当遇到一个比基准值小的数，就把该值赋给低位。

当低位比基准值小的时候，低位索引 i 往高位移动，也就是i++，当遇到一个比基准值大的数，就把该值赋给高位。

重复以上，直到i < j，然后，将基准值赋给低位，递归去排序基准值左侧部分和基准值右侧部分，每次递归都需要找一个新的基准值。

 @Test
public void testQuickSort() {
    int[] arr = {1, 3, 2, 6, 5, 4, 8, 9, 7, 0, 10};
    quickSort(arr, 0, arr.length - 1);
    // -- output :  [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
    System.out.println(Arrays.toString(arr));
}

private void quickSort(int[] arr, int low, int high) {
    if (low >= high) {
        return;
    }
    //低位索引
    int i = low;
    //高位索引
    int j = high;
    //找一个基准值
    int temp = arr[low];
    while (i < j) {
        //将高位和基准值比较
        while (i < j && arr[j] >= temp) {
            j--;
        }
        //将高位不符合条件的值赋给低位
        if (i < j) {
            arr[i] = arr[j];
        }
        //将低位和基准值比较
        while (i < j && arr[i] <= temp) {
            i++;
        }
        //将低位不符合条件的值赋给低位
        if (i < j) {
            arr[j] = arr[i];
        }
    }
    //将基准值赋给i
    arr[i] = temp;
    //排序low到i-1部分的
    quickSort(arr, low, i - 1);
    //排序i+1到high部分的
    quickSort(arr, i + 1, high);
}