题意整理：

题目会给出一个数组，需要对该数组进行排序后返回排序的结果

排序算法有很多种，下图给出常见的排序算法及其时间复杂度，空间复杂度以及稳定性
（由于是在编译器中编写，用 n2 表示 n²）

需要注意的是，对于本题，的算法明显是无法通过的。而的算法不是基于比较排序，需要依赖数据性质，在此处也不合适。所以可以采用的有快速排序、堆排序和归并排序。
本题解实现快排和归并排序，对于堆排直接调用优先队列解决。

方法一：快速排序

核心思想：

快速排序是对较大的随机数据中速度最快的算法，可以视作冒泡排序的优化版本。
快速排序的具体思路如下：
在待排序的元素取出一个元素作为基准点，之后将待排序的元素进行分区，比基准点大的元素放在它的右边，比其小的放在它的左边。分区完毕后，对两个区域递归调用排序。
需要注意的点：在对基准点的选取中，不能够选择特定点如开头或结尾，这在数组有序或具备有序时会导致排序算法的效率很差，如果数组是已经排序的，选择开头或结尾会导致算法时间复杂度退化为O（n），既所有元素都位于基准点一侧，甚至因为递归缘故耗时要比冒泡更长。
避免上述问题的方法有很多种，常见的就是在选择元素时采用随机化，从数组中随机选择一个基准点。此处采用的是三值取中法，既对数组首元素，尾元素，和中间元素进行比较，选出位于中间值的元素作为基准点。作为优化，在选择中可以令这三个元素变为有序，并将基准点置于数组末尾，这样能够减少排序中比较的量。

核心代码：

class Solution {
public:
    //用于找到基准点，并让三值有序
    int mediam(vector<int>& arr, int left, int right) {
        int mid = (left + right) / 2;
        //以下三个交换让 首，尾，，中间有序
        if(arr[left] > arr[mid]) {
            swap(arr[left], arr[mid]);
        } 
        if(arr[left] > arr[right]) {
            swap(arr[left], arr[right]);
        } 
        if(arr[mid] > arr[right]) {
            swap(arr[mid], arr[right]);
        } 
        //将基准值放到倒数第二个元素便于比较
        swap(arr[mid], arr[right - 1]);
        return arr[right - 1];//返回基准值
    }

    void quickSort(vector<int>& arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int pivot = mediam(arr, left, right);
        int i = left, j = right - 1;
        while(i < j) {
            //比基准值大的与比基准值小的交换位置，直到交错
            while(arr[++i] < pivot);
            while(arr[--j] > pivot);
            if(i < j) {
                swap(arr[i], arr[j]);
            }
        }
        swap(arr[i], arr[right - 1]);//将基准值放回正确位置
        //递归调用
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
    }

    vector<int> MySort(vector<int>& arr) {
        quickSort(arr, 0, arr.size() - 1);//调用快排
        return arr;
    }
};

复杂度分析：

时间复杂度：，此处不会出现最坏情况，故递归次数为 ,每次复杂度为 ,所以总的时间复杂度为
空间复杂度：，即为递归使用的栈的深度，此处递归次数为

方法二：归并排序

核心思想：

归并排序是利用归并的思想实现的排序方法，该算法采用分治策略，既将问题分成一些小的问题然后递归求解，之后再将各答案合并。
体现到排序上的实现即为：将数组均分为左右两边，将两边各自完成排序（此处可以递归调用归并排序直到数组大小为，此时已经有序），再将两边元素进行合并。当然这需要借助一个辅助数组。

核心代码：

class Solution {
public:
    //合并两个区间使用的函数
    void merge(vector<int>& arr, int left, int mid, int right) {
        vector<int> help(right - left + 1);//辅助数组
        int p1 = left, p2 = mid + 1, i = 0;
        while(p1 <= mid && p2 <= right) {
            //将较小值填入
            help[i++] = arr[p1] > arr[p2] ? arr[p2++] : arr[p1++];
        } 
        //填入剩余值
        while(p1 <= mid) {
            help[i++] = arr[p1++];
        }
        while(p2 <= right) {
            help[i++] = arr[p2++];
        }
        i = 0;
        for(int j = left; j <= right; ++j) {
            arr[j] = help[i++];//将数据从辅助数组复制回原数组
        }
    }

    void mergeSort(vector<int>& arr, int left, int right) {
        if(left >= right) {
            return;
        }
        int mid = left + ((right - left) >> 1); //找到中间位置
        mergeSort(arr, left, mid);//递归排序
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);//合并两个区间
    }

    vector<int> MySort(vector<int>& arr) {
        mergeSort(arr, 0, arr.size() - 1);//调用归并排序
        return arr;
    }
};

复杂度分析：

时间复杂度：，需要递归 次，而每次合并操作的平均时间复杂度为，所以归并排序总的时间复杂度为。
空间复杂度：,需要创建一个与原数组等长的辅助数组用于合并。

方法三：使用priority_queue

核心思想：

c++中的priority_queue既是基于堆实现的，所以可以直接调用它实现堆排。创建一个优先队列（小顶堆），将数据全部插入后再逐个弹出，即为排序后的序列。

核心代码：

class Solution {
public:
    vector<int> MySort(vector<int>& arr) {
        priority_queue<int, vector<int>, greater<int>> q;//建立一个小顶堆
        int n = arr.size();
        for(int i = 0; i < n; ++i) {
            q.push(arr[i]);//将所有数据压入优先队列中
        }
        for(int i = 0; i < n; ++i) {
            arr[i] = q.top();//弹出堆顶元素，即为堆中最小数字
            q.pop();
        }
        return arr;
    }
};

复杂度分析：

时间复杂度：,优先队列内部采用的是堆排序，时间复杂度为
空间复杂度：，使用了一个优先队列进行辅助。需要注意的是，如果直接采用自建堆的方法，将数组建为堆，那么空间复杂度为，此处并非这种实现