LeetCode #912：Sort an Array(排序数组)

题目描述

题意基本上就是把 “默写快排” 四个大字给拍脸上了，调用标准库的 sort 在面试中肯定是没分的【手动狗头
需要注意的是测试用例中存在有序的长数组，如果直接取第一个元素作为快排的枢轴会超时，这里我在每次划分的时候取区间中间的元素作为枢轴来避免超时。

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

private:
    void qSort(vector<int>& nums, int low, int high) {
        if(low < high) {
            int p = partition(nums, low, high);
            qSort(nums, low, p - 1);
            qSort(nums, p + 1, high);
        }
    }

    int partition(vector<int>& nums, int low, int high) {
        swap(nums[low], nums[(low + high) / 2]); //选择中间的元素作为枢轴，避免有序长数组的Test Case超时
        int temp = nums[low];
        while(low < high) {
            while(low < high && nums[high] >= temp) high--;
            swap(nums[low], nums[high]);
            while(low < high && nums[low] <= temp) low++;
            swap(nums[low], nums[high]);
        }
        nums[low] = temp;
        return low;
    }
};

2023 年更新：数据经过了加强，上面的代码已经不能 AC 了，下面补一份堆排序的版本：

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        int n = nums.size();

        vector<int> heap(n + 1, 0);

        for(int i = 0; i < n; i ++) {
            heap[i + 1] = nums[i];
        }
        heap[0] = n; // 堆数组的第0号元素存放堆的大小

        // 自底向上构建堆
        for(int i = n / 2; i > 0; i --) {
            down(i, heap);
        }

        for(int i = 0; i < n; i ++) {
            nums[i] = heap[1];
            heap[1] = heap[heap[0] --]; // 删除堆顶元素，即用堆的最后一个元素替换堆顶并使得堆大小减一
            down(1, heap); // 将新的堆顶元素下沉
        }

        return nums;
    }

    void down(int i, vector<int>& heap) {
        int p = i;

        if(i * 2 <= heap[0] && heap[p] > heap[i * 2]) {
            p = i * 2;
        }
        if(i * 2 + 1 <= heap[0] && heap[p] > heap[i * 2 + 1]) {
            p = i * 2 + 1;
        }

        if(p != i) {
            swap(heap[p], heap[i]);
            down(p, heap);
        }
    }
};

用归并排序也能过，代码如下：

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

    void mergeSort(vector<int>& nums, int l, int r) {
        if(l >= r) {
            return;
        }
        int mid = l + r >> 1;
        mergeSort(nums, l, mid);
        mergeSort(nums, mid + 1, r);
        
        int i = l;
        int j = mid + 1;
        int k = 0;
        int temp[50010];

        while(i <= mid && j <= r) {
            if(nums[i] < nums[j]) {
                temp[k ++] = nums[i ++];
            } else {
                temp[k ++] = nums[j ++];
            }
        }
        while(i <= mid) {
            temp[k ++] = nums[i ++];
        }
        while(j <= r) {
            temp[k ++] = nums[j ++];
        }
        for(i = l, j = 0; i <= r; i ++, j ++) {
            nums[i] = temp[j];
        }
    }
};