MM93 阅读(20) 评论(0)

  从这一篇博文开始,我们将开始讨论排序算法。所谓排序算法,就是将给定数据根据关键字进行排序,最终实现数据依照关键字从小到大或从大到小的顺序存储。而这篇博文,就是要介绍一种简单的排序算法——插入排序(Insertion Sort)。

  为了使精力专注于排序算法本身,而不是对数据的分析、处理,若无特殊说明,我们每一篇介绍排序算法的博文,均做如下假定:

  1.数据存储于一个数组之中,且数据个数N即数组大小

  2.数据类型即int

  3.排序目标为从小到大

 

 

  那么,插入排序是怎样的算法呢?其实插入排序的思想来源就是“插队”

  首先我们想象一下这个现实场景:有一个长度为n的队伍,队伍中每个人都比前面的人要高,你是新来的第n+1个人,现在位于队尾,请问你该怎么找到自己应处的位置,以使得队伍保持原有顺序(从矮到高)?

  这个问题所有人都会解,那就是:我与前一个人比较,若我更矮,则我站到他前面,持续此比较直至我比我前面的人高或同样高,或者我来到第一名为止。

  这个问题和这个问题的解法,就是插入排序的根本。

 

  现在我们将场景转换到数组中:有一个大小为n的int型数组a,a[0]至a[n-2]已按从小到大排好序,但是第a[n-1]即最后一个元素是“新来的”,现在要将新元素放到正确的位置上,以使得数组保持从小到大的顺序,该怎么做?

  同样的,我们令新元素不断地与前一个元素比较,若小于前一个元素则两者交换位置,直至新元素大于等于前一个元素,或新元素到达a[0]时停止。

void unfinishedInsertionSort(int *a, unsigned int n)
{
    //“新元素”的当前位置从N-1开始
    int CurrentPosition = n - 1;

    //只要新元素尚未到达a[0],且前一个元素小于新元素,则不断地令新元素与前一个元素交换位置
    for (;CurrentPosition != 0 && a[CurrentPosition - 1] > a[CurrentPosition];--CurrentPosition)
        swap(&a[CurrentPosition], &a[CurrentPosition - 1]);
}

 

  上述想法就是插入排序的雏形:若元素Xn前面的X0到Xn-1均已排好序,那么Xn只需要不断地向前“插入”,直至前一个元素与Xn的大小关系符合顺序(如需从小到大排序,则Xn的前一个元素不大于Xn即两者关系符合顺序),或Xn到达第一个位置即可完成排序。

 

 

  不难发现,雏形中尚待解决的问题就是:如何令Xn前面的所有元素排好顺序?

  这个问题可以尝试用递归的想法解决:要令Xn排好序,就需要令X0到Xn-1有序,而要令Xn-1排好序,则需要令X0到Xn-2有序……最后会发现,要想令X1排好序,则需要令X0到X0有序,而X0到X0一定是有序的,因为只有一个元素,也就是说递归的基准情形出现了,而根据X0到X0的有序,可以得到X0到X1的有序,X0到X2的有序,直至得到X0到Xn-1的有序,也就有了X0到Xn的有序。因此这个递归的想法可行,而且这个想法就是插入排序从雏形到完整的解决思想。

  

  将上述想法与插入排序的雏形相结合后,我们就得到了插入排序的实现方法:设数组a有n个元素,令下标x从1递增至n-1,对于每个a[x]我们都执行“插入”操作(即插入排序的雏形操作)。

  下面为插入排序的例程:

void InsertionSort(int *a, unsigned int size)
{
    int temp;    //temp用于暂存执行插入的元素的值,使用temp可以避免元素间的交换
    int CurPos;   //CurPos表示执行插入的元素当下所处的下标
    
    //StartPos表示执行插入操作的元素开始插入时的下标
    //令StartPos从1递增至size-1,对于每个a[StartPos],我们执行向前插入的操作
    for (int StartPos = 1;StartPos < size;++StartPos) 
    {
        temp = a[StartPos];   
        for (CurPos = StartPos;CurPos != 0 && a[CurPos - 1] > temp;--CurPos)
            a[CurPos] = a[CurPos - 1];   //令前一个元素后移,相当于令当前元素前移,但循环结束后记得令temp执行真实的移动

        a[CurPos] = temp;
    }
}

 

  计算插入排序的时间复杂度并不难,最坏的情况是数组中元素恰好完全反序,此时插入排序的内循环必然执行至CurPos==0为止,而外循环从StartPos=1至StartPos=size-1共size-1次,每一次内循环执行StartPos次,即内循环总共执行1+2+3+……+size-1次,即size(size-1)/2次,即O(n2)

 

 

  大部分人在学习C语言时就接触过冒泡排序,所以我们将不再对冒泡排序进行介绍。从时间复杂度上看,插入排序和冒泡排序是一样的,都是O(n2),但是在实际执行时,插入排序会比冒泡排序好得多,原因就是在数据“部分有序”时,插入排序可以减少很多比较次数,而冒泡排序的比较则是“固定的”。

  举例来说,现有数据1,2,3,4,5,7,6。若插入排序则需比较7次,交换1次(元素2,3,4,5,7均一次比较即结束,元素6与7比较一次,交换,再与5比较一次,结束)。而冒泡排序则需比较6+5+4+3+2+1=21次,交换1次。

  造成冒泡排序与插入排序间差异的主要原因就是:插入排序的比较“更充分地利用了已存在的顺序信息”,而冒泡排序无论如何都需要(N-1)+(N-2)+(N-3)+……+1次比较。其实在数据“接近有序”的情况下,插入排序几乎是最快的排序,完全有序的数据其只需要N-1次比较即结束排序。可以说在O(n2)这个级别的排序算法中,插入排序是绝对的首选。

  不过我们再次回顾上述例子,会发现两个排序算法虽然需要的比较次数不同,但需要的交换次数却是相同的,即使你换一个数据序列,这两个排序算法需要的交换次数依然是一样多,这是为什么呢?我们下一篇博文将揭开这个秘密。

 

 

 

 

  附:选择排序也是常见的初学排序算法,它需要的比较次数为N+N-1+N-2+……+2,比冒泡排序还要多N-1次,但是它的交换次数有可能比插入和冒泡都要少,比如数据5,4,3,2,1需按从小到大排序,若使用插入或冒泡排序,将需要10次交换,而选择排序的交换操作只需要2次。但是实际使用时插入排序依然比选择排序优先考虑,因为:

  1.选择排序的“实质交换”虽然可以更少,但形式上来说,选择排序是固定执行N次交换的:每一趟我们都会找出当前最小元素然后将其交换至正确位置,所以肯定有N次交换。只不过会出现“当前元素恰好在正确位置上”的情况,从而没有“实质交换”罢了,但代价依然是有的,比如判断当前元素位置与目标位置是否不同,或直接执行自己与自己的交换。而这些都会使得选择排序没有理想的那么快。

  2.若想选择排序的交换次数趋向于少,则数据就越需趋向于反序。而如果编程时对数据的预期是趋向于反序,那么进行其它更高级的算法会更快,即使必须选择O(n2)级别的算法,也可以考虑执行反序的插入排序,而后将数据翻转过来。