当前位置：首页 > article >正文

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

article 2024/10/26 18:27:26

题目

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

你必须在不使用任何内置函数的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

解法

class Solution {
    int partition(vector<int>& nums, int l, int r) {
        int pivot = nums[r];
        int i = l - 1;
        for (int j = l; j <= r - 1; ++j) {
            if (nums[j] <= pivot) {
                i = i + 1;
                swap(nums[i], nums[j]);
            }
        }
        swap(nums[i + 1], nums[r]);
        return i + 1;
    }
    int randomized_partition(vector<int>& nums, int l, int r) {
        int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
        swap(nums[r], nums[i]);
        return partition(nums, l, r);
    }
    void randomized_quicksort(vector<int>& nums, int l, int r) {
        if (l < r) {
            int pos = randomized_partition(nums, l, r);
            randomized_quicksort(nums, l, pos - 1);
            randomized_quicksort(nums, pos + 1, r);
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        srand((unsigned)time(NULL));
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};

我们通过一个例子来展示快速排序代码中变量的动态变化。假设我们要排序的数组为 nums = [3, 6, 8, 10, 1, 2, 1]。这个数组会通过randomized_quicksort方法进行排序。

初始状态：

nums = [3, 6, 8, 10, 1, 2, 1]
l = 0（左边界）
r = 6（右边界）

步骤 1：调用 `randomized_partition`

randomized_partition 随机选取一个元素作为主元，这里假设随机选择的是 nums[2] = 8，然后将其和最后一个元素交换，nums[r] = 1。交换后的数组为：

nums = [3, 6, 1, 10, 1, 2, 8]（选定的主元 8 被放置到了最后）

接着，调用 partition 方法，对数组进行划分：

pivot = 8（主元）
i = -1（指向小于等于主元的区域的边界）
j = 0 开始遍历数组：
- nums[0] = 3，3 <= 8，i = 0，交换 nums[0] 和 nums[0]（数组不变）。
- nums[1] = 6，6 <= 8，i = 1，交换 nums[1] 和 nums[1]（数组不变）。
- nums[2] = 1，1 <= 8，i = 2，交换 nums[2] 和 nums[2]（数组不变）。
- nums[3] = 10，10 > 8，不做任何操作。
- nums[4] = 1，1 <= 8，i = 3，交换 nums[3] 和 nums[4]，得到 nums = [3, 6, 1, 1, 10, 2, 8]。
- nums[5] = 2，2 <= 8，i = 4，交换 nums[4] 和 nums[5]，得到 nums = [3, 6, 1, 1, 2, 10, 8]。

遍历结束后，i + 1 = 5，交换 nums[5] 和 nums[6]，得到 nums = [3, 6, 1, 1, 2, 8, 10]。返回位置 pos = 5，这意味着主元 8 已经在正确的位置上。

步骤 2：递归调用 `randomized_quicksort`

对左半部分 nums[0...4] = [3, 6, 1, 1, 2] 进行排序：

随机选择主元，假设选择 nums[1] = 6，交换 nums[1] 和 nums[4]，得到 nums = [3, 2, 1, 1, 6, 8, 10]。
进行 partition 操作，最终将主元 6 放置在正确位置，数组变为 nums = [3, 2, 1, 1, 6, 8, 10]，返回位置 pos = 4。

对左半部分 nums[0...3] = [3, 2, 1, 1] 继续排序：

随机选择主元，假设选择 nums[0] = 3，交换 nums[0] 和 nums[3]，得到 nums = [1, 2, 1, 3, 6, 8, 10]。
进行 partition 操作，最终主元 3 放置在正确位置，数组变为 nums = [1, 2, 1, 3, 6, 8, 10]，返回位置 pos = 3。

继续对左右两部分递归，直至完成排序：

对 nums[0...2] = [1, 2, 1] 进行排序，最终得到 nums = [1, 1, 2, 3, 6, 8, 10]。
右半部分 nums[6...6] = [10] 不需再排序。

最终结果：

nums = [1, 1, 2, 3, 6, 8, 10]

变量变化总结：

主元 pivot 不断变化，随机选择后与尾部交换。
变量 i 控制已排序区域，j 遍历数组进行比较。

为什么要把主元放到最后一个？

将主元（pivot）放到最后一个元素的主要原因是方便在快速排序的分区过程中进行比较和交换。以下是一些详细的解释：

简化分区逻辑
在快速排序中，我们需要重新排列数组，使得所有小于或等于主元的元素都在主元的左侧，而所有大于主元的元素都在右侧。将主元放到最后一个位置后，我们可以通过一个简单的遍历将数组分成两个部分，这样做能够简化比较逻辑。
便于交换
在分区过程中，使用最后一个元素作为主元可以使我们在进行元素交换时更加方便。我们可以在遍历过程中保持一个指针 i，该指针表示小于等于主元的元素的边界。每当我们找到一个小于或等于主元的元素时，就将其与 i 指向的元素交换。遍历完成后，只需将主元与 i 后面的元素交换，最终主元就会处于其正确的位置。
直观的结束条件
将主元放到数组的最后一个位置，使得我们可以轻松地使用 j 指针遍历数组。在遍历结束后，主元的最终位置可以直接通过指针的计算得出。
避免主元干扰
在分区过程中，主元作为一个特殊的元素，其位置在排序过程中不应受到影响。将主元置于最后一位，能够避免在比较和交换时对其产生干扰。