跳转至

912 排序数组

堆排序

class Solution {
private:
    void heapify(vector<int>& nums, int u, int heapSize) {
        int smallest = u;
        int l = 2 * u + 1, r = 2 * u + 2;
        if (l < heapSize && nums[l] < nums[smallest])
            smallest = l;
        if (r < heapSize && nums[r] < nums[smallest])
            smallest = r;
        if (smallest != u) {
            swap(nums[smallest], nums[u]);
            heapify(nums, smallest, heapSize);
        }
    }
    void buildMinHeap(vector<int>& nums, int heapSize) {
        for (int i = nums.size() / 2; i >= 0; i--)
            heapify(nums, i, heapSize);
    }

public:
    vector<int> sortArray(vector<int>& nums) {
        vector<int> ans;
        int heapSize = nums.size();
        buildMinHeap(nums, heapSize);
        for (int i = heapSize - 1; i >= 0; i--) {
            ans.push_back(nums[0]);
            swap(nums[0], nums[i]);
            heapify(nums, 0, i);
        }
        return ans;
    }
};

归并排序

class Solution {
private:
    vector<int> tmp;
    void mergeSort(vector<int>& nums,int l,int r){
        if(l < r){
            int mid = (l + r)>> 1;
            mergeSort(nums,l,mid);
            mergeSort(nums,mid+ 1,r);
            int cnt = 0;
            int i = l, j = mid + 1;
            while(i <= mid && j <= r){
                if(nums[i] <= nums[j])
                    tmp[cnt++] = nums[i++];
                else
                    tmp[cnt++] = nums[j++];
            }
            while(i <= mid)
                tmp[cnt++] = nums[i++];
            while(j <= r)
                tmp[cnt++] = nums[j++];
            for(int i = 0; i < r - l + 1;i++)
                nums[l+i] = tmp[i];
        }
    }
public:
    vector<int> sortArray(vector<int>& nums) {
        tmp.resize(nums.size(),0);
        mergeSort(nums,0,nums.size() - 1);
        return nums;
    }
};

快速排序

class Solution {
private:
    void quickSort(vector<int>& nums, int l, int r) {
        // 注意是l < r
        if (l < r) {
            int idx = l + rand() % (r - l + 1);
            int pivot = nums[idx];
            int i = l - 1, j = r + 1;
            while (i < j) {
                do
                    i++;
                while (nums[i] < pivot);
                do
                    j--;
                while (nums[j] > pivot);
                if(i < j)
                    swap(nums[i],nums[j]);
            }
            // 因为是 l < r 所以这里是quickSort(nums, l, j)而不是quickSort(nums, l, j - 1)
            quickSort(nums, l, j);
            quickSort(nums, j + 1, r);
        }
    }

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