---

基本插入排序的实现是这样的：每次将一个待排序的数据元素，插入到前面已经排好序的数列中的适当位置，使数列依然有序；直到待排序数据元素全部插入完为止。

下面是插入排序算法的实现代码：

 

void insertsort(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;

     }

}

 

基本插入排序的时间复杂度为O(n²)，是一种稳定排序算法。

 

希尔排序是一种经过改进的插入排序算法。基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。具体做法：首先确定一组增量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(n^1.25)，它不是稳定排序。