插入排序
2.1.1 基本思想
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。
实际中我们玩扑克牌时，就用了插入排序的思想——每摸一张新牌，就将其插入到手中已有序的牌中的合适位置。
2.1.2 直接插入排序
当插入第i（i >= 1）个元素时，前面的array[0],array[1], …,array[i-1]已经排好序。此时用array[i]的排序码与array[i-1],array[i-2], … 的排序码顺序进行比较，找到插入位置后将array[i]插入，原来位置上的元素顺序后移。
直接插入排序的特性总结：
- 元素集合越接近有序，直接插入排序算法的时间效率越高；
- 时间复杂度：
- 最好情况（已有序）：O(N)
- 平均/最坏情况：O(N²)
- 空间复杂度：O(1)，它是一种原地排序算法；
- 稳定性：稳定（相等元素的相对位置不会改变）。
voidDirectSorting(int*arr,intn){for(inti=0;i<n-1;i++){intend=i;intcur=arr[end+1];while(end>=0){if(cur<arr[end]){arr[end+1]=arr[end];end--;}elsebreak;}arr[end+1]=cur;}}直接排序与冒泡排序形式上有些相似，但本质区别很大，冒泡排序是对相邻的两个数轮流比较，将最大的数经过n-1轮后冒泡到最后一个，此后每轮冒泡次数减一，而直接排序是将从有序数列开始（对于无序数列来说，有序数列是0），将后面的无序数依次与前面的有序数比较，将其放在合适的位置
2.1.3 希尔排序（缩小增量排序）
希尔排序（Shell Sort）又称缩小增量排序，是对直接插入排序的一种高效改进算法。其基本思想是：
先选定一个小于数组长度的整数作为初始增量（
gap），将待排序序列中所有间隔为gap的元素划分为若干个子序列，每个子序列分别进行直接插入排序；随后逐步缩小增量（如gap = gap / 2或gap = gap / 3 + 1），重复分组和排序过程；当增量减至 1 时，整个序列被当作一个子序列进行最后一次直接插入排序，此时序列已基本有序，排序效率很高。
关键说明：
预排序
- 分组方式：不是按连续块分组，而是按“下标模
gap相同”来分组。
例如，当gap = 3时，子序列为：- 第0组：
arr[0], arr[3], arr[6], ... - 第1组：
arr[1], arr[4], arr[7], ... - 第2组：
arr[2], arr[5], arr[8], ...
- 第0组：
- 每轮排序：对每个子序列独立执行直接插入排序，使得在数列进行完全的直接插入排序时，数列趋于有序，可以大大提升直接插入排序的效率。
- Knuth 序列：对于gap，我们应该灵活分组，对数列进行多次分组预排序列，目前认为Knuth 序列是其中比较高效的分组方法之一，hk=(3^k-1)/2，k∈z+，即当gap=1, 4, 13, 40, 121, 364, 1093, 3280, …时，符合Knuth序列，但是我们在实际过程中，为了方便，通常用gap=n/3+1来代替Knuth序列，简洁的同时+1保证最后gap一定会回到1完成最后的完全直接排序，且效率与Knuth序列相近
希尔排序的特点：
| 项目 | 说明 |
|---|---|
| 时间复杂度 | 依赖增量序列，通常为 O(n^1.3) ，优于直接插入排序 |
| 空间复杂度 | O(1) （原地排序） |
| 稳定性 | 不稳定（跨组交换可能改变相等元素的相对顺序） |
| 适用场景 | 中等规模数据（几千到几万），或作为快速排序的优化子过程 |
为什么有效？
- 初始大增量使元素快速移动到大致正确的位置（“粗调”）；
- 后续小增量对已基本有序的序列做精细调整（“微调”）；
- 最后
gap = 1时，直接插入排序的效率接近 O(n) 。
核心优势：通过多轮“局部有序”，显著减少最终插入排序的移动次数。
voidShellSorting(int*arr,intn){for(intgap=n/3+1;gap>=1;gap/=3)for(inti=0;i<n-gap;i++)//合并写法，虽然将数组分为了n/gap个组，每个组都有gap个数，但不一定需要三层循环，可以从下标零开始，对每一个数开始顺序调正，但他们依旧是与自己gap组的数比较{intend=i;intcur=arr[end+gap];while(end>=0){if(cur<arr[end]){arr[end+gap]=arr[end];end=end-gap;}elsebreak;}arr[end+gap]=cur;}}使用实现Kunth序列分组：
voidKnuthShellSorting(int*arr,intn){intgap=1;while(gap<n/3){// 注意：这里用 n/3 避免 gap >= n,(n/3-1)*3=n-3gap=gap*3+1;}//到此处完成knuth序列。while(gap>=1){for(inti=0;i<n-gap;i++){intend=i;intcur=arr[end+gap];while(end>=0&&cur<arr[end]){arr[end+gap]=arr[end];end-=gap;}arr[end+gap]=cur;}gap=(gap-1)/3;遍历Knuth序列}}
