题解 | #排序#

class Solution {
  private:
    void merge(std::vector<int>& array, int left, int mid, int right) {
        std::vector<int> temp(right - left + 1);
        int i = left, j = mid + 1, k = 0;

        while (i <= mid && j <= right) {
            if (array[i] <= array[j]) {
                temp[k++] = array[i++];
            } else {
                temp[k++] = array[j++];
            }
        }

        while (i <= mid) {
            temp[k++] = array[i++];
        }

        while (j <= right) {
            temp[k++] = array[j++];
        }

        for (int i = left, k = 0; i <= right; ++i, ++k) {
            array[i] = temp[k];
        }
    }

    void mergeSort(std::vector<int>& array, int left, int right) {
        if (left < right) {
            int mid = left + (right - left) / 2;
            mergeSort(array, left, mid);
            mergeSort(array, mid + 1, right);
            merge(array, left, mid, right);
        }
    }
    void quickSort(std::vector<int>& array, int left, int right) {
        if (left >= right) return;
        int pivot = array[left];
        int i = left, j = right;

        while (i < j) {
            while (i < j && array[j] >= pivot) j--;
            array[i] = array[j];
            while (i < j && array[i] <= pivot) i++;
            array[j] = array[i];
        }

        array[i] = pivot;
        quickSort(array, left, i - 1);
        quickSort(array, i + 1, right);
    }

  public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    vector<int> MySort(vector<int>& arr) {
        // write code here
        // mergeSort(arr, 0, arr.size() - 1);
        quickSort(arr, 0, arr.size() - 1);
        return arr;
    }
};