《算法》读书笔记 - 排序
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;
}