冒泡排序

目录

1 算法描述

插入排序是一个简单的基于插入的排序算法。当输入的数据规模较小或者输入数据基本已经排好序时,这个算法比较有效。此算法也用来配合其他比较高级的算法完成排序。

可以用这样一个场景来描述插入排序:假设待排序列的数字都印在卡片上,并且卡片叠在一起朝下扣在桌面上。此时你手中没有一张卡片。排序开始,你用右手从桌上揭起一张卡片放到左手中,此时左手中有一张卡片,当然这张卡片是排好序的。接着,你又揭起第二张卡片,此时你比较这张卡片和左手中的卡片。如果新揭起的卡片上数字大于第一次揭起的卡片上数字,就把第二张卡片放在第一张卡片右边,否则就放在左边。依次类推。这样,你左手的卡片始终是排好序的,右手那一张新揭起来的卡片是本次排序需要插入的,桌面上的剩余卡片是还没有来得及排序的。当桌面和右手都没有卡片时,左手的卡片就是全部排好序的卡片。

2 示例

假设输入数据是(5,2,4,6,1,3),图1给出插入排序的排序过程。

20170702insertionSort.png

Figure 1: (5,2,4,6,1,3)的插入排序过程

3 插入排序伪代码

插入排序的伪代码如图2所示:

20170702insertionSortPseudoCode.png

Figure 2: 插入排序伪代码

4 算法分析

1 给出(5,2,4,6,1,3)的插入排序过程。在伪代码中,索引j表示当前在右手中的扑克牌,它将要被插入到左手已经排好序的序列中去。在每一次的外部 for 循环中,有序子序列为A[1,,j1],未排序的序列为A[j+1,,n],待排序的元素为A[j]。我们用循环不变式来陈述A[1,,j1]的一些特性。

在每一次外部 for 循环中,子序列 A[1,,j1] 对应初始已排序列。

  1. Initialization 我们证明,在第一次循环中,即j=2时,循环不变式成立。这是显然的,当j=2时,子序列A[1,,j1]=A[1],只有一个元素,当然是成立的。
  2. Maintenance 我们证明:在接下来的每一次循环中,循环不变式成立。这是很显然的,每一次我们都移动A[j1],A[j2],A[j]找到合适的位置。这样,下一次 for 循环开始时,子序列 A[1,,j1] 是已经排好的子序列。
  3. Termination 最后我们检验当循环结束时排序结果。对于插入排序来说。当j>n时,排序结束。当j=n+1时子序列A[1,,n]对应已经排好序的子序列,显然这个序列就是我们需要的结果。

以上,我们分析了插入排序的正确性,接下来我们分析插入排序的复杂度。此处我们只分析插入算法的时间复杂度。事实上,一个算法的时间复杂度取决于多种因素,比如输入的数组大小和输入数组的已排序程度。通常来讲一个算法需要的时间随着输入规模的增大而增大。在插入排序中,我们假定伪代码每一行运行需要的时间是固定的,第i行运行需要时间ci。对于每一个j=2,3,,n,定义tj为需要判断 while 循环条件的次数。当 for 循环和 while 循环结束时,判断条件要比循环体多执行一次。最后,我们标记伪代码中每一行需要的时间。

20170702insertionSortComplexity.png

Figure 3: 插入排序的时间复杂度

总的运行时间可以表示为:

T(n)=c1n+c2(n1)+c4(n1)+c5nj=2tj+c6nj=2(tj1)+c7nj=2(tj1)+c8(n1)

需要注意的是,即使相同规模的输入,也会产生不同的运行时间。对于插入排序,当输入已经排好序时,运行时间最少,此时tj=1,j=2,3,,n

T(n)=(c1+c2+c4+c5+c8)n(c2+c4+c5+c8)=An+B

如果输入序列是按逆序排好的序列,则运行时间最长。此时tj=j,j=2,3,,n

T(n)=(c52+c62+c72)n2+(c1+c2+c4+c52c62c72+c8)n(c2+c4+c5+c8)

最差情况可以表述为T(n)=An2+Bn+C

在插入排序的时间复杂度中,我们给出了最好情况和最差情况的复杂度。在以后的分析过程中,我们只分析最差运行时间,也就是对于输入规模为n的输入的最长运行时间。这样做有三点理由:

  1. 最差运行时间给出了算法运行时间的上界。也即给出了算法运行永远不会超过的时间。
  2. 对于一些算法,最差情况经常发生。
  3. 平均时间复杂度通常趋近于最差情况,至少在数量级上是相同的。

5 插入排序C代码实现

编辑环境:Emacs;编译:GCC;调试:GDB;操作系统:Windows XP SP3;CPU:Intel core i5-2400; memory:3.16GB

 1: 
 2: int *  insertion_sort (int   a[] )
 3:   {
 4:       int i=0,j=0,key=0;
 5:       for(j=1;j<10;j++)
 6:       {
 7:           key = a[ j ];
 8:           i = j-1;
 9:           while (i>-1 && a[ i ] > key )
10:           {
11:               a[ i + 1 ] = a [ i ];
12:               i--;
13:           }
14:           a[ i+1 ] = key;
15:       }
16:       return a;
17:   }