插入排序和希尔排序

插入排序：

插入排序由n-1趟排序组成。第 i 趟排序前，保证从位置 0 到位置i-1 上的元素已经是排序状态（这是插入排序正确的原因，也是前提条件）。

所以第 i 趟的排序工作就是将 A[i] 放到 A[0,1,2,3...i-1]中的正确的位置。

举个例子。就像玩扑克牌的时候，我们每次拿到的是一张不知道的牌，然后顺着左手中已经有的牌遍历，然后找到它正确的位置后插入这张新牌，这时候在这新插入的牌之前的牌的位置是不变的。但它之后的牌的位置都向后依次移动了一位。

我们给个简单的图例：

代码如下

void InsertSort(int *A,int n)
{
 int i,j;
 int key;
for(i=1;i<n;i++)
{
    key=A[i];

 /*检测是不是在正确的位置上*/
    for(j=i;j>0&&key<A[j-1];j--)
        A[j]=A[j-1];

    A[j]=key;
}
}

基于上面的解释，插入排序应该很好理解了。下面我们来分析一下插入排序的运行时间问题。

 

最坏情况下，当输入的逆序的。内层循环每次都执行，且执行最大次数。

所以 T(n)=2+3+4+....n=O(n^2);

最好情况下，当输入是已排序时，内层循环并不工作 

所以 时间复杂度T(n)=O(n)

所以插入排序的运行时间变化差别是很大的，如果输入几乎被排序，那么插入排序的运行时间很快。

 

对于平均时间的分析，我们假设不存在重复的元素。

我们先来讨论一下插入排序到底做了什么事情。

我们定义一个逆序： i < j 但 A[i]>A[j] 这样的一个序偶（A[i],A[j]）我们称为一个逆序，

所以显然插入排序所做的工作就是同交换相邻元素来消除逆序对，从而带到排序的目的。所以插入排序的运行时间可表示为 T(n)=O(I+n)。其中 I  为逆序数，O(n)为所做的其他线性工作。

 

那么如果我们知道一个任意 输入序列中的平均逆序数，就知道了插入排序的平均运行时间。

 

定理：含N个互异数的数组的平均逆序数是N(N-1)/4

证明如下：

考虑一个序列 A ,和它的反序列 A~ 。则任意一个序偶（a,b）必定是A或者A~中的一个逆序数

比如 序列A=3,6,1,4,8,7,9和它的反序列A~=9,7,8,4,1,6,3      则（3,6）是A~中的一个逆序 （4,6）是A中的一个逆序。

所以对于n个元素的序列A，任意取两个数组成的序偶。必定是A和A~中的一个逆序

所以总的序偶数为   N(N-1)/2  （这是相对于A和A~整体而言。）

所以 A 中的逆序数为总逆序数的一半  即N(N-1)/4.

 

我们看到任意不包含相同元素的数组A的逆序数 为  O(n^2)

所以我们得到差投入排序的平均时间为T(n)=O(n^2).

 

 

希尔排序：

 

我们将希尔排序和插入排序在一起介绍，原因就是希尔排序的原理和插入排序是一样的，只是它多了一个增量序列。

他也是通过比较元素来工作，不同的是它并不像插入排序那样比较相邻的元素，而是比较相距一定距离的元素。各躺比较所用的距离也逐渐减小，直到距离减小为1。

所以他的最后一次进行的就是插入排序。

希尔排序使用的的增量序列H1,H2,H3````Hk.只要h1=1 任何增量序列都是可行的。但存在一些序列比另外一些序列更好。

使用增量Hi排序依次后，对于每一个i 有A[i]<=A[i+Hi]   即所有相距Hi的元素都被排序了 。此时称数组是Hi 排序的。并且在之后的排序中保持它的Hi 排序性。

 

我们给出其代码。我们使用Shell建议的增量序列Hi=N/2和Hi=Hi/2.

void ShellSort(int *A,int n)
{
    int i,j;
    int increase;
    int key;
    for(increase=n/2;increase>0;increase/=2)
    {
        for(i=1;i<n;i+=increase)
        {
            key=A[i];
            for(j=i;j>0&&j-increase>=0;j-=increase)
            {
                if(key<A[j])
                    A[j]=A[j-increase];
                else
                    break;
            }
            A[j]=key;
        }
    }
}

对于希尔排序的运行时间分析通常基于特定的增量序

对于希尔增量 T(n)=O(n)

对Hibbard（1,3,7。。。。2k-1）增量T(n)=O(N^3/2)  (k和3/2为指数)。

对Sedgewick（1,5,19,41,109.。。。）增量T(n)=O(N^7/6) (7/6为指数)。

对于他们的定量分析参考《数据结构与算法分析》P169