插入排序
1.从第一个元素开始，该元素可以认为已经被排序
2.取出下一个元素，在已经排序的元素序列中从后向前扫描
3.如果前元素（已排序）大于取出的元素，将前元素就移到下一位置，
4.重复步骤3，直到找到已排序的元素小于或者等于被取出元素的位置
5.将被取出元素插入到该位置后
重复步骤2~5
插入排序.gif
void InsertSort(int arr[], int len) {
int j,i;
for ( i = 1; i < len; ++i) {
//取出新元素
int temp = arr[i];
for ( j = i; j > 0; j--) {
if (arr[j - 1] > temp) {
//将元素往前移动
arr[j] = arr[j - 1];
} else {
break;
}
}
//插入合适的位置
arr[j] = temp;
}
}
希尔排序
希尔排序.gif
看上面动画可能不是非常清楚，我画了个简单图
image.png
分析上面图，首先会选择步长，每次步长都除以2，第一次步长为长度/2，第一次从0开始，步长为5的数进行比较交换，比如上图第一次的时候8和3进行交换，9和4交换，1和6不交换，因为1比6小，依次推论。第二次的时候，因为上次步长为5所以这次步长为2，如上图，3，1比较进行交换等
代码
void shellInsertSort(int arr[], int len) {
//首先需要定义步长
int increment = len / 2;
int i, j, k;
while (increment > 0) {
//8 9 1 7 2 3 5 4 6 0
//每次循环的次数,可以上图的不同直线有几条，第一次的时候是5，第二次是2(虽然颜色不一样)，第三次是1
for (i = 0; i < increment; ++i) {
//交换的数
for (j = i + increment; j < len; j += increment) {
//其实就是取出来的数
int temp = arr[j];
//实际就是插入排序
for (k = j; k > i && arr[k - increment] > temp; k -= increment) {
//将大的数往后移动
arr[k] = arr[k - increment];
}
//插入进去
arr[k] = temp;
}
}
//每次循环完，步长除于2
increment /= 2;
}
}
