LeetCode912 排序数组-快速排序存档

链接

https://leetcode-cn.com/problems/sort-an-array/

题意

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

解法

快速排序，选定主元的时候需要进行随机化选取
如果一直选择第一个元素可能会导致复杂度退化

代码

class Solution {
public:
    void print(vector<int>& a) {
        for (int i: a) {
            cout << i << ' ';
        }
        cout << endl;
    }

    int partition(vector<int> &a, int start, int end) {
        swap(a[start], a[end]);
        int small = start;
        for (int i = start; i < end; i++) {
            if (a[i] < a[end]) {
                swap(a[i], a[small]);
                small++;
            }
        }
        swap(a[small], a[end]);
        // 保证small左边的数都小于samll 右边的数都大于small
        return small;
    }

    void quick_sort(vector<int>& a, int start, int end) {
        if (end <= start) return;
        int pivot = rand() % (end - start + 1) + start; // 随机选择一个主元和start交换
        // 避免复杂度退化
        swap(a[start], a[pivot]);
        int index = partition(a, start, end);
        quick_sort(a, start, index - 1);
        quick_sort(a, index + 1, end);
    }
    vector<int> sortArray(vector<int>& nums) {
        quick_sort(nums, 0, nums.size() - 1);
        cout << nums.size() << endl;
        return nums;
    }
};