1. 选择排序

思想就是 从数组的第一个元素开始，找出从该元素开始到数组结束中的最小元素，与当前元素交换。

vector<int> selection_sort(vector<int> v) {
    int len = v.size();
    for(int i=0;i<len;i++) {
        int min_index = i;
        for(int j=i+1;j<len;j++) {
            if( v[j] < v[min_index] ) {
                min_index = j;
            }
        }
        //将 v[i]~v[len-1] 中的最小值与 v[i] 交换
        int tmp = v[i];
        v[i] = v[min_index];
        v[min_index] = tmp;
    }
    return v;
}

2. 插入排序

插入排序的整体思想就是将每个元素之前的部分视为已经排序好的，然后该元素插入到其中的适当位置。

vector<int> insertion_sort(vector<int> v) {
    int len = v.size();
    for(int i = 1; i < len; i++ ) {
        int j=i;
        //不断将元素前移，直到该元素大于等于当前位置的迁移元素，
        //即满足大于等于左侧元素，同时小于等于右侧元素，即移到了适当位置
        while(j>0 && v[j]<v[j-1]) {
            int tmp = v[j];
            v[j] = v[j-1];
            v[j-1] = tmp;
            j--;
        }
    }
    return v;
}

3. 希尔排序

希尔排序是插入排序的一个变种，解决了插入排序中交换元素操作过多的问题。希尔排序首先选定一个步进，按该步进将数组分为若干组。
例如一个长度为 10 的数组a[]，若按步进为 3 分组，则 a[0],a[3],a[6],a[9]为一组，a[1],a[4],a[7]为一组，a[2],a[5],a[8]为一组，然后对这几个子分组分别进行插入排序，排序完成后，缩短步进，重复上面的操作，直到步进为 1 的分组排序结束。
《算法》中选择 1,4,13,40... 这个序列来改变步进，而似乎选择 1,2,4,8,16 这个序列来改变步进更方便

vector<int> shell_sort( vector<int> v ) {
    int len = v.size();
    for(int gap=len>>1;gap>0;gap>>=1) {
        for(int i = gap; i<len; i++) {
            int j = i;
            while(j-gap>=0 && v[j]<v[j-gap]) {
                int tmp = v[j-gap];
                v[j-gap] = v[j];
                v[j] = tmp;
                j-=gap;
            }
        }
    }
    return v;
}