1.冒泡排序    时间复杂度O(n^2)   空间复杂度O(1)  稳定class Solution {public:    //冒泡排序    void BubbleSort(vector<int>& a)    {        for(int i=0;i<a.size()-1;i++)            for(int j=1;j<a.size()-i;j++)                if(a[j-1]>a[j])                    swap(a[j-1],a[j]);    }    vector<int> MySort(vector<int>& arr) {        BubbleSort(arr);        return arr;    }};2.直接选择排序    时间复杂度O(n^2)   空间复杂度O(1)  不稳定class Solution {public:    //直接选择排序    void SelectSort(vector<int>& a)    {        for(int i=0;i<a.size();i++)        {            int min=i;            for(int j=i;j<a.size();j++)                if(a[j]<a[min])                    min=j;            swap(a[i],a[min]);        }    }    vector<int> MySort(vector<int>& arr) {        SelectSort(arr);        return arr;    }};3.插入排序    时间复杂度O(n^2)   空间复杂度O(1)  稳定class Solution {public:    //插入排序    void InsertSort(vector<int>& a)    {        for(int i=1;i<a.size();i++)        {            if(a[i]<a[i-1])            {                int tmp=a[i];                int j=i;                while(tmp<a[j-1])                {                    a[j]=a[j-1];                    j--;                }                a[j]=tmp;            }        }    }    vector<int> MySort(vector<int>& arr) {        InsertSort(arr);        return arr;    }};4.希尔排序    时间复杂度O(n^1.3)   空间复杂度O(1)  不稳定class Solution {public:    //Shell排序    void ShellSort(vector<int>& a)    {        int h=1;        while(h<a.size()/3)            h=3*h+1;        while(h>=1)        {            for(int i=h;i<a.size();i++)                for(int j=i;j>=h&&a[j]<a[j-h];j-=h)                    swap(a[j],a[j-h]);            h/=3;        }    }    vector<int> MySort(vector<int>& arr) {        ShellSort(arr);        return arr;    }};5.快速排序    时间复杂度O(nlogn)   空间复杂度O(nlogn)  不稳定class Solution {public:    //快速排序    void QuickSort(vector<int>& a,int l,int r)    {        if(l>=r) return;        int i=l,j=r,temp=a[i];        while(i<j)        {            while(i<j&&a[j]>=temp)                j--;            if(i<j)            {                a[i]=a[j];                i++;            }            while(i<j&&a[i]<temp)                i++;            if(i<j)            {                a[j]=a[i];                j--;            }        }        a[i]=temp;        QuickSort(a,l,i-1);        QuickSort(a,i+1,r);    }    vector<int> MySort(vector<int>& arr) {        QuickSort(arr,0,arr.size()-1);        return arr;    }};6.归并排序    时间复杂度O(nlogn)   空间复杂度O(1)  稳定class Solution {public:    //归并排序    void Merge(vector<int>& a,int l,int r)    {        if(l>=r)            return;        int m=(l+r)/2;        Merge(a,l,m);        Merge(a,m+1,r);        MergeSort(a,l,m,r);    }    void MergeSort(vector<int>& a,int l,int m,int r)    {        vector<int>temp;        int left=l,right=m+1;        while(left<=m&&right<=r)            temp.emplace_back(a[left]<=a[right]?a[left++]:a[right++]);        while(left<=m)            temp.emplace_back(a[left++]);        while(right<=r)            temp.emplace_back(a[right++]);        for(int j=0;j<temp.size();j++)            a[l+j]=temp[j];    }    vector<int> MySort(vector<int>& arr) {        Merge(arr,0,arr.size()-1);        return arr;    }};7.堆排序    时间复杂度O(nlogn)   空间复杂度O(1)  不稳定class Solution {public:    //堆排序    void MaxHeapify(vector<int>& a,int start,int end)    {        int dad=start;        int son=dad*2+1;        while(son<=end)        {            if(son+1<=end&&a[son+1]>a[son])                son++;            if(a[dad]>a[son])                return;            else            {                swap(a[dad],a[son]);                dad=son;                son=dad*2+1;            }        }    }    void HeapSort(vector<int>& a)    {        for(int i=a.size()/2-1;i>=0;i--)            MaxHeapify(a,i,a.size()-1);        for(int i=a.size()-1;i>0;i--)        {            swap(a[0],a[i]);            MaxHeapify(a,0,i-1);        }    }    vector<int> MySort(vector<int>& arr) {        HeapSort(arr);        return arr;    }};