八大排序算法指的是冒泡排序、选择排序、插入排序、希尔排序、堆排序、归并排序、快速排序和基数排序（本文没有）。关于八种排序方法的对比在下表中：

0、主函数统一采用：

#include <vector>
#include <iostream>
using namespace std;
int main()
{
    int a[]={3,1,6,8,12,2,5,7};
    int len=sizeof(a)/4;
    vector<int> arr(a,a+len);
    Solution sl;
    arr = sl.guibing(arr); // 快排的参数传入略有不同
    return 0;
}

1、冒泡排序：

class Solution{
public:
    // 冒泡排序，每次最大的沉底
    vector<int> MaoPao(vector<int> arr)
    {
        int len=arr.size();       
        for(int i=0;i<len;i++)
        {
            for(int j=1;j<len-i;j++)
            {
                if(arr[j-1]>arr[j])
                {
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                }
            }
        }
        return arr;
    }
}；

2、选择排序

class Solution{
public:
    // 选择排序，每次选择最小的出来放前面
    vector<int> Select(vector<int> arr)
    {
        int len=arr.size();
        for(int i=0;i<len;i++)
        {
            int min_num=i;
            for(int j=i;j<len;j++)
            {
                if(arr[j]<arr[min_num])
                    min_num=j;
            }
            int temp=arr[min_num];
            arr[min_num]=arr[i];
            arr[i]=temp;
        }
        return arr;
    }
};

3、插入排序

class Solution{
public:
    // 插入排序，依次把每个数字插入到正确的相对位置
    vector<int> Insert(vector<int> arr)
    {
        int len=arr.size();
        for(int i=1;i<len;i++)
        {
            int ins=arr[i],j;
            // 找ins该在的位置，并把大于它的后移
            for(j=i-1;j>=0;j--)
            {
                if(arr[j]>ins)
                    arr[j+1]=arr[j];
                else
                    break;
                
            }
            // 位置j的数小于ins，ins应该放在j+1的位置
            arr[j+1]=ins;
        }
        return arr;
    }
};

4、希尔排序

class Solution{
public:
    // 希尔排序，插入排序的改进版本
    vector<int> Shell(vector<int> arr)
    {
        int len=arr.size();
        int a[]={3,1};
        vector<int> sh(a,a+2);
        for(int it=0;it<sh.size();it++)
        {
            int gap=sh[it];
            // 后面的双循环等同于插入排序，把+1和-1都改成了+gap/-gap
            for(int i=gap;i<len;i+=gap)
            {
                int ins=arr[i],j;
                for(j=i-gap;j>=0;j-=gap)    // 这里如果再int j，不报错但会出大问题
                {
                    if(arr[j]>ins)
                        arr[j+gap]=arr[j];
                    else
                        break;
                    
                }
                arr[j+gap]=ins;
            }
        }
        return arr;
    }
};

5、堆排序

class Solution{
public:
    vector<int> Adjust(vector<int> arr,int start,int end)
    {
        int temp=arr[start];
        for(int i=2*start+1;i<=end;i=2*i+1)
        {
            if(i<end && arr[i]<arr[i+1])
                i++;
            if(arr[i]>temp)
            {
                arr[start]=arr[i];
                start=i;
            }
            else
                break;
        }
        arr[start]=temp;
        return arr;
    }
    vector<int> Heap_sort(vector<int> arr)
    {
        int len=arr.size();
        for(int i=len/2-1;i>=0;i--)
        {
            arr = Adjust(arr,i,len-1);
        }
        for(int i=0;i<len;i++)
        {
            int temp=arr[0];
            arr[0]=arr[len-1-i];
            arr[len-1-i]=temp;
            arr = Adjust(arr,0,len-2-i);
        }
        return arr;
    }
};

6、快速排序

class Solution{
public:
    vector<int> Quick_Sort(vector<int> arr,int low,int high)
    {
        int i=low,j=high,key=arr[low];
        if(low>=high)
            return arr;
        while(low<high)
        {
            while(low<high && key<=arr[high])
                high--;
            if(key>arr[high])
            {
                arr[low]=arr[high];
                low++;
            }
            while(low<high && key>=arr[low])
                low++;
            if(key<arr[low])
            {
                arr[high]=arr[low];
                high--;
            }
        }
        arr[low]=key;
        arr = Quick_Sort(arr,i,low-1);
        arr = Quick_Sort(arr,low+1,j);
        return arr;
    }
}；

7、归并排序

class Solution{
public:
    vector<int> guibing(vector<int> arr)
    {
        int len=arr.size();
        // gap:每次归并的长度
        for(int gap=1;gap<len;gap*=2)
        {
            vector<int> brr;
            int s1=0,e1=s1+gap-1,s2=e1+1,e2; // 每两段归并的首尾位置，并不断更新
            if(s2+gap-1<len-1)
                e2=s2+gap-1;
            else
                e2=len-1;
            while(s2<len)
            {
                while(s1<=e1 && s2<=e2)
                {
                    if(arr[s1]<arr[s2])
                        brr.push_back(arr[s1++]);
                    else
                        brr.push_back(arr[s2++]);
                }
                while(s1<=e1)
                    brr.push_back(arr[s1++]);
                while(s2<=e2)
                    brr.push_back(arr[s2++]);
                s1=e2+1;
                e1=s1+gap-1;
                s2=e1+1;
                if(s2+gap-1<len-1)
                    e2=s2+gap-1;
                else
                    e2=len-1;
            }
            while(s1<len)
                brr.push_back(arr[s1++]);
            for(int i=0;i<len;i++)
                arr[i]=brr[i];
            brr.clear();
        }
        return arr;
    }
};