快速排序算法思路

从小到大排序时

快速排序算法原理：
快速排序利用了分治的思想，采用递归来实现
如果要排序一个数组，先取一个参照数（这里取数组最后一个数作为参照）把数组从分成以参数为”中间“结点的前后2部分，数组中参照数之前的都小于参照数，参照数之后的都大于参照数,
然后，对参照数的前后两部分分别排序 这样整个数组就有序了。

递推公式：

1. quickSort(p,r) = partition(p,r)+quickSortCore(p,q-1)+quickSortCore(q+1,r);
2. q = partition(p,r);
3. 终止条件：p>=r 不用继续分解
4. p: 每段的起始下标
5. r: 每段的末尾下标
6. q: 每段的"中间"下标

• 最好情况下
• 最坏情况下
  

时间复杂度：O(N*logN) ~ O($n^2$)

1. 快速排序算法的耗时是在拆分这里(partition)，通过上图可以看出是个完全二叉树，当n规模足够大时就可以近似看成是满二叉树，由partition函数来看合并的时间复杂度是O(n)

• 最好情况下 O(nlogn)：即拆分时左右2部分均分，时间复杂度由上图可知每层处理的数据规模都是n 假设每层耗时常量t 树高为h,那么总耗时=n*t*h, T(n) = n*t*${\log }_{2}n$ (参考:完全二叉树的树高H和结点数N的关系)
• 最坏情况下 O($n^2$)：即当数组数据已经有序时例如{1,2,3,4,5},此时无法均分,取5为参照数,每次就只会执行quickSortCore(p,q-1)方法,partition处理的数据规模就是每次:T(n) = (n+n-1+ …1)*t = t*n*(n-1)/2 (t指单个数据处理耗时,是个常量值,n指数据规模)

空间复杂度：O(logn)~O($n$)，快速排序虽然没有申请额外的空间,但是有递归函数调用栈的内存消耗。

• 最好情况下 O(logn)：即拆分时左右2部分均分时树深度最深也就是树的高度可表示${\log }_{2}n$。
• 最坏情况下 O($n$)：即当数组数据已经有序时例如{1,2,3,4,5},此时无法均分,取5为参照数,每次就只会执行quickSortCore(p,q-1)方法一直往下递归

快速排序是不稳定的排序算法。 例如{6,8,7,6,3,5,9,4},取末尾4为参照数,拆分时,当下标j=4指向数3时 此时下标i=-1,r=7 ,arr[j] < arr[r] 进入交换导致第一个6在第二个6的后面顺序发生改变。

总结:快速排序算法时间复杂度：O(N*logN) ~ O($n^2$), 空间复杂度：O(logn) ~ O($n$),该算法可以进行进一步优化：出发点就是尽量使其每次左右均分数据规模

一、核心代码

private static int[] quickSort(int[] arr) {
        if (null != arr && arr.length > 0) {
            quickSortCore(arr, 0, arr.length - 1);
        }
        return arr;
    }

    private static void quickSortCore(int[] arr, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = partition(arr, p, r);
        quickSortCore(arr, p, q - 1);
        quickSortCore(arr, q + 1, r);
    }

    /**
     * [p,i] 小于 arr[r]的区域
     * [i+1,j-1] 大于 arr[r]的区域
     * [j,r-1]  未处理的区域
     * r 下标默认是分区点参照的元素
     * p,j,i,r 均指下标,arr[r]指参照数
     *
     * @param arr
     * @param p
     * @param r
     * @return
     */
    private static int partition(int[] arr, int p, int r) {
        // 初始时设置i= -1,表示小于参照数的区域是空,i标识小于参照数的区域末尾位置
        int i = p - 1;
        // 扫描未处理区域和挨个和参照数进行比较
        for (int j = p; j < r; j++) {
            // 比参照数小的放到[p,i]区域,[p,i]区域就开始扩大了
            if (arr[j] < arr[r]) {
                swap(arr, i + 1, j);
                i++;
            }
        }
        // 再把参照数放到比它小的区域的后一个下标位置,这样 参照数左侧就是全部小于参照数的数，右侧就是大于参照数的数，可以继续往下拆分左右2侧递归了
        swap(arr, i + 1, r);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

二、测试用例

package arithmetic.ecut.com.排序.a_快速排序;

/**
 * 快速排序
 *
 * @author 起凤
 * @description: TODO
 * @date 2022/4/11
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {1, 5, 6, 2, 3, 4};
        print(quickSort(arr));

        int[] arr1 = {2, 3, 1, 4, -1, 8, -1};
        print(quickSort(arr1));

        int[] arr2 = {-1, 7, 1, 4, 5, 8, 7};
        print(quickSort(arr2));
    }

    private static int[] quickSort(int[] arr) {
        if (null != arr && arr.length > 0) {
            quickSortCore(arr, 0, arr.length - 1);
        }
        return arr;
    }

    private static void quickSortCore(int[] arr, int p, int r) {
        if (p >= r) {
            return;
        }
        int q = partition(arr, p, r);
        quickSortCore(arr, p, q - 1);
        quickSortCore(arr, q + 1, r);
    }

    /**
     * [p,i] 小于 arr[r]的区域
     * [i+1,j-1] 大于 arr[r]的区域
     * [j,r-1]  未处理的区域
     * r 下标默认是分区点参照的元素
     * p,j,i,r 均指下标,arr[r]指参照数
     *
     * @param arr
     * @param p
     * @param r
     * @return
     */
    private static int partition(int[] arr, int p, int r) {
        // 初始时设置i= -1,表示小于参照数的区域是空,i标识小于参照数的区域末尾位置
        int i = p - 1;
        // 扫描未处理区域和挨个和参照数进行比较
        for (int j = p; j < r; j++) {
            // 比参照数小的放到[p,i]区域,[p,i]区域就开始扩大了
            if (arr[j] < arr[r]) {
                swap(arr, i + 1, j);
                i++;
            }
        }
        // 再把参照数放到比它小的区域的后一个下标位置,这样 参照数左侧就是全部小于参照数的数，右侧就是大于参照数的数，可以继续往下拆分左右2侧递归了
        swap(arr, i + 1, r);
        return i + 1;
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void print(int[] sort) {
        StringBuilder builder = new StringBuilder();
        for (int i = 0; i < sort.length; i++) {
            builder.append(sort[i]).append(",");
        }
        System.out.println(builder);
    }

}

参考资料

• 极客时间专栏-数据结构与算法之美
• 完全二叉树的高度为什么是对lgN向下取整
• Markdown/LaTeX数学符号-公式大全