常用排序算法之插入排序 ( 直接插入排序、希尔排序 )

插入排序的方法是：从初始有序的子集合开始，不断地把新的数据元素插入到已排列有序子集合的合适位置上，使子集合中数据元素的个数不断增多，当子集合等于集合时，插入排序算法结束。常用的插入排序有直接插入排序和希尔排序。

直接插入排序

方法：顺序地把待排序的数据元素按其关键字值的大小插入到已排序数据元素子集合的适当位置。子集合的数据元素从只有一个数据元素开始逐次增大，当子集合大小最终和集合大小相同时排序完毕。

C++实现：

InsertSort.cpp

 1 void InsertSort( DataType a[], int n )
 2 {
 3     int i, j;
 4     DataType temp;
 5 
 6     for ( i = 0; i < n-1; i ++ )
 7     {
 8         temp = a[i+1];
 9         j = i;
10         while ( j > -1 && temp.key <= a[j].key )
11         {
12             a[j+1] = a[j];
13             j --;
14         }
15 
16         a[j+1] = temp;
17     }
18 }

时间复杂度：分最好、最坏和随机三种情况。

    最好：待排数据集合已经排好序。此时，while循环执行次数为0，而外层for循环每次比较次数为1，数据元素赋值语句执行次数为2。因此整个排序算法的比较次数为 n-1 ,赋值语句执行次数为 2(n-1) ,所以直接插入排序算法最好情况下的时间复杂度为 O(n) 。

    最坏：待排数据集合以反序排列。这时，while循环执行次数为 i ,而外层for循环中的比较次数和赋值语句执行次数如下：

        比较次数 = [i=1,i++,i<n-1](i+1) = (n-1)(n+2)/2

        移动次数 = [i=1,i++,i<n-1](i+2) = (n-1)(n+4)/2

    因此，直接插入排序算法最坏情况下的时间复杂度是 O(n^2) 。

    随机：元素随机排列，则数据元素的期望比较次数和期望移动次数约为 n^2/4 。因此，其时间复杂度为 O(n^2) 。

直接插入排序算法的时间效率越高，其时间效率在 O(n) 到 O(n^2) 之间，此结论是希尔排序算法成立的基础。

空间复杂度为 O(l)  。

---------------------------------------------------------------------------------

希尔排序

方法：把待排序的数据元素分成若干个小组，对同一小组内的数据元素用直接插入法（也可用其他排序方法）排序；小组的个数逐次缩小；当完成了所有数据元素都在同一组内的排序后排序过程结束。又称作缩小增量排序。

算法中，增量值的取值方法为：

    增量 d[0] = n / 2,  d[1] = d[0] / 2, d[2] = d[1] / 2, ... , d[n] = d[n-1] / 2 = 1.

    增量为1时，所有元素均在同一组内，数据已接近有序，采用直接插入排序算法时间效率高。

C++实现：

ShellSort.cpp

 1 void ShellSort( DataType a[], int n, int d[], int numOfD )
 2 {
 3     int i, j, k, span;
 4     DataType temp;
 5     for (m = 0; m < numOfD; m ++)
 6     {
 7         span = d[m];
 8         for (k = 0; k < span; k ++)
 9         {
10             for (i = k; i < n-span; i = i+span)
11             {
12                 temp = a[i+span];
13                 j = i;
14                 while (j > -1 && temp.key <= a[j].key)
15                 {
16                     a[j+span] = a[j];
17                     j = j - span;
18                 }
19                 a[j+span] = temp;
20             }
21         }
22     }
23 }

时间复杂度：希尔排序是四重循环，但每重循环的次数都很小，并且当增量递减、小组变大时，小组内的数据元素数值已基本有序，而越有序的直接插入排序算法的时间效率越高。若增量的取值较合理，希尔排序的时间复杂度约为 O(n(lbn)^2) 。

空间复杂度： O(1) 。

由于希尔排序算法是按增量分组进行排序，因此希尔排序是一种不稳定的排序算法。