快排

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


    void quickSort(vector<int>& nums, int left, int right) {
        if (left >= right) return;
        int k = partition(nums, left, right);
        quickSort(nums, left, k-1);
        quickSort(nums, k+1, right);
    }

    int partition(vector<int>& a, int left, int right) {
        int pivot = a[left];

        while(left < right) {
            while(left < right && a[right] > pivot) {
                --right;
            }
            std::swap(a[left], a[right]);
            while(left < right && a[left] <= pivot) {
                ++left;
            }
            std::swap(a[right], a[left]);
        }
        std::swap(a[left], pivot);
        
        return left;
    }
};

堆排序

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};

        heapSort(nums, nums.size());

        return nums;
    }

    void heapSort(vector<int>& nums, int len) {
        
        // build max heap
        for (int i=len/2; i>=0; --i) {
            heapify(nums, i, len);
        }

        for (int i=len-1; i>0; --i) {
            swap(nums[0], nums[i]);
            --len;
            heapify(nums, 0, len);
        }
    };

    void heapify(vector<int>& nums, int i, int heapSize) {
        int left = 2*i+1;
        int right = 2*i+2;
        int max = i;

        if (left < heapSize && nums[left] > nums[i]) {
            max = left;
        }
        if (right < heapSize && nums[right] > nums[i] && nums[right] > nums[left]) {
            max = right;
        }
        if (max != i) {
            swap(nums[i], nums[max]);
            heapify(nums, max, heapSize);
        }
        
    };
};

归并

class Solution {
public:
    vector<int> sortArray(vector<int>& nums) {
        if (nums.empty()) return {};

        tmp.resize(nums.size(), 0);
        sort(nums, 0, nums.size()-1);

        return nums;
    }

    void sort(vector<int>& nums, int begin, int end) {
        if (begin >= end) return;
        int mid = (begin+end)/2;

        sort(nums, begin, mid);
        sort(nums, mid+1, end);

        int i = begin, j = mid+1;
        int count = begin;
        while(i <= mid && j <= end) {
            if (nums[i] < nums[j]) {
                tmp[count++] = nums[i++];
            } else {
                tmp[count++] = nums[j++];
            }
        }

        while(i<=mid) tmp[count++] = nums[i++];
        while(j<=end) tmp[count++] = nums[j++];

        for (int i=begin; i<=end; ++i) {
            nums[i] = tmp[i];
        }
    }

private:
    vector<int> tmp;
};