直接插入排序(Straight Insertion Sort)的基本思想是：
- 把n个待排序的元素看成一个有序表和一个无序表
- 开始时有序表中只有1个元素，无序表中包含n-1个元素。排序过程中每次从无序表中取出第一个元素，将它插入有序表中的适当位置，使之成为新的有序表。
- 重复上述过程n-1次即可完成排序
下面选取直接插入排序的一个中间过程对其进行说明。假设{20,30,40,10,60,50}中的前3个数已经排列过，是有序的了；接下来对10进行排列。示意图如下：
图中将数列分为有序区和无序区。我们需要做的工作只有两个：(1)取出无序区中的第1个数，并找出它在有序区对应的位置。(2)将无序区的数据插入到有序区；若有必要的话，则对有序区中的相关数据进行移位。
代码：
void insert_sort(int a[], int n)
{
int i, j;
// 为a[i]区间{0,1,...,i-1}中寻找到一个合适的位置
for(i = 1; i < n; i++)
{
j = i - 1;
int tmp = a[i];
while(j >= 0 && tmp < a[j])
{
// 将比a[i]大的数往后移
a[j + 1] = a[j];
j--;
}
j++;
// 把a[i]放到正确的位置上
a[j] = tmp;
}
}时间复杂度：$$O(N^2)$$，空间复杂度$$O(1)$$
直接插入排序是稳定的算法，它满足稳定算法的定义。
希尔排序(Shell Sort)是插入排序的一种，它是针对直接插入排序算法的改进。该方法又称缩小增量排序，因DL.Shell于1959年提出而得名。
希尔排序实质上是一种分组插入方法。它的基本思想是：
- 对于n个待排序的数列，取一个小于n的整数gap（gap被称为步长）
- 将待排序元素分成若干个组子序列，所有距离为gap倍的元素放在同一个组中；然后，对各组内的元素进行直接插入排序。这一趟排序完成之后，每一个组的元素都是有序的。
- 然后减小gap的值，并重复执行上述的分组和排序。
- 重复这样的操作，当gap=1时，整个数列就是有序的。
举例说明，假如待分组的11个元素：
{9 10 2 8 6 11 1 7 4 3 5}
过程如下：
第1趟：gap = 11/2 = 5
第一组： 9 11 5
第二组： 10 1
第三组： 2 7
第四组： 8 4
第五组： 6 3
对每一组进行直接插入排序，得到：
第一组： 5 9 11
第二组： 1 10
第三组： 2 7
第四组： 4 8
第五组： 3 6
原数列变成：{5 1 2 4 3 9 10 7 8 6 11}
第2趟：gap = 5/2 = 2
第一组： 5 2 3 10 8 11
第二组： 1 4 9 7 6
对每一组进行直接插入排序，得到：
第一组： 2 3 5 8 10 11
第二组： 1 4 6 7 9
原数列变成：{2 1 3 4 5 6 8 7 10 9 11}
第2趟：gap = 2/1 = 1
第一组：2 1 3 4 5 6 8 7 10 9 11
直接插入排序得到：{1 2 3 4 5 6 7 8 9 10 11}，排序结束。
代码
希尔排序中，首先要选取步长gap的值。选取了gap之后，就将数列分成了gap个组，对于每一个组都执行直接插入排序。
在排序完所有的组之后，将gap的值减半，继续对数列进行分组，然后进行排序。
重复这样的操作，直到 gap < 0 为止。此时，数列也就是有序的了。
因此，只需要修改插入排序的insert_sort() 函数，使它支持gap：
// 增加了起位置（start）、结束位置（end）和步长（gap）
void insert_sort(int a[], int start, int end, int gap)
{
int i,j;
for(i = start + gap; i <= end; i++) //***
{
j = i - gap; //***
int tmp = a[i];
while(j >= start && tmp < a[j]) //***
{
a[j + gap] = a[j]; //***
j -= gap; //***
}
j += gap; //***
a[j] = tmp;
}
}void shell_sort(int a[], int n)
{
int gap = n / 2;
while(gap)
{
// 按照步长来分组
for(int i = 0; i < gap; i++)
// 对每一个分组进行直接插入排序
insert_sort(a, i, n-1, gap);
// 每次完成之后步长减半
gap = gap / 2;
}
}希尔排序的时间复杂度与增量（即步长gap）的选取有关。例如，当增量为1时，希尔排序退化成了直接插入排序，此时的时间复杂度为$$O(N^2)$$，而Hibbard增量的希尔排序的时间复杂度为$$O(N^{3/2})$$。
直接插入排序是不稳定的算法，对于相同的两个数，可能由于分在不同的组中而导致它们的顺序发生变化。