1.直接插入排序

直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。

设数组为a[0…n-1]。

1. 初始时，a[0]自成1个有序区，无序区为a[1..n-1]。令i=1

2. 将a[i]并入当前的有序区a[0…i-1]中形成a[0…i]的有序区间。

3. i++并重复第二步直到i==n-1。排序完成。

代码如下：

voidInsertSort(int*a,size_tn)//直接插入排序{assert(a);for(inti=1;i<n;++i){inttmp=a[i];intj=i-1;while(j>=0&&a[j]>tmp){a[j+1]=a[j];--j;}a[j+1]=tmp;}}


2.希尔排序

该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

voidshellsort2(inta[],intn){intj,gap;for(gap=n/2;gap>0;gap/=2)for(j=gap;j<n;j++)//从数组第gap个元素开始if(a[j]<a[j-gap])//每个元素与自己组内的数据进行直接插入排序{inttemp=a[j];intk=j-gap;while(k>=0&&a[k]>temp){a[k+gap]=a[k];k-=gap;}a[k+gap]=temp;}}