912. 排序数组（快速排序）

912. 排序数组 #

链接 #

912. 排序数组

题目 #

给你一个整数数组 nums，请你将该数组升序排列。

示例 1：

输入：nums = [5,2,3,1]
输出：[1,2,3,5]

示例 2：

输入：nums = [5,1,1,2,0,0]
输出：[0,0,1,1,2,5]

提示：

  • 1 <= nums.length <= 5 * 104
  • -5 * 104 <= nums[i] <= 5 * 104

解答 #

快速排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        qsortRange(nums, 0, nums.size() - 1);
        return nums;
    }

    void qsortRange(vector<int>& nums, int l, int r) {
        if (l >= r) {
            return;
        }

        int i = l, j = r;
        int x = nums[(l + r) / 2]; // Pivot is the middle element

        do {
            while (nums[i] < x) i++;
            while (nums[j] > x) j--;

            if (i <= j) {
                swap(nums[i], nums[j]);
                i++;
                j--;
            }
        } while (i <= j);

        qsortRange(nums, l, j);
        qsortRange(nums, i, r);
    }
};

这段代码实现的是快速排序（Quick Sort）算法，用于对一个整数数组进行排序。快速排序是一种高效的排序算法，采用分而治之的策略，平均时间复杂度为 (O(n \log n))。

下面通过一个具体的例子来解释这段代码的工作原理：

假设有一个数组 nums = [3, 6, 8, 4, 1, 2, 1]，我们希望调用 sortArray 函数对其进行排序。

  1. 初始化调用：sortArray(nums) 被调用，它又调用 qsortRange(nums, 0, 6)（因为数组的大小为 7，索引从 0 到 6）。

  2. 选择基准值：在 qsortRange 函数内部，首先选择数组中间的值作为基准值 x，这里是 nums[(0+6) >> 1] = nums[3] = 10。

  3. 分区操作：

    • 初始化两个指针 i = l - 1 = -1 和 j = r + 1 = 7。
    • 进入循环，不断移动 i 和 j，直到 i 指向的元素大于等于 x，j 指向的元素小于等于 x，然后交换这两个元素的位置。这个过程会不断重复，直到 i >= j，此时所有小于 x 的元素都会被移动到 x 的左边，所有大于 x 的元素都会被移动到 x 的右边。
    • 在这个例子中，10 作为基准值，分区操作后，数组可能被重新排列为 [3, 6, 8, 1, 1, 2, 10]，j 此时指向第一个 10 的位置，即索引 6。

  4. 递归排序：

    • 接下来，qsortRange 会递归地对基准值左边的数组 [3, 6, 8, 1, 1, 2] 和右边的数组（这个例子中右边没有元素）进行排序。
    • 对于左边的数组，过程会重复：选择基准值、分区、递归排序，直到数组被完全排序。

  5. 完成排序：递归过程持续进行，最终整个数组变成有序状态。

代码解释：

  • qsortRange 函数是快速排序的核心，它接受四个参数：要排序的数组 nums 和子数组的起止索引 l、r。
  • 如果 l >= r，说明子数组不需要排序（已经是有序的或者只有一个元素），直接返回。
  • i、j 用于遍历数组，x 是基准值。
  • 通过不断交换元素，将小于基准值的元素移动到基准值的左边，将大于基准值的元素移动到基准值的右边。
  • 递归地对基准值左右两侧的子数组进行相同的操作，直到整个数组排序完成。

这段代码通过快速排序算法实现了对一个整数数组的排序，展示了快速排序的高效和实用性。

以数组 nums = [3, 6, 8, 4, 1, 2, 1] 为例，我们将通过快速排序的过程来简短地说明如何对其进行排序。我们从最初的调用 qsortRange(nums, 0, 6) 开始。

  1. 第一次分区：

    • 基准值 x = nums[(0+6) >> 1] = nums[3] = 4。
    • 分区结束后，可能的一个结果是：[3, 1, 2, 1, 4, 6, 8]，其中基准值 4 现在位于正确的排序位置。
    • 接下来对左边的 [3, 1, 2, 1] 和右边的 [6, 8] 进行递归排序。

  2. 左侧 [3, 1, 2, 1] 的排序：

    • 选择基准值 x = nums[(0+3) >> 1] = 1。
    • 分区操作可能会使数组保持不变（因为所有元素都已经满足以 1 为基准的分区条件），但递归会继续处理更小的子数组。
    • 继续递归，直到所有子数组都被正确排序。

  3. 右侧 [6, 8] 的排序：

    • 选择基准值 x = nums[(0+1) >> 1] = 6（假设这是在其局部索引下的操作）。
    • 分区后数组可能保持不变，因为 6 和 8 已经是有序的。
    • 递归继续，但很快就会因为子数组的大小而停止。

通过上述过程，整个数组最终会被排序为 [1, 1, 2, 3, 4, 6, 8]。

注意：快速排序的具体步骤（特别是分区后的数组状态）可能会根据不同的基准值选择和分区策略有所不同，但最终结果是一致的——得到一个有序数组。

基于这个算法怎么找到第 k 大元素 #

要找到数组中第二大的元素，我们可以稍微修改快速排序的过程，特别是在分区步骤后，利用快速选择（Quick Select）算法的思想。快速选择算法是快速排序算法的一个变种，用于在未完全排序的数组中找到第 (k) 小（或第 (k) 大）的元素，其平均时间复杂度也是 (O(n))。

以下是如何基于快速排序算法找到数组中第二大元素的步骤：

  1. 选择基准值：与快速排序一样，选择一个元素作为基准值。

  2. 分区：进行一次分区操作，将小于基准值的元素放到基准值的左边，将大于基准值的元素放到基准值的右边。

  3. 利用分区结果：

    • 如果基准值的最终位置正好是倒数第二个（即，只有一个元素比它大），那么这个基准值就是第二大的元素。
    • 如果基准值的最终位置大于倒数第二个，说明第二大的元素在基准值的左侧，我们可以在左侧继续进行快速选择。
    • 如果基准值的最终位置小于倒数第二个，说明第二大的元素在基准值的右侧，我们可以在右侧继续进行快速选择。

  4. 递归：根据上一步的结果，递归地在基准值的左侧或右侧进行快速选择，直到找到第二大的元素。

Edit Edit this page