75.颜色分类

两天宇宙人

2020-01-11

🥧典型的堆排序题目

class Solution {
public:
    void sortColors(vector<int>& nums) {
        nums.insert(nums.begin(), 0);
        int n = nums.size() - 1;
        for(int i = n / 2; i >= 1; --i) {
            sink(nums, i, n);
        }
        while(n > 1) {
            swap(nums[1], nums[n--]);
            sink(nums, 1, n);
        }
        nums.erase(nums.begin());
    }
    void sink(vector<int>& nums, int k,int n) {
        int j;
        while(k <= n / 2) {
            j = k * 2;
            if(nums[j] < nums[j + 1] && j + 1 <= n) ++j;
            if(nums[k] >= nums[j]) break;
            swap(nums[k], nums[j]);
            k = j;
        }
    }
};