2.1：初级排序算法

一：选择排序

每次选最小的与未排序的最前面那个交换一下：

class SelectionSort
{
public:
    static void exch(vector<int> &arr, int p, int q)
    {
        int temp = arr[p];
        arr[p] = arr[q];
        arr[q] = temp;
    }

    static void sort(vector<int> &arr)
    {
        int N = arr.size();
        vector<int> &yin = arr;
        for (int i = 0; i < N; ++i)
        {
            int min = i;
            //每次内循环确定一个min值，min为最小值的下标，注意是下标哦
            //用下标好处多多，直接用值的话，你还得确定min的初始值是多少
            for (int j = i + 1; j < N; ++j)
            {
                if (arr[j] < arr[min])
                {
                    min = j;
                }
            }
            exch(arr, i, min);
        }
    }
};
//O(T) = O(N^2); O(S) = O(1); 稳定排序

二：插入排序

摸牌，手上的牌已经有序了（在初始输入大致有序的情况下较快）

class InsertionSort
{
public:
    static void exch(vector<int> &arr, int p, int q)
    {
        int temp = arr[p];
        arr[p] = arr[q];
        arr[q] = temp;
    }

    static void sort(vector<int> &arr)
    {
        int N = arr.size();
        for (int i = 0; i < N; ++i)
        {
        //如果刚摸的牌arr[j]比手上最大的牌arr[j-1]小，则交换一下，继续比较
        //直到arr[j]到达合适位置（最小，或者刚好有牌小于等于它）
            for (int j = i; j>0 && arr[j] < arr[j - 1]; --j) 
            {
                exch(arr, j, j - 1);
            }
        }
    }
};
//O(T) = O(N^2); O(S) = O(1); 稳定排序

三：希尔排序

将插入排序的1换成h，并不断减少至1即可

class ShellSort
{
public:
    static void exch(vector<int> &arr, int p, int q)
    {
        int temp = arr[p];
        arr[p] = arr[q];
        arr[q] = temp;
    }

    static void sort(vector<int> &arr)
    {
        int N = arr.size();
        int h = 1;
        while (h < N / 3)
        {
            h = 3 * h + 1;
        }
        while (h >= 1)
        {
            for (int i = 0; i < N; ++i)
            {
                for (int j = i; j>0 && arr[j] < arr[j - 1]; --j)
                {
                    exch(arr, j, j - 1);
                }
            }
            h /= 3;
        }

    }
};
//h之间最好互质

复杂度跟h序列有关，至今没研究透彻