题解 | #排序# C++常用的七种排序算法

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;
    }
};

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;
    }
};

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;
    }
};

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;
    }
};

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;
    }
};

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;
    }
};

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;
    }
};