1.直接插入排序
1.1.算法思想
每次将该元素按照其大小插入到前面已有序的序列中（将数组中第一个元素视为有序，因此从第二个元素开始）
1.2.代码
void InsertSort(int arr[], int n){ int i, j, temp; //遍历数组 for (i = 1; i < n; i++){ //当前元素的前驱大于当前元素 if (arr[i - 1] > arr[i]) { //保存arr[i] temp = arr[i]; //将前面有序序列中的所有大于arr[i]的值全部后移一位 for (j = i - 1; j >= 0 && arr[j] > temp; j--){ arr[j + 1] = arr[j]; } //将原arr[i]赋值给arr[j + 1] arr[j + 1] = temp; }//if }//for }
1.3.时间复杂度和稳定性
最好情况：原本就有序，仅需遍历一遍数组。O（n）
最坏情况：逆序，每一轮都必须从当前元素往前遍历到第一个元素，并且每个数组元素都要依次向后移动。O（n^2）
稳定性：依次向前遍历数组找到第一个小于等于该元素的元素，在其后面插入元素，因此，该算法稳定
适用：链式和顺序都可以（大部分排序算法仅适用顺序）
2.折半插入排序
2.1.算法思想
与折半查找类似，逐一遍历数组元素，在数组前面有序的序列中找到该元素的位置（将数列中第一个元素视为有序）
1.low初始化为1，high初始化为i - 1，将 arr[i] 存入 arr[0]
2.mid更改为 (low + high) / 2，对比 arr[0] 和 arr[mid] 的大小：arr[mid] 大，则去右半边；arr[mid]小或者相等，则去左半边（这个是与折半查找区别的地方，也是折半插入排序稳定的原因）
3.循环执行2，直到 low > high，此时，从arr[low]开始到第 i - 1 个元素依次向后移一位，然后将arr[0] 插入 arr[low]
4.循环123直到整个数组有序
2.2.代码
void InsertSort(int arr[], int n){ int i, low, high, mid; //遍历数组 for(i = 2; i < n; i++) { //arr[0]保存当前元素 arr[0] = arr[i]; //初始化low和high指针分别为第一个元素和第i - 1个元素 low = 1; high = i - 1; //循环直到low > high，查找当前元素在当前序列中的位置 while (low <= high) { //更新mid mid = (high + low) / 2; //mid指向的元素小于arr[0]，去左半边继续排序 if(arr[0] < arr[mid) high = mid - 1; //mid指向的元素大于等于arr[0]，去右半边，这是该算法稳定的原因 else low = mid + 1; } //从arr[low]开始的元素依次向后移 for (int j = i - 1; j >= low; j--){ arr[j] = arr[j - 1]; } //在arr[low]处插入元素 arr[low] = arr[0]; }//for }
2.3.时间复杂度和稳定性
1.该算法对比直接插入排序，仅降低了比较的次数O(
)，但是，移动的次数并没有降低还是O（n^2），因此，时间复杂度仍为O（n^2）
2.该算法稳定：arr[mid]小或者相等，则去左半边（这个是与折半查找区别的地方，也是折半插入排序稳定的原因）
3.折半插入排序的效率与表中顺序无关，仅与表长 n 有关
4.适用：仅顺序（折半查找也是）
3.希尔排序
3.1.算法思想
将表中的分成一个个子表，子表中进行直接插入排序，当整个表中基本有序的时候，再对整个表进行一次直接插入排序
1.取d1（通常为 n / 2），将表分为d1组，组内每个元素相距d1，对组间元素进行直接插入排序
2.取d2为d1 / 2，重复1操作；直到d = 1，表中所有元素合并为一个表，此时已经基本有序，进行最后一次直接插入排序
3.2.代码
void ShellSort(int arr[], int n) { int d; //初始化d为n/2，每一轮d为上一轮的1/2 for (d = n / 2; d >= 1; d /= 2) { //从每个个分组的第二个元素开始，遍历剩余元素，进行直接插入排序 for (int i = 1 + d; i < n; i++) { //直接插入排序（组间元素对比） if (arr[i] < arr[i - d]) { arr[0] = arr[i]; int j; for (j = i - d; j > 0 && arr[j] > arr[0]; j -= d) { arr[j + d] = arr[j]; } arr[j + d] = arr[0]; }//if }//for }//for }
3.3.时间复杂度和稳定性
1.希尔排序的时间复杂度为O（n^1.3）
2.稳定性：虽然组间排序是用直接插入排序，但是仍然不稳定
3.适用：仅适用顺序存储
