一、直接插入排序

基础版：

伪码：

算法 InsertSort(R,n.R)
/*排列n个记录，使之对应的关键字非递减排列*/
FOR j=2 TO n DO
{
    i ← j-1. //每次循环将R[j]插入到R[1],...R[j-1]中
    K ← K[j]. R ← R[j].
    WHILE i > 0 AND K < K[i] DO
    {
        R[i+1]←R[i]. i ← i-1.
    }.

    R[i+1] ← R

}

改进版本A

基础版本算法有一个缺点：需要随时判断i是否大于0.
我们可以通过在表头设定一个非常小的值来避免这步判断。

需要多小呢？比所有值都小就可以了！

算法 InsertSortA(R,s,e.R)
/*对记录R[s]、R[s+1]、R[s+2]、R[s+3]、R[e]进行排序
令R[s-1]对应的K[s-1] ≤ min{K[i] | s ≤ i ≤ e }*/
FOR j=s+1 TO e DO
{
    i ← j-1. //每次循环将R[j]插入到R[1],...R[j-1]中
    K ← K[j]. R ← R[j].
    WHILE K < K[i] DO
    {
        R[i+1]←R[i]. i ← i-1.
    }.
    R[i+1] ← R
}

二、希尔排序

先举简单的例子：

对长度为n的数组进行排序：

• step 1: 选取增量为8分组。比如R[1]、R[9]、R[17]为1组，R[2]、R[10]、R[19]为2组…每一组内通过简单插入排序保证有序
• step 2: 选取增量4来分组。
• step 3: 选取增量2来分组
• step 4：选取增量1来分组。

经过以上四步，排序完成
该例子中，选取的增量序列为8、4、2、1

算法 ShellSort(R,n.R)
/*排列n个记录，使之对应的关键字非递减排列*/
d ← n/2 //（取下界）
WHILE d > 0 DO
{
FOR j=d TO n DO
{
    i ← j-d.
    K ← K[j]. R ← R[j].
    WHILE i > 0 AND K < K[i] DO
    {
        R[i+d]←R[i]. i ← i-d.
    }.

    R[i+d] ← R

}
d ← n/2 //（取下界）
}

这个递增序列是相当低效的。

长度序列也可以有以下选择：
1、 $2^{k}-1$ ，最坏复杂度O($n^(3/2)$)
2、 形如$2^{p}3^{q}$且小于n的所有正整数的集合。{$2^{p}3^{q}$|$2^{p}3^{q}$ < n} 则希尔算法的复杂度为$O(n{({log}_{2}n)}^2)$
3、目前已知的最好序列是{1、4、10、23、57、132、301、701、1750}。使用该序列时时间效率优于堆排序、插入排序。小规模数据优于快排，大规模数据不如快排。(也就是说这可能是处理小规模数据最好的算法)