题解 | #排序#

核心点是分治，需要将数组分成三段left，middle，right；其中中间一段只是一个数字，左段的全部数字要比中间数小，右段的全部数字要比中间数大。

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    
    int sortPartition(vector<int>& arr, int left_index, int right_index) {
        int key_num = arr[left_index]; // left_index的数字移出到key_num, left_index位置腾空
        while(left_index < right_index) {
            while(left_index < right_index && arr[right_index] >= key_num) right_index--; // 从右往左移动找到小于key_num的right_index
            if(left_index < right_index) arr[left_index] = arr[right_index]; // right_index的数字移出到腾空的left_index, right_index位置腾空
            while(left_index < right_index && arr[left_index] < key_num) left_index++; // 从左往右移动找到大于key_num的left_index
            if(left_index < right_index) arr[right_index] = arr[left_index]; // left_index的数字移出到腾空的right_index, left_index位置腾空
        }
        arr[left_index] = key_num; // 比较数key_num移出到腾空的left_index, key_num位置腾空
        return left_index;
    }
    
    int quickSort(vector<int>& arr, int left_index, int right_index) {
        
        if (left_index >= right_index) return 0;
        int middle_index = sortPartition(arr, left_index, right_index);
        quickSort(arr, left_index, middle_index - 1);
        quickSort(arr, middle_index + 1, right_index);
        return 0;
    }
    
    vector<int> MySort(vector<int>& arr) {
        // write code here
        quickSort(arr, 0, arr.size() - 1);
        return arr;
    }
};