Chinaunix首页 | 论坛 | 博客
  • 博客访问: 3835811
  • 博文数量: 146
  • 博客积分: 3918
  • 博客等级: 少校
  • 技术积分: 8584
  • 用 户 组: 普通用户
  • 注册时间: 2010-10-17 13:52
个人简介

个人微薄: weibo.com/manuscola

文章分类

全部博文(146)

文章存档

2016年(3)

2015年(2)

2014年(5)

2013年(42)

2012年(31)

2011年(58)

2010年(5)

分类: C/C++

2011-08-28 11:05:18

    插入排序是一种比较适合人类思维的排序方法。平时打扑克的时候,大家都是习惯把当前的摸到的扑克插入到已经排好的扑克之中,本质就是一种插入排序。

    插入排序的思想就是,新的元素插入之前,我的数组是已序的,这需要把新元素插入到已序数组的合适位置即可。

    当然插入排序效率不高,对于大规模的随机数据,不能采用这种方法,但是这也不是说插入排序一无是处,下面两种情况完全可以采用插入排序。

     1 小规模的排序,比如数组只有十几个元素,或者几十个元素。,所以很多复杂排序算法,递归到数组个数比较小的时候,停止递归,采用插入排序,能够减少函数调用,同时提高效率。参见前文提到的归并排序mergesort的C实现
     2 如果数组几乎排好序了,采用插入排序性能也不错,哪怕数组规模很大。下一篇博文三者取中快速排序会提到。

     下面的代码首先遍历一遍数组,选择最小的元素放在最左边left,作为一个观察哨。

     如果没有这个观察哨,我们总要判断 j 是否大于left,每次都要判断,影响性能。有个观察哨,我们不需要关心j 是否大于left,因为当前要插的元素,不会比left位置上的更小 。
   
 参考文献:
 1算法:C语言实现  Robert Sedgewick著,霍红卫译

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<time.h>

  4.  void swap(int *a,int *b)
  5. {
  6.     int t = *a;
  7.      *a = *b;
  8.      *b = t;
  9. }

  10. int insertsort(int array[],int left,int right)
  11. {
  12.     int i;
  13.     int j;
  14.     int cur;
  15.     
  16.     /*find the min element ,put it in the leftest position, use it as a guard*/
  17.     for(i = right;i>left;i--)
  18.     {
  19.       if(array[i] < array[i-1])
  20.          swap(&array[i],&array[i-1]);
  21.     }

  22.     for( i = left + 2; i <= right;i++)
  23.     {
  24.         cur = array[i];
  25.         j = i;

  26.         while(cur < array[j-1]) 
  27.         {
  28.            array[j] = array[j-1]; /*比当前元素大的,往右移,给当前元素腾位置*/
  29.            j--;
  30.         }
  31.         array[j] = cur;
  32.     }
  33. }


  34. int test_insertsort(int number)
  35. {
  36.     int i;
  37.     
  38.     int *array = malloc(number*sizeof(int));
  39.     if(array == NULL)
  40.     {
  41.           printf("malloc failed\n");
  42.           return -1;
  43.     }
  44.   

  45.     printf("----------------------------------------before insert sort----------\n");
  46.     srand(time(NULL));
  47.     for(i = 0;i<number;i++)
  48.     {
  49.         if(number < 100)
  50.          array[i] = rand()%1000;
  51.         else
  52.          array[i] = rand();
  53.         printf("\tarray[%-6d] = %-6d\n",i,array[i]);
  54.     }

  55.     printf("----------------------------------------after insert sort-----------\n");
  56.     
  57.     insertsort(array,0,number-1);
  58.     
  59.     if(number < 25)
  60.     {
  61.         for(i = 0;i<number;i++)
  62.         {
  63.             printf("\tarray[%-6d] = %-6d\n",i,array[i]);
  64.         }
  65.     }

  66.     for( i = 0 ; i < number-1;i++)
  67.     {
  68.          if(array[i] > array[i+1])
  69.          {
  70.              printf("insert sort failed \n");
  71.              break;
  72.          }
  73.     }
  74.     
  75.     free(array);
  76.     return 0;
  77.     
  78. }

  79. int main(int argc,char *argv[])
  80. {
  81.     if(argc != 2)
  82.     {
  83.         printf("usage : ./test number\n");
  84.         return -1;
  85.     }

  86.     int number = atoi(argv[1]);
  87.     if(number <= 0)
  88.     {
  89.          printf("number is 0,please input a big number \n");
  90.          return -2;
  91.     }

  92.     test_insertsort(number);
  93. }
阅读(4448) | 评论(0) | 转发(1) |
给主人留下些什么吧!~~