快速排序

双指针实现，选定一个基准值，分别对基准值左右两个子序列进行递归操作，使其变得有序（即比基准值大的放右边，比基准值小的放左边），重要的是基准值，算法快慢取决于基准值的位置。

如何选取基准值

1. 
   选第一个或者最后一个

这种选取对于随机数组来说没问题，但是对于有序数组，此时为最坏情况，时间复杂度为O(n2)

public static void subSort(int[] arr, int start, int end) {
    if (start < end) {
        int low = start;
        int high = end;
        int base = arr[start];  // 基准值，取左边第一个
        while (low < high) {
            while (low < high && arr[high] >= base) {
                high--;
            }
            arr[low] = arr[high];   // 当arr[high]小于基准值，就要赋值给arr[left]
            while (low < high && arr[low] <= base) {
                low++;
            }
            arr[high] = arr[low];   // 当arr[low]大于基准值，就要赋值给arr[high]
        }
        arr[low] = base;    // 此时low = high，用基准值来填这个坑
        subSort(arr, start, low - 1);
        subSort(arr, low + 1, end);
    }
}

1. 
   随机生成基准值
2. 
   三数取中法

快速排序最好情况的时间复杂度为O(nlog2n)