经典排序算法归纳笔记(2)

    上一篇我们回顾了选择和冒泡排序、以及改进的冒泡排序两种算法，今天我们来看一下插入排序和希尔排序。

插入排序
    插入排序的本质是将待排序序列分成有序和无序两部分，通常情况下我们都认为序列的第一元素是有序的，所以插入排序一般是从序列的第二个元素(下标是1的位置)开始。插入排序的的思想是：从无序序列里取出一个元素，我们将这个元素叫做哨岗，然后用一个额外的存储单元将其值保存下来，然后再在有序序列里，从后向前逐次比较它们和哨岗的大小。如果哨岗比有序序列的值还小，则向后移动有序序列里的数据，直到找到第一个比哨岗小的元素为止。还是以前面用到的序列A={6,3,1,9,2,5,8,7,4}为例，看一下算法的执行过程：

   上述插入排序过程，灰色表示有序部分，白色表示无序部分，黄色表示无序序列里当前所选择的哨岗，而橙色表示最后在有序序列为哨岗所找到的合适位置，绿色的圈表示本趟插入时的执行步骤。简单分析一下第八趟的插入过程：
   第八趟插入排序开始前，无序序列里就剩下一个元素了。将元素4标记为哨岗，用一个额外的存空间temp记录下。然后从有序序列最后一个元素9开始，与元素4进行比较。因为9比4大，所以元素9向后移动，然后是有序序列里的元素8，也比4大，同样地，8也往后移动，一直到元素5也比4大，所以继续往后移动。到元素3的时候，它比4小，所以元素4应该安放在元素3后面紧挨着的位置，即元素5腾出来的地方，最后将哨岗的值4设置到那里就OK了。根据上述思路，我们就可以很容易地写出插入排序的核心代码了：

int i,j,tmp;
for(i=1;i<len;i++){     //下标i用于从无须序列里取元素，因为第一个元素a[0]已经有序，所以下标从1开始
   tmp = a[i];          //tmp代表哨岗，每从无序序列里取出一个元素a[i]，就用哨岗tmp将其值保存下来

   for(j=i;j>0;j--){    //下标j用于在有序序列里为哨岗找一个合适的插入位置，j需要在有序序列从后向前遍历
      if(tmp<a[j-1])
        a[j] = a[j-1];  //将有序序列里的元素向后移动
      else
        break;          //找到了合适的位置则退出
   }
   a[j] = tmp;          //将哨岗的值安放在合适的位置上
}

    上述代码的核心逻辑已经很清楚明了了，方便理解插入排序的核心思想。这段代码还可以写得更漂亮点：

int i,j,tmp;
for(i=1;i<len;i++){
    for(j=i,tmp=a[i];j>0 && tmp;j--){
          a[j] = a[j-1];
    }
   a[j] = tmp;
}

    上面两段代码，在gcc标准编译环境下，后者生成的机器指令代码确实比前者要少几条，但在O2、O3优化级别下，两段程序最终生成的机器指令数量是一模一样的。备注：我GCC的版本是4.4.7。

   接下来分析一下插入排序算法的效率。如果待排序序列长度为n，则初始时无序序列长度为n-1，因为第一个元素是有序的。在最好的情况下，比较的次数是n-1次，移动元素0次；最坏的情况是，当序列为逆序时：
   无须序列第一个元素(即整个待排序序列的第二个元素)，比较的次数1，移动1次；
   第二个元素，比较次数2，移动次数2；
   第三个元素，比较次数3，移动次数3；
   ... ...
   第n-1个元素的比较次数为n-1，移动的次数也是n-1；
   所以，插入排序最坏的情况下，其时间复杂度n*(n-1)/2，即O(n^2)。
   这里我们介绍的是传统的插入排序，又叫直接插入排序。和现有查找算法进行结合后，产生了新的插入排序算法，例如折半插入排序、表插入排序、希尔插入排序等，这些衍生出来的算法，核心思想和直接插入排序是一致的，变化的部分主要是在有序序列里找哨岗的位置上进行优化做文章，不像传统的直接插入排序算法是在有序序列从后向前逐次查找的过程。新算法充分借助了二分查找，或者希尔查找算法的优势，可以提高插入排序算法的时间效率。感兴趣的朋友可以自己去写写代码。

希尔排序
   希尔排序又叫递减增量排序算法，它是直接插入排序的一种改进算法。当增量为1时，希尔排序就是直接插入排序。如果待排序序列长度为n，执行第一次希尔排序时，增量一般是n/2；第二次一般是n/4，以此类推，直到增量递减为1，再执行一次直接插入排序。继续看希尔排序的过程，A={6,3,1,9,2,5,8,7,4}：

   上述希尔排序过程中，前两趟里颜色相同的元素属于一个分组，我们对每个这样的分组使用直接插入排序算法。第三趟时，增量已经为1了，即进行直接插入排序。所以，基于直接插入排序，我们可以很容易写出希尔排序的核心算法：

int i,j,tmp,d=len;
while((d/=2)>0){      //增量依次递减到1
  for(i=d;i<len;i++){ //无须序列下标从d开始，且哨岗tmp=a[d]
     for(j=i,tmp=a[i];j>=d && tmp<a[j-d];j-=d){
        a[j] = a[j-d];
     }
     a[j] = tmp;
  }
}

     我们可以看到，希尔排序是插入排序更普遍的情况。希尔排序算法的重点就在于增量的选择方式上，如果增量选择不合适将会大大影响算法的整体效率，这也是的希尔排序的时间复杂分析起来比较困难的主要原因。如果按照通常情况下，待排序列长度折半的方式选取增量的话，其时间复杂度最坏的情况是O(n^2)。

   欲了解更多希尔排序增量的相关知识，请点击“这里”。
   未完，待续...