题解 | #排序#

思路：

题目的主要信息：

• 给数组排序
• 不要求稳定与否

就十分普通的排序问题，不考虑时间空间，常见的排序算法都可以，以下介绍几种。

方法一：sort函数（快排）
具体做法：
直接调用sort函数排序。

class Solution {
public:
    vector<int> MySort(vector<int>& arr) {
        sort(arr.begin(), arr.end()); //直接调用排序函数
        return arr;
    }
};

复杂度分析：

• 时间复杂度：，快排的时间复杂度
• 空间复杂度：，没有额外空间

方法二：冒泡排序法（超时）
具体做法：
两层循环，内循环依次比较前后元素的大小，若是大的在前，则交换二者顺序

class Solution {
public:
    vector<int> MySort(vector<int>& arr) {
        for(int i = 0; i < arr.size(); i++)
            for(int j = 1; j < arr.size(); j++)
                if(arr[j] < arr[j - 1]){//比较并冒泡
                    int temp = arr[j];  //交换
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
        return arr;
    }
};

复杂度分析：

• 时间复杂度：，两层循环
• 空间复杂度：，除了常数变量，没有额外空间、

方法三：归并排序法
归并排序利用了分治的思想来对序列进行排序。对一个长为n的待排序的序列，我们将其分解成两个长度为n/2的子序列。每次先递归调用函数使两个子序列有序，然后我们再线性合并两个有序的子序列使整个序列有序。

class Solution {
public:
    vector<int> temp;
    void mergeSort(vector<int>& arr, int l, int r) {
        if (l >= r) 
            return;
        int mid = (l + r) / 2; //中间划分
        mergeSort(arr, l, mid); //排序两边
        mergeSort(arr, mid + 1, r);
        int i = l, j = mid + 1;
        int cnt = 0;
        //合并
        while (i <= mid && j <= r) { //依次比较，先取较小值
            if (arr[i] <= arr[j])
                temp[cnt++] = arr[i++];
            else
                temp[cnt++] = arr[j++];
        }
        while (i <= mid)  //剩余的元素
            temp[cnt++] = arr[i++];
        while (j <= r)
            temp[cnt++] = arr[j++];
        for (int i = 0; i < r - l + 1; ++i)
            arr[i + l] = temp[i];
    }
    vector<int> MySort(vector<int>& arr) {
        temp.resize(arr.size(), 0);
        mergeSort(arr, 0, arr.size() - 1);
        return arr;

    }
};

复杂度分析：

• 时间复杂度：，递归公式为，故复杂度为
• 空间复杂度：，借助了temp数组

方法四：堆排序
具体做法：
使用priority_queue模拟大根堆，将数组中的元素依次入堆，然后因为是大数在堆顶，依次出堆时需要逆序放回数组中。

class Solution {
public:
    vector<int> MySort(vector<int>& arr) {
        priority_queue<int> q; //大根堆
        for(int i = 0; i < arr.size(); i++) //入堆
            q.push(arr[i]);
        for(int i = arr.size() - 1; i >= 0; i--){  //大的在顶部，所以逆序
            arr[i] = q.top();
            q.pop();
        }
        return arr;
    }
};

复杂度分析：

• 时间复杂度：，元素入堆为，一共n个元素
• 空间复杂度：，堆的大小