14 | #排序#

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型vector 待排序的数组
     * @return int整型vector
     */
    /* 快排，其他排序算法需要继续补充 */
    vector<int> MySort(vector<int>& arr) {
        quickSort(arr, 0, arr.size()-1);
        return arr;
    }

    void quickSort(vector<int>& arr, int left, int right) {
        if (left < right) {
            int mid = partSort(arr, left, right);
            quickSort(arr, left, mid - 1);
            quickSort(arr, mid + 1, right);
        }
    }

    int  partSort(vector<int>& arr, int left, int right) {
        /* 将所有小于left都划分到左边，这里取一个标记数 key */
        int key = arr[left];
        int le = left; /* 保证[left, le]的闭区间是小于key的 */
        /* 遍历扫描key之后的元素，如果小<=key，先移动le,然将其交换到le后面的一个元素 */
        for (int i = le + 1; i <= right; i++) {
            if (arr[i] <= key) {
                le++;
                swap(arr[i], arr[le]);
            }
        }
        swap(arr[le], arr[left]);
        return le;
    }
};