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

解答 #

三路划分是快速排序中的一种优化技术，特别适用于处理包含大量重复元素的数组。其基本思想是将数组分成三个部分：小于基准值的元素、等于基准值的元素、以及大于基准值的元素。这样做的好处是可以在排序过程中跳过所有等于基准值的元素，从而减少不必要的比较和交换，提高算法效率。

#include <vector>
using namespace std;

class Solution {
public:
    void quickSort(vector<int>& nums, int l, int r) {
        if (l >= r) return;

        int i = l, j = r, p = nums[(l + r) >> 1], e = l;

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

        quickSort(nums, l, i - 1);
        quickSort(nums, j + 1, r);
    }

    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
};

这个代码并不是特别直观，所以解释一下：

  1. 我们选择中点或任意一个元素作为基准值 pivot。
  2. 我们使用指针 i、j 界定小于和大于 pivot 的元素。中间是尚未处理的元素。
  3. 用 e 表示当前正在处理的元素。让 e 遍历 i 到 j 之间的元素。
    1. 如果当前值小于 pivot，我们将其交换到左边。然后

可根据下面的幻灯片理解：

Edit Edit this page