排序的故事---插入排序

     说起插入排序，其实它的工作原理十分简单，举例来说一下，按照从小到大顺序排列下面的一组数：
                           9   5   7   3   4
     从第二个数起，把它之后的部分看成是未排列的部分，第一个元素是已排序的部分，然后依次把未排序的部分的第一个元素取出，插入到已排好的部分的正确位置，于是已排好部分的元素个数加一，未排好部分元素个数减一。一直到未排好部分元素的个数为零时结束。于是上述的例子的排序过程如下：
                           9   5   7   3   4
                           5   9   7   3   4
                           5   7   9   3   4
                           3   5   7   9   4
                           3   4   5   7   9
     在一些传统的教科书里面中一般这样来作插入工作：如果要把X[i]从X[0]插入到X[i-1]这一个已经排好的段落之中，令X[i]与X[i-1],X[i-2],...,X[1],X[0]相比较，如果X[j]>=X[i](0<=j<=i-1)，就把X[j]向后移一位，直到X[j]小于X[i]，X[i]就放在X[j+1]处。C语言的代码如下：

void sort(int input[], int n)
{
         int current;
         int x;
         int i;
         for(current=1; current
         {
              x = input[current];
              i = current - 1;
              while(x=0)
              {
                 input[i+1] = input[i];
                 i--;
              }
              input[i+1] = x;
         }
}

     在最坏的情况下，每一个X[i]都比较i次，也就是于每一个X[i-1],X[i-2],...,X[1],X[0]都比较过，然后才找到正确的位置，于是总比较次数是：1+2+3+...+(n-1)=n(n-1)/2，也就是说这是个O(n^2)的算法。在平均情况下，如果用数学推倒还是与n^2成正比的，所以它的速度是很慢的，但是这是可以加快的。但是需要解决两个问题：
      第一. 如何把数据插到已排好的一串数据中
      第二. 如何加快数据移动的速度         
     对于第一个问题，我们可以用到二分查找法(Binary Search)，其实在一组已经排好的数据中找数据，或者是找位置，如果不用很特殊的数据结构，那么二分查找法(Binary Search)就一定可以用的上。通过数学推倒可以得出通过二分查找法(Binary Search)后比较次数与nlogn成正比的，是小于n^2的。
     那么第一个问题解决了，对于第二个问题，我们可以用到<string.h></string.h>的函数：
          void*memmove(void*dest,const void*src,int count);
     这表示从src指出的地方起，移动count个char到dest所指出的地方去，一般而言，好的编译程序的链接库多半会用汇编语言来写这个函数，而不会用C写，因此效率会比高级语言好，更重要的是，很多机器硬件都有一个移动一个区域的(block move)指令，因此就更快了。所以可以把X[j+1]的地址给src，把X[j+2]的地址给dest，把要移动的数组个数给count，于是使用memmove()一次就可以完成移动，效率是相当高的。C代码如下：

#include <string.h></string.h>
#include <stdio.h></stdio.h>
#include <stdlib.h></stdlib.h>
#define  SIZE sizeof(int)/sizeof(char)

void  sort(int input[], int n)
{
        int  current, pos;
        int  low, high, mid;
        int  x;
        for (current = 1; current < n; current++)
        {
               x = input[current];
               pos = -1;
               if (x < input[0])
                     pos = 0;
               else if (x <= input[current-1])
               {
                    low  = 0;
                    high = current - 1;
                    while (high - low > 1)
                    {
                        mid = (low + high) / 2;
                        if (x >= input[mid])
                            ow = mid;
                        else
                            high = mid;
                    }
                    pos = low + 1;
               }
               if (pos >= 0)
               {
                     memmove((void *) &input[pos+1], (void *) &input[pos],
                             SIZE*(current-pos));
                     input[pos] = x;
               }
        }
}

      好了说了大半天，终于把我当时学习数据结构时的插入排序法改进的还算完美，很可惜当时老师没有鼓励我们改进书上的算法，直到今天我才回头来重新研究这个算法，也许我曾经太相信大学的教育，相信老师，可是慢慢发现自己很失望，但失去的不会再回来，“不要为洒掉的牛奶而哭泣”。每天靠自己的努力来充实生活吧。对了，最后还要补充一下，插入排序具有稳定性的......