我们从二叉树的角度来谈谈快速排序算法的原理和应用

趁热打铁今天我们继续用二叉树的角度来谈谈快速排序算法的原理和应用。 ？一句话概括了归并排序：先对数组的左半部分进行排序，然后对数组的右半部分进行排序，然后将数组的两半部分合并。

同时问了一个问题，让你用一句话总结一下快速排序。我的答案是：

快速排序是指先对一个元素进行排序，然后对其余元素进行排序。

为什么这么说？我慢慢告诉你。

快速排序的核心无疑是功能配送。 partition的功能是找到nums[lo..hello]

,p nums[lo]中的分区点..p- 1] 小于或等于 nums

和 nums

所有元素 Pu 都大于 Pu 及其左侧的元素元素更小并且右边的元素都比它大。这是什么意思？不就是放在了正确的位置吗？

函数分区实际上对元素nums

进行排序。

元素已排序，接下来做什么？您可以轻松排列其余元素。

剩下的元素是什么？左一团，右一团，继续，返回子数组，使用函数partition对剩余元素进行排序。

从二叉树的角度来看，我们可以将子域nums [lo..hi]理解为二叉树节点处的值，将函数srot理解为二叉树的转换函数。

关于二叉树先序遍历序列，下面的GIF正在运行快速排序过程：

你注意到最终的二叉树是什么了吗？这是一棵二叉搜索树：

这应该不难理解，因为函数partition将数组分成左小右大两部分，就像二叉搜索树左小右大一样特征匹配。

你也可以这样理解：快速排序的过程就是构建二叉搜索树的过程。

但是说到构建二叉搜索树，就不得不说一下不平衡二叉搜索树的极端情况。在极端情况下，二叉搜索树会退化为链表，从而导致运行效率大幅降低。

在快速排序过程中也有类似的情况。例如，在我画的图中，函数 partition 选择的分割点可能始终是 nums [lo..hi] 将其分割成两半，但实际上你可能不会真幸运。

如果每次都很倒霉，一侧的元素很少，就会导致二叉树生长不平衡：

这种情况下，时间复杂度会显着增加。我们稍后将更详细地讨论时间要求。解释。

为了避免这种极端情况，我们需要引入随机性。

常见的做法是在排序之前对整个数组进行洗牌算法，或者在函数partition中随机选择数组元素作为分割点。本文将使用其中的第一个。

快速排序代码实现

理解了上面的概念，我们直接看快速排序代码实现：

class Quick {

    public static void sort(int[] nums) {
        // 为了避免出现耗时的极端情况，先随机打乱
        shuffle(nums);
        // 排序整个数组（原地修改）
        sort(nums, 0, nums.length - 1);
    }

    private static void sort(int[] nums, int lo, int hi) {
        if (lo >= hi) {
            return;
        }
        // 对 nums[lo..hi] 进行切分
        // 使得 nums[lo..p-1] <= nums
 < nums

        int p = partition(nums, lo, hi);

        sort(nums, lo, p - 1);
        sort(nums, p + 1, hi);
    }

    // 对 nums[lo..hi] 进行切分
    private static int partition(int[] nums, int lo, int hi) {
        int pivot = nums[lo];
        // 关于区间的边界控制需格外小心，稍有不慎就会出错
        // 我这里把 i, j 定义为开区间，同时定义：
        // [lo, i) <= pivot；(j, hi] > pivot
        // 之后都要正确维护这个边界区间的定义
        int i = lo + 1, j = hi;
        // 当 i > j 时结束循环，以保证区间 [lo, hi] 都被覆盖
        while (i <= j) {
            while (i < hi && nums[i] <= pivot) {
                i++;
                // 此 while 结束时恰好 nums[i] > pivot
            }
            while (j > lo && nums[j] > pivot) {
                j--;
                // 此 while 结束时恰好 nums[j] <= pivot
            }
            // 此时 [lo, i) <= pivot && (j, hi] > pivot

            if (i >= j) {
                break;
            }
            swap(nums, i, j);
        }
        // 将 pivot 放到合适的位置，即 pivot 左边元素较小，右边元素较大
        swap(nums, lo, j);
        return j;
    }

    // 洗牌算法，将输入的数组随机打乱
    private static void shuffle(int[] nums) {
        Random rand = new Random();
        int n = nums.length;
        for (int i = 0 ; i < n; i++) {
            // 生成 [i, n - 1] 的随机数
            int r = i + rand.nextInt(n - i);
            swap(nums, i, r);
        }
    }

    // 原地交换数组中的两个元素
    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}

这里是基本功能节二分查找框架的详细讲解中的实现，正确找到分割点将测试您对边界条件的控制。一个小错误就会导致不正确的结果。

处理边界细节的一个技巧是，您需要明确定义每个变量的定义以及区间的开始和结束。具体细节请看代码注释。建议单独练习。

接下来我们来分析一下快速排序的时间复杂度。

很明显，快速排序的时间复杂度主要消耗在函数split上，因为这个函数中有一个循环。

那么 division 该函数执行了多少次？每次实施需要多长时间？总体时间复杂度是多少？

与归并排序类似。应该根据之前画的图来整体分析：

section 执行次数就是二叉树的节点数，每次执行的复杂度就是每个节点表示的长度子数组 nums[lo..hi] ，因此总时间复杂度是整棵树 中“数组元素”的数量。

假设数组元素个数为N，则二叉树各层元素个数之和为O(N);O(N) ;在理想情况下，当分裂点均匀分布时，树的层数为O(logN)，所以理想的总时间复杂度为O( NlogN)。

由于快速排序没有使用辅助数组，空间复杂度就是递归栈的深度，也就是树的高度O(logN)。

当然，我们已经说过，快速排序的有效性存在一定程度的随机性。如果每个分区的结果极不均匀：

快速排序退化为选择排序，树高度为O(N)。每个节点层的元素数量从N开始减少。总时间复杂度为：

N + (N - 1) + (N - 2) + ... + 1 = O(N^2)

所以我们说快速排序的理想状态是 时间复杂度为O(NlogN)，空间复杂度为,O(logN) 最差的时间复杂度是极端情况下的复杂度为O(N^2)，空间复杂度为O(N)。

不过不用担心，随机分区的功能不太可能出现极端情况，所以快速排序的效率还是很高的。

还有一点需要注意的是，快速排序是一种“不稳定排序”。相比之下，上面提到的归并排序是一种“稳定排序”。

对于序列中的相同元素，如果排序后它们的相互位置不变，则该排序算法称为“稳定排序”，反之称为“不稳定排序”。

如果只对int数组进行排序，稳定性就没有任何意义。但如果对一些结构比较复杂的数据进行排序，那么按稳定性排序就有更大的优势。

例如，您有一些已按订单号排序的订单数据。现在你想对订单的交易日期进行排序：

如果你使用稳定的排序算法（例如合并排序），那么这些订单将不仅仅按交易日期排序，还会按具有相同交易的订单的订单号排序日期仍按顺序排列。

但是，如果使用不稳定的排序算法（例如快速排序），那么即使排序结果按照交易日期排序，订单号与交易日期相同的订单也会出现乱序。

在实际项目中，我们经常会使用某个复杂对象的某个字段作为排序键，所以要注意一下API提供的API底层使用的是哪种排序算法编程语言以及它是否稳定。不稳定，很可能会影响代码执行的效率甚至正确性。

说了这么多，快速排序算法应该解释清楚了。问题 912 “排序数组”允许您对数组进行排序。我们可以直接使用快速排序代码模板：

class Solution {
    public int[] sortArray(int[] nums) {
        // 归并排序对数组进行原地排序
        Quick.sort(nums);
        return nums;
    }
}

class Quick {
    // 见上文
}

快速排序算法

不仅快速排序算法本身很有趣，而且它还有几个有趣的变体，其中最著名的就是快速排序算法。

215.问题“数组中的第K大元素”是一个类似的问题。函数签名如下：

int findKthLargest(int[] nums, int k);

这道题要求我们找到第第k最大元素，有点绕口k❙意思是找到数组之后的元素

nums

例如，输入 nums = [2,1,5,4], k = 2，算法应返回 4，因为 4 是最大的 2。 P 中的❙tin元素。

这个问题有两种解决方案，一种是二叉堆解决方案（优先级队列），另一种是快速选择算法。让我们分别看看它们。

二叉堆的解决方案比较简单，但是时间要求有点高，直接看代码即可：

int findKthLargest(int[] nums, int k) {
    // 小顶堆，堆顶是最小元素
    PriorityQueue<Integer> 
        pq = new PriorityQueue<>();
    for (int e : nums) {
        // 每个元素都要过一遍二叉堆
        pq.offer(e);
        // 堆中元素多于 k 个时，删除堆顶元素
        if (pq.size() > k) {
            pq.poll();
        }
    }
    // pq 中剩下的是 nums 中 k 个最大元素，
    // 堆顶是最小的那个，即第 k 个最大元素
    return pq.peek();
}

二叉堆（优先级队列）是一种可以自动排序的数据结构，我们后面有一步一步的指导 二叉堆数据结构的实现 实现了这个结构之后，我想大家都知道它的特点了。

基本思想是将顶部的小堆pq视为筛子，较大的元素将沉降，较小的元素将漂浮到顶部；当堆大小超过k时间时，我们删除堆顶部的元素，因为这些元素相对较小，我们希望第一个k成为最大的元素。

当nums中的所有元素都通过后，堆中最大的k元素和最小的元素将保留在筛子中。所以“k最大元素”。

这个想法非常简单。唯一需要注意的是，Java 的默认实现​​PriorityQueue 是一个小顶堆。某些语言的优先级队列默认情况下可能有很大的顶堆，可能需要进行一些调整。

二叉堆中插入和删除元素所需的时间与堆中元素的数量有关。这里我们的堆大小不会超过k，所以插入和移除元素的复杂度是O(logk)然后设置for循环。假设数组元素总数为N，则总时间复杂度为O(Nlogk)。

该解决方案的空间复杂度显然是二叉堆的大小，即O(k)。

快速选择算法是快速排序的变体，效率更高。如果能在面试中写出快速选择算法，那绝对是加分项。

首先，题目问“k最大元素”，相当于对尾部数组排序后“按n - k排序的元素”。为了便于表达，下面的文字Also k' = n - k。

如何知道“分配给k'的元素”？其实你可以在执行快速排序算法函数distribution的时候查看。

我们刚才说了，函数partition会将nums

放在正确的位置，所以.❀nums【nums】nums

：

在此此时，虽然整个数组没有排序，但我们已经让nums

左边的元素小于nums，所以知道nums

是排名的。

然后我们可以将 ​​p 与 k' 进行比较，如果 p❙›❙›› 大元素 V nums

，如果 p > k' 表示最大元素 k'❙] lo[1]... 。

接下来前往nums

可以进一步缩小排名。元素范围k'最终找到目标元素。

您可以这样编写解决方案代码：

int findKthLargest(int[] nums, int k) {
    // 首先随机打乱数组
    shuffle(nums);
    int lo = 0, hi = nums.length - 1;
    // 转化成「排名第 k 的元素」
    k = nums.length - k;
    while (lo <= hi) {
        // 在 nums[lo..hi] 中选一个分界点
        int p = partition(nums, lo, hi);
        if (p < k) {
            // 第 k 大的元素在 nums
 中
            lo = p + 1;
        } else if (p > k) {
            // 第 k 大的元素在 nums[lo..p-1] 中
            hi = p - 1;
        } else {
            // 找到第 k 大元素
            return nums
;
        }
    }
    return -1;
}


// 对 nums[lo..hi] 进行切分
int partition(int[] nums, int lo, int hi) {
    // 见前文
}

// 洗牌算法，将输入的数组随机打乱
void shuffle(int[] nums) {
    // 见前文
}

// 原地交换数组中的两个元素
void swap(int[] nums, int i, int j) {
    // 见前文
}

这个代码框架实际上与我们之前的二分搜索框架代码非常相似。这也是这个算法高效的原因，但是为什么时间复杂度是O(N)呢？

显然，这个算法的时间复杂度也主要集中在函数partition上。我们需要估计函数部分已经执行了多少次以及每次执行需要多长时间。 。在最好的情况下，每个函数 TimePartition 切割 P 恰好是中间索引 (LO + Hi) / 2（两个点），并且在每个光束向左或向右分裂后，继续除法，则函数division的执行次数为logN，每次数组输入的大小减半。

因此，总时间复杂度为：

# 等差数列
N + N/2 + N/4 + N/8 + ... + 1 = 2N = O(N)

当然，与快速排序类似，快速选择算法中的函数分布也可能出现极端情况。在最坏的情况下，p 始终为 lo + 1，或者始终为 hi - 1。这样的话，时间复杂度就降低为O(N^2)：

N + (N - 1) + (N - 2) + ... + 1 = O(N^2)

这也是我们在代码中使用函数shuffle的原因通过引入随机性，我们可以避免极端情况，使算法的效率保持在较高水平。随机化后的快速选择算法的复杂度可以认为是O(N)。

至此，我们就讲完了快速排序算法和快速选择算法。从二叉树的角度理解这个想法应该不难，但是函数split需要你更加关注细节。理解和记忆。