2-路插入排序（2-Path Insertion Sort）
基本思想
2-路插入排序是在折半插入排序的基础上再改造，其目的是减少排序过程中移动元素的次数，但是为此需要 n 个记录的辅助空间
具体地，另设一个和 L（的关键字）同类型的数组 d，将 L[1] 赋值给 d[1]，并将 d[1] 看成是在排好序的序列中处于中间位置的元素（中轴），然后依次将待排序列 L[2…n] 依次插入到 d[1] 之前或之后的有序序列中，即比 d[1] 小的插入到前面，比 d[1] 大的插入到后面。排序完成后，将 d[] 中有序序列回填到 L 中，并释放放 d。
要点：算法实现时，可将 d[] 看成一个循环向量，并设置两个指针 first 和 final 分别指向排序进行时已得到的有序序列中第一个元素和最后一个元素在 d[] 中的位置。
代码实现
void TwoInsertSort(int L[], int n)
{
int i, j, first = 0, last = 0; // 初始化首尾指针
int *tmpbuffer = (int *)malloc(n * sizeof(int));
for (i = 1; i < n; ++i) tmpbuffer[i] = 0;
tmpbuffer[0] = L[1]; // tmpbuffer[0]为中轴
for (i = 2; i <= n; ++i)
{
if (L[i] >= tmpbuffer[0]) // 右插，保证稳定大于时取等
{
// 首次运行到这时，循环不会执行
for (j = last; L[i] < tmpbuffer[j]; --j)
tmpbuffer[j+1] = tmpbuffer[j]; // 从last开始，比较查找，向后移动
tmpbuffer[j+1] = L[i]; last = last + 1;
}
else // 左插
{
// 首次运行到这时，循环不会执行，
// 之后，first 指针将移动到数组尾部 d[n-1]不需要管j会不会越界
for (j = first; L[i] >= tmpbuffer[j]; ++j)
tmpbuffer[j-1] = tmpbuffer[j]; // 从first开始，比较查找，向前移动
// 首次运行到这时，first 指针将移动到数组尾部 d[n-1]，此时需要取余，之后不需要
tmpbuffer[(j-1+n)%n] = L[i]; first = (first - 1 + n) % n;
}
}
// 回填 L
for (i = 1; i <= n; ++i)
L[i] = tmpbuffer[(first++)%n]; // first 为有序序列头指针
free(tmpbuffer);
}归纳分析
- 稳定排序（stable sort）
针对折半插入排序的优化，减少移动次数，仍是稳定排序。
- 空间复杂度（out-of-place 非原地算法，O(n)）
需要另辟 n 空间辅助排序，排序完成后需要回填数据，空间复杂度为 O(n)
- 时间复杂度
比较和移动操作一块进行；
排序中，移动元素次数约为 n2/8，2-路插入排序只能减少移动元素的次数，不能绝对避免移动，并且当当待排序列首元素 L[1] （被选为中轴）是序列中最小或最大时，2-路插入排序将完全失去优越性，因此，2-路插入排序时间复杂度 与初始状态有关。
当然，在选择中轴元素时，不一定非要选择首元素，可随机选择首元素尽可能避免这种问题。
平均情况下，2-路插入排序时间复杂度为 O(n2)。
- 初态影响
仍然是插入排序，受初始状态影响。
- 过程特征
一趟排序不能确定一个元素的最终位置，但会产生局部有序的有序子序列。
- 适用性
仍然是插入排序，比较适合用于“基本有序”的序列和“数据量不大”的序列。
扩展
既有中轴，又有头尾指针，显得有些冗余，取消中轴，由首尾指针将序列分成三部分，进行3路插入，相当于两个中轴，代码实现如下：
void ThreeInsertSort(int L[], int n)
// 这个其实是3路，跟first和last比较，待排序列被first和last分成了三部分
{
int i, j, first = 0, last = 0; // 初始化首尾指针
int *tmpbuffer = (int *)malloc(n * sizeof(int));
for (i = 1; i < n; ++i) tmpbuffer[i] = 0;
for (i = 2; i <= n; ++i)
{
if (L[i] >= tmpbuffer[last]) // 保证稳定大于时取等
{
last = last + 1;
tmpbuffer[last] = L[i];
}
else if (L[i] < tmpbuffer[first]) // 小于时不取等
{
first = (first-1+n) % n;
tmpbuffer[first] = L[i];
}
else // 中间这部分仍是简单插入排序
{
j = last++;
while(L[i] < tmpbuffer[j])
{
tmpbuffer[(j+1)%n] = tmpbuffer[j];
j = (j-1+n) % n;
}
tmpbuffer[(j+1)%n] = L[i];
}
}
// 回填L
for (i = 1; i <= n; ++i)
L[i] = tmpbuffer[(first++)%n]; // first 为有序序列头指针
free(tmpbuffer);
}希尔排序（Shell’s Sort）
产生来源
根据之前对直接插入排序的分析可得，其时间复杂度为 O(n2)，而当待排序列 基本有序 时，排序效率会有很大提高，复杂度可提升至 O(n)；另一方面，当数量较小时，排序效率又会有很大提升。基于这两点考量，1959 年 Shell 提出了希尔排序，又称缩小增量排序（Diminshing Increment Sort）
基本思想
先将待排序列按增量分割成若干元素数量相同的子序列，分别进行直接插入排序，（不断缩小增量）待整个序列“基本有序”时，再对全体序列进行一次直接插入排序（即增量缩小至1）。
具体地，
注意点：划分子序列不是简单地“连续逐段分割”，而是将相隔某增量的元素划分为一组；因此，排序过程中，元素的移动不是一步一步的移动，而是跳跃式的移动，而这种分组跳跃式移动也使得希尔排序是一种不稳定排序。
要点：增量的选择 和 排序最终以1为增量进行排序结束。
代码实现
void ShellSort(int L[], int n)
{
int i, j, k, d; // 增量
for (d = n/2; d >= 1; d /= 2)
{
// 一趟插入排序，增量为 d，故需进行 d 组子序列排序
for (i = 1; i <= d; ++i) // i 是每组子序列首元素
{
for(j = i+d; j <= n; j += d) // 无序部分
{
L[0] = L[j]; // L[0] 仅用于暂存待插入元素
for (k = j-d; k >= i && L[k] > L[0]; k -=d) // 在有序部分中找位置
L[k+d] = L[k];
L[k+d] = L[0]
}
}
}
}上述代码，在进行一趟希尔排序时，是分成 d 组进行的，每组独立进行排序（L5-L7），可以将其合并，进行依次遍历即可，改进如下。
void ShellSort(int L[], int n)
{
int i, j, dk; // 增量 dk
for (dk = n/2; dk >= 1; dk /= 2) // 这里 dk序列取 n/2,n/4,...1
{
// 一趟希尔插入排序
for(i = 1+dk; i <= n; ++i) // L[1+dk,...n]
{
L[0] = L[i]; // L[0] 仅用于暂存待插入元素
for (j = i-dk; j >= 1 && L[j] > L[0]; j -=dk) // 在有序部分中找位置
L[j+dk] = L[j];
L[j+d] = L[0]
}
}
}归纳分析
- 不稳定排序（unstable sort）
分组跳跃式移动使得希尔排序是一种不稳定排序。
- 空间复杂度（in-place 原地算法，O(1)）
需要 1 个辅助空间暂存元素，希尔排序的空间复杂度为 O(1)。
- 时间复杂度
希尔排序的分析较复杂，其时间复杂度是依赖于“增量序列”的函数，涉及到一些数学上尚未解决的问题，目前尚未求得一种最好的增量序列。
最坏情况下，希尔排序的时间复杂度为 O(n2)。
但大量的研究证明了一些局部结论，
当增量序列为 delta[k] = 2t-k+1-1 时，
希尔排序的时间复杂度为 O(n3/2)，其中 t 为排序趟数，1 ≤ k ≤ ⌊ log2(n+1) ⌋
也有从大量实验推导出，
当 n 在某个特定范围时，希尔排序的时间复杂度约为 O(n1.3)，当 n → ∞ 时，可提高到 O(n(log2n)2)。
注意：增量序列有很多种取法，但都需要使增量序列中的值没有除 1 外的公因子，并且最后一个增量必须为 1。
- 初态影响
仍然是插入排序，受初始状态影响。
- 过程特征
一趟排序不能确定一个元素的最终位置，也不会产生有序子序列。
- 适用性
希尔排序是根据插入排序的适用性（比较适合用于“基本有序”的序列和“数据量不大”的序列）进行的相应优化。
由于是分组跳跃式比较移动，所以希尔排序仅适用于顺序存储的序列。