`
aladdin_leon
  • 浏览: 118359 次
  • 性别: Icon_minigender_1
  • 来自: 哈尔滨
社区版块
存档分类
最新评论

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

阅读更多

     说起插入排序,其实它的工作原理十分简单,举例来说一下,按照从小到大顺序排列下面的一组数:
                           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语言的代码如下:

  1. void sort(int input[], int n)   
  2. {   
  3.          int current;   
  4.          int x;   
  5.          int i;   
  6.          for(current=1; current
  7.          {   
  8.               x = input[current];   
  9.               i = current - 1;   
  10.               while(x=0)   
  11.               {   
  12.                  input[i+1] = input[i];   
  13.                  i--;   
  14.               }   
  15.               input[i+1] = x;   
  16.          }   
  17. }  

     在最坏的情况下,每一个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代码如下:

  1. #include <string.h></string.h>   
  2. #include <stdio.h></stdio.h>   
  3. #include <stdlib.h></stdlib.h>   
  4. #define  SIZE sizeof(int)/sizeof(char)   
  5.   
  6. void  sort(int input[], int n)   
  7. {   
  8.         int  current, pos;   
  9.         int  low, high, mid;   
  10.         int  x;   
  11.         for (current = 1; current < n; current++)   
  12.         {   
  13.                x = input[current];   
  14.                pos = -1;                
  15.                if (x < input[0])        
  16.                      pos = 0;              
  17.                else if (x <= input[current-1])    
  18.                {                                    
  19.                     low  = 0;                          
  20.                     high = current - 1;               
  21.                     while (high - low > 1)    
  22.                     {   
  23.                         mid = (low + high) / 2;    
  24.                         if (x >= input[mid])    
  25.                             ow = mid;     
  26.                         else  
  27.                             high = mid;   
  28.                     }   
  29.                     pos = low + 1;   
  30.                }   
  31.                if (pos >= 0)    
  32.                {   
  33.                      memmove((void *) &input[pos+1], (void *) &input[pos],   
  34.                              SIZE*(current-pos));   
  35.                      input[pos] = x;   
  36.                }   
  37.         }   
  38. }  

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

分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics