Chinaunix首页 | 论坛 | 博客
  • 博客访问: 464095
  • 博文数量: 68
  • 博客积分: 2606
  • 博客等级: 上尉
  • 技术积分: 1308
  • 用 户 组: 普通用户
  • 注册时间: 2010-12-13 23:01
文章分类
文章存档

2012年(6)

2011年(62)

分类: C/C++

2011-09-01 16:16:07

------------------------------------------
本文为本人原创,欢迎转载!
转载请注明出处:snowboy.blog.chinaunix.net
雪夜流星
------------------------------------------
1.二分排序也叫折半插入排序,是直接插入排序的一种改进,查找插入位置的时候利用了二分查找算法,从而减少了比较和移动这两种操作的次数。实现代码如下:
  1. #include <stdio.h>
  2. #include <stdlib.h>


  3. /*****************************************************************

  4.  *功能描述:二分排序(折半排序)算法

  5.  *传入参数:num:需要排序的数组首地址, n:数组的元素

  6.  *传出参数:num:排序后的数组首地址,传入参数和传出参数空间复用,降低空间复杂度

  7.  *返回值: 无

  8.  ****************************************************************/


  9. void B_insert_sort(int *num, int n)
  10. {
  11.     int tmp, i, j, low, high, m;
  12.     
  13.     /*判断参数的合法性,当指针为空或者数组中只有一个元素时,直接返回*/
  14.     if((num == NULL) || (n<2))
  15.     {
  16.         return;
  17.     }

  18.     /*把第一个节点当成有序表,将第二个节点插入到这个表中,    有序表
  19.     更新为两个    节点的表,把后面的节点逐个插入到不断更新的有序表中*/
  20.     for(i=1; i<n; i++)
  21.     {
  22.         tmp = num[i];
  23.         low = 0;
  24.         high = i-1;

  25.         /*二分查找算法:当下界low大于上界时,能够确定插入元素的位置为high+1,因为上界的
  26.         最后一次更新是tmp <= num[m],num[m]存放的是比tmp大并且最接近tmp的数,tmp插入到
  27.         num[m]的位置是最适合的,此处的m=high+1*/
  28.         while(low<=high)
  29.         {
  30.                 m = (low+high)/2;
  31.                 if(tmp <= num[m])
  32.                 {
  33.                     high = m - 1;
  34.                 }
  35.                 else
  36.                 {
  37.                     low = m + 1;
  38.                 }
  39.         }
  40.         
  41.         /*由于程序是将num[i]插入到含i个元素(num[0]--num[i-1])的有序表中,前面已经将
  42.         num[i]的值保存在临时变量中,在找到插入的位置后,将插入位置及后面的元素均往后移
  43.         一位,把high+1位置腾出来放待插入元素num[i]*/
  44.         for(j=i-1; j>=high+1; j--)
  45.         {
  46.             num[j+1] = num[j];
  47.         }
  48.         num[high+1] = tmp;
  49.         /* 因为while退出条件为low>high,其变化量均为1,退出循环时必为low=high+1,每次查找
  50.          完毕后,low总比high大一,num[low]总是存放第一个比tmp大的数,因此亦可以用下面的一段程序
  51.          替代上面的代码
  52.            for(j=i-1; j>=low; j--)
               {
                   num[j+1] = num[j];
               }
               num[low] = tmp;
  53.         */
  54.     }

  55.     return;
  56. }

  57. int main(void)
  58. {
  59.     int i;
  60.     int num[5] = {5, 4, 3, 2, 1};
  61.     
  62.     printf("before:\n");
  63.     for(i=0; i<5; i++)
  64.     {
  65.         printf("num[%d]:%d\n", i, num[i]);
  66.     }
  67.     
  68.     B_insert_sort(num, 5);

  69.     printf("after:\n");
  70.     for(i=0; i<5; i++)
  71.     {
  72.         printf("num[%d]:%d\n", i, num[i]);
  73.     }

  74.     return 0;
  75. }
阅读(2444) | 评论(1) | 转发(1) |
给主人留下些什么吧!~~