[LC]912.排序数组

题目

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

你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。

分析

堆排序

代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        buildHeap(nums);
        int n = nums.size();
        for (int i = 0; i < n - 1; ++i)
        {
            swap(nums[0], nums[n - 1 - i]);
            heapAdjust(nums, 0, n - 1 - i);
        }
        return nums;
    }
    void heapAdjust(vector<int> &nums, int k, int n)
    {
        int i = left(k);
        while (i < n)
        {
            if (i + 1 < n && nums[i] < nums[i+1])++i;
            if (nums[k] >= nums[i]) break;
            swap(nums[k], nums[i]);
            k = i;
            i = left(k);
        }
    }
    void buildHeap(vector<int> &nums)
    {
        for (int i = nums.size() / 2 - 1; i >= 0; --i)
        {
            heapAdjust(nums, i, nums.size());
        }
    }
private:
    int left(int i) { return 2 * i + 1; }
};

时间复杂度：$O(nlogn).$

空间复杂度：$O(1).$

快速排序

代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void quickSort(vector<int>& nums, int low, int high)
    {
        if (low >= high) return;
        int pivot_idx = partition(nums, low, high);
        quickSort(nums, low, pivot_idx - 1);
        quickSort(nums, pivot_idx + 1, high);
    }
    int partition(vector<int>& nums, int low, int high)
    {
        swap(nums[low], nums[low + rand() % (high - low + 1)]);
        int pivot = nums[low];
        int l = low + 1, r = high;
        while (true)
        {
            while (l <= r && nums[l] < pivot) ++l;
            while (l <= r && nums[r] > pivot) --r;
            if (l >= r) break;
            swap(nums[l], nums[r]);
            ++l; --r;
        }
        swap(nums[low], nums[r]);
        return r;
    }
};

时间复杂度：$平均O(nlogn),最坏O(n^2).$

空间复杂度：$平均O(logn)，最坏O(n).$

归并排序

代码

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        mergeSort(nums, 0, nums.size() - 1);
        return nums;
    }
    void mergeSort(vector<int>& nums, int low, int high)
    {
        if (low >= high) return;
        int m = low + ((high - low) >> 1);
        mergeSort(nums, low, m);
        mergeSort(nums, m+1, high);
        merge(nums, low, m, high);
    }
    void merge(vector<int>& nums, int low, int mid, int high)
    {
        vector<int> buffer(nums.begin() + low, nums.begin() + mid + 1);
        int i, j, k;
        for (k = low, i = 0, j = mid + 1; i < buffer.size() && j <= high; ++k)
        {
            if (buffer[i] <= nums[j]) nums[k] = buffer[i++];
            else nums[k] = nums[j++];
        }
        while (i < buffer.size()) nums[k++] = buffer[i++];
    }
};

时间复杂度：$O(nlogn).$

空间复杂度：$O(n).$