数据结构与算法-快速排序

 以下代码是作者本人，在idea里验证过的，核心代码主要就是原地完成排序并获取中间值的下标，有两种方法来实现请参考ge tMid()与getMid2()两个方法，第一种方法更容易理解，但不优雅，第二种理解起来困难些，但是代码看起来更优雅。

快速排序是时间复杂度是O(nlogn)，空间复杂度O(1)，但是不是稳定的排序算法。

相同的元素在使用快速排序后原来的循环可能会发生改变。

 /**
     * 快速排序
     * @param arr 数组
     * @param left 数组左下标
     * @param right 数组右下标
     */
    private static void quickSort(Integer[] arr, int left, int right){
        if (left >= right) {
            return;
        }
        // 排序并获取中间值（基准值）的下标
//        int mid = getMid(arr, left, right);
        int mid = getMid2(arr, left, right);
        // 递归排序左边的区间，注意：最后一位参数不能写成mid，否则会死循环
        quickSort(arr, left, mid - 1);
        // 递归排序右边的区间，中间的参数不能写为mid，否则会死循环
        quickSort(arr, mid + 1, right);

    }

    /**
     * 查到基准下标（此过程中涉及重新排序）
     * @param arr 数组
     * @param left 数组左下标
     * @param right 数组右下标
     * @return 中值下标
     */
    private static int getMid(Integer[] arr, int left, int right) {
        int base = arr[left];
        while (left < right){
            // 从最右边开始查找小于基准点点值，如没有就将最右边的下标减1
            // （注意：判断条件必须是包含等于，否吃会死循环，因此快速排序不能保证两个等值的元素，排完循序后还保持原有循序，不是稳定的排序算法）
            while (left < right && arr[right] >= base) {
                right--;
            }
            // 找到小于基准点点值后交换
            arr[left] = arr[right];
            // 从左边开始查找大于基准值的元素，没有就将下标加1
            while (left < right && arr[left] <= base){
                left++;
            }
            // 找到大于基准点的值后交换
            arr[right] = arr[left];
        }
        // 最后将原来的基准值填充回来，此时的left就是基准值的下标（注意：left经过++操作已经不是原来的下标值了）
        arr[left] = base;
        return left;
    }


    /**
     * 巧妙使用数组下标排序并获取中间值（基准值）下标
     * @param arr 数组
     * @param left 左下标
     * @param right 右下标
     * @return 中值下标
     */
    private static int getMid2(Integer[] arr, int left, int right){
        int i = left;
        int pivot = arr[right];
        for (int j = left; j < right; j++) {
            if (arr[j] < pivot) {
                int temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
                i++;
            }
        }
        int temp = arr[i];
        arr[i] = arr[right];
        arr[right] = temp;
        return i;
    }