1. 排序思想

与归并排序一样, 快速排序也使用了分治法

1. 分解: 将原问题分解为若干子问题
2. 解决: 解决这些子问题
3. 合并: 将子问题的解合并, 形成原问题的解

快排的思想:

1. 分解:  选取数组中一个数字q, 将数组分为两个部分, 左边是比q小的数字, 右边是比q大的数字
2. 解决:  通过递归调用快速排序, 将左边的数组排列有序,  再将右边的数组排列有序
3. 合并:  没有操作

2. 实现

• Java实现

public static int[] quickSort(int[] arr, int left, int right) {
    if (left < right) {
        int partitionIndex = partition(arr, left, right);//分解成两个子问题
        quickSort(arr, left, partitionIndex - 1); //解决左边
        quickSort(arr, partitionIndex + 1, right); //解决右边
    }
    return arr;
}

//分解过程
private static int partition(int[] arr, int left, int right) {
    //设定基准值 pivot
    int pivot = left; //这里选用第一个数为基准值, 其实选哪个都无所谓
    int lessThanPivot = pivot + 1; //lessThanPivot 左边的(不含)都比基准值小
    for (int i = lessThanPivot; i <= right; i++) {
        if (arr[i] < arr[pivot]) {
            swap(arr, i, lessThanPivot);
            lessThanPivot++;
        }
    }
    swap(arr, pivot, lessThanPivot - 1);
    return lessThanPivot - 1;
}

• 这里在分解的时候, 选择了子序列中最左边的数作为基准值, 其实选择哪个都无所谓, 因为序列本来就是无序的

3. 分析

时间复杂度

• 标题的O(nlogn) 其实是快速排序的平均情况的时间复杂度
• 快速排序真正的最坏情况是O(n²), 但是我们又可以对朴素的快速排序做一些变化使得其很难发生最坏情况
• 快速排序通常是实际排序应用中最好的选择, 因为它平均性能非常好, 期望时间复杂度是 O(nlogn), 并且隐含的常量因子非常小

空间复杂度

• 快速排序是原址排序, 所以空间复杂度是O(1)
• 在虚拟环境中快速排序也能很好的工作

最坏情况

什么时候会出现最坏情况:

1. 所有元素顺序
2. 所有元素倒序
3. 所有元素一样

在上面三种情况下, 这种标准的快速排序算法的时间复杂度会劣化到O(n²), 因为每次分解的时候, 子问题的规模只会缩小一个元素, 最终导致子问题递归到 n 层, 平均每一层的子问题有 n/2 个 最终时间复杂度会是 O(n²)

避免最坏情况

既然已经有了最坏情况的, 我们该怎么解决呢?

这里我给出一个简单的方法:

最朴素的快速排序选择基准值是选择第一个数或者最后一个数

我们可以在这进行优化, 就是在每次选择基准值的时候, 随机进行选择

这样即使整个序列是已经有序或者逆序的情况下, 我们每次分解子问题的时候问题的规模平均都能缩小一半

JDK的做法

• JDK中的快速排序是使用了双轴快速排序, 有效地降低了发生最坏情况的概率 生产应用
• 快速排序虽然理论上的最坏时间复杂度是O(n²), 但是在实际运用中,基本都能通过一些改造避免最坏情况
• 实际上快速排序也是世界上应用的最广泛,最多的排序算法
• 生产中可以放心使用

想要看看快排与其他排序的效率区别可以自己编译执行看看:

https://github.com/vbohush/SortingAlgorithmAnimations