插入排序总结

前言

1、插入排序(Insertion sort)的基本思想

1）插入排序的基本思想：每次将一个待排序的记录，按其关键字大小插入到前面已经排序序的子文件的适当位置，直到全部记录插入完成为止。

2）插入排序方法的代表：直接插入排序和希尔排序

一、直接插入排序

1、直接插入排序的基本思想

假设带排序的记录存放在数组R[1…n]中。初始时，R[1]自成1个有序区，无序区为R[2..n]。从i=2起直至i=n为止，依次将R[i]插入当前的有序区R[1…i-1]中，生成含n个记录的有序区。

直接插入排序的基本操作是将当前无序区的第1个记录R[i]插人到有序区R[1…i-1]中适当的位置上，使R[1…i]变为新的有序区。因为这种方法每次使有序区增加1个记录，通常称增量法。

2、直接插入排序算法的核心

准备需插入的数据R[2…n].
在满足条件下，为插入值腾空间（数据向后移）
在腾出地方上插入值

3、直接插入排序算法的实现

void InsertSort(int *arr,int len)
{
  int i,j;        // i主要记录当前位置，j记录i之前的位置
  int curValue;      // 保存i位置的当前值
  for (i=1;i<len;i++)    // 依次插入arr[1], arr[2], arr[len-1]
  {
    if (arr[i]<arr[i-1])// 满足条件就执行插入操作
    {
      curValue = arr[i];      // 保存无序区的第一个值
      j = i-1;          // 记录i之前的位置
      do            
      {
        arr[j+1] = arr[j];    // 数据往后移，为需插入值腾空间
        j--;
      } while (curValue<arr[j]);  // 
      arr[j+1] = curValue;    // 在正确的位置上插入无序区的第一个值
    }
  }
}

4、直接插入排序算法的性能分析

直接插入排序是一个就地排序，且它是稳定的。直接插入排序的最好时间复杂度为O(n)，最坏时间复杂度为O(n^2)，平均时间复杂度为O(n^2)。

二、希尔排序(Shellsort)

1、希尔排序的基本思想

先取一个小于n的整数 $d_1$ 作为第一个增量，把文件的全部记录分为 $d_1$ 个组。所有距离为 $d_1$ 的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后取第二个增量 $d_2<d_1$ 重复上述的分组和排序，直至所取的增量 $d_t=1(d_t<d_{t-1}<...<d_2<d_1)$ ，即所有记录放在同一组中进行直接插入排序为止。

先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的。

该方法实质上是一种分组插入方法。

2、希尔排序算法的核心

增量d的更新
直接插入排序

3、希尔排序算法的示例

以n=10的一个数组49, 38, 65, 97, 26, 13, 27, 49, 55, 4为例

第一次 gap = 10 / 2 = 5

49 38 65 97 26 13 27 49 55 4

1A 1B

2A 2B

3A 3B

4A 4B

5A 5B

1A,1B，2A,2B等为分组标记，数字相同的表示在同一组，大写字母表示是该组的第几个元素，每次对同一组的数据进行直接插入排序。即分成了五组(49, 13) (38, 27) (65, 49) (97, 55) (26, 4)这样每组排序后就变成了(13, 49) (27, 38) (49, 65) (55, 97) (4, 26)，下同。

第二次 gap = 5 / 2 = 2

排序后

13 27 49 55 4 49 38 65 97 26

1A 1B 1C 1D 1E

2A 2B 2C 2D 2E

第三次 gap = 2 / 2 = 1

4 26 13 27 38 49 49 55 97 65

1A 1B 1C 1D 1E 1F 1G 1H 1I 1J

第四次 gap = 1 / 2 = 0 排序完成得到数组：

4 13 26 27 38 49 49 55 65 97

4、希尔排序算法的实现

void ShellSort(int a[], int n)
{
    int d;
    for (d=n/2; d>0; d=d/2)                // 设置增量
    {
        for (int i=d; i<n; i+=d)
        {
            if (a[i]<a[i-d])
            {
                int j = i-d;
                int temp = a[i];
                do 
                {
                    a[j+d] = a[j];
                    j = j-d;
                } while (temp<a[j]&&j>=0);
                a[j+d] = temp;
            }        
        }
    }
}

5、希尔排序算法的性能分析

希尔排序不是稳定的，希尔排序的平均时间复杂度为O(nlogn)，最坏时间复杂度为O(n^S)(1<S<2).

参考:http://blog.csdn.net/morewindows/article/details/6668714