插入排序
归纳起来，常见的排序算法分为如下5类：
1）插入排序：普通插入排序，shell排序等；
2）选择排序：普通选择排序，堆排序；
3）交换排序：冒泡法，快速排序；
4）归并排序；
5）基数排序。
下面，就来实现各个排序算法。要掌握这些算法，大家首先要理解各个算法的具体执行原理和过程，然后应该把这些过程用C语言表达出来。
其中归并排序与基数排序留给大家自学。
基本插入排序的实现是这样的：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。
假如待排数据为：9,6,2,3,10，那么每趟插入排序之后（从小到大），数据的变化情况为：
6,9,2,3,10
2,6,9,3,10
2,3,6,9,10
2,3,6,9,10
基本插入排序的时间复杂度为O(n^2)，是一种稳定排序算法。所谓的稳定排序是指待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj（即i<j）.若在排序后的序列中Ri仍然领先于Rj，则称所用的方法是稳定的。比如下面的数据：
3,6,
其中
简单插入排序的算法实现：
void insert_sort(int a[], int n)
{
int i, j, tmp;
for (i = 1; i < n; i++)
{
tmp = a[i];
j = i - 1;
while (tmp < a[j])
{
a[j+1] = a[j];
j--;
}
a[j+1] = tmp;
}
}
6.1.1 希尔排序
希尔排序是一种经过改进的插入排序算法。基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。具体做法：首先确定一组增量d0，d1，d2，d3，...,dt-1()其中n>d0>d1>...>dt-1=1)，对于i
=0,1,2,...,t-1,依次进行下面的各趟处理：根据当前增量di将n个元素分成di个组，每组中元素的下标相隔为di;再对各组中元素进行直接插入排序。
下面是一个希尔排序的实现算法：
void shellsort(int a[], int n)
{
int i, j, gap, tmp;
gap
= n/2;
while (gap > 0) {
for (i = gap + 1; i <= n; i++)
{
j = i - gap;
while (j > 0)
{
if (a[j] > a[j+gap])
{
tmp = a[j];
a[j]
= a[j+gap];
a[j+gap] = a[j];
}
else
{
j = 0;
}
}
}
gap /= 2;
}
}
希尔排序的复杂度为：O(n1.25)，它不是稳定排序。
