快速排序算法（leetcode题解分析）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
    // partition函数：
    // 在进行分区操作时，需要维护两个指针i,j
    // i指向小于pivot的最后一个元素；j指向当前正在处理的元素
    // i的初始值l-1，这意味着当第一次迭代时，如果 nums[j] <= pivot，我们将会交换 nums[i+1] 和 nums[j]，并将 i 加 1
    // 这样，在第一次迭代之后，i 的值就变成了 l
    // 之后，每当 nums[j] <= pivot 时，i 的值都会加 1。
    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); 
        // partition函数将数值进行分区（按照大小将数据放到基准位两侧）
    }
    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)); // 随机数发生器的初始化函数、后面使用了rand()
        randomized_quicksort(nums, 0, (int)nums.size() - 1);
        return nums;
    }
};