Chinaunix首页 | 论坛 | 博客
  • 博客访问: 313798
  • 博文数量: 144
  • 博客积分: 0
  • 博客等级: 民兵
  • 技术积分: 493
  • 用 户 组: 普通用户
  • 注册时间: 2013-08-14 17:08
文章分类

全部博文(144)

文章存档

2015年(42)

2014年(19)

2013年(83)

我的朋友

分类: LINUX

2015-03-16 14:31:13

原文地址:折半插入排序 作者:kathy870513

    直接插入排序在查找待排序记录位置时使用的是顺序查找,所以在有序序列中查找待插入记录的位置时可以使用折半查找法。
    基本思想:因为R[1..i-1]是一个按关键字有序的序列,可以利用折半查找定位记录R[i]在R[1..i]中插入位置,再将插入位置开始的记录顺序后移一个位置,将R[i]插入到指定位置。
    程序:
  1. #include <stdio.h>
  2. #include <unistd.h>
  3. #include <stdlib.h>
  4. #include <time.h>
  5. #define MAXSIZE 10
  6. typedef struct
  7. {
  8.  int length;
  9.  int arr[MAXSIZE+2];
  10. }list;
  11. void insert(list* p)
  12. {
  13.  int i,j;
  14.  int low,high,mid;
  15.  for (i = 2; i <= p->length; i += 1)
  16.  {
  17.   p->arr[0] = p->arr[i];
  18.   low = 1;
  19.   high = i-1;
  20.   while (low <= high)
  21.   {
  22.    mid = (low+high) / 2;
  23.    if (p->arr[0] <= p->arr[mid])
  24.    {
  25.     high = mid-1;
  26.    }
  27.    else
  28.    {
  29.     low = mid+1;
  30.    }
  31.   }
  32.   for (j = i-1; j >= high + 1; j --)
  33.   {
  34.    p->arr[j+1] = p->arr[j];
  35.   }
  36.   p->arr[high+1] = p->arr[0];
  37.  }
  38. }
  39. int main()
  40. {
  41.  int i;
  42.  list *plist;
  43.  plist = (list*)malloc(sizeof(list));
  44.  plist->length = MAXSIZE;
  45.  plist->arr[MAXSIZE+2] = 0;
  46.  srand((unsigned int)time(NULL));
  47.  for (i = 1; i < MAXSIZE+1; i += 1)
  48.  {
  49.   plist->arr[i] = (rand() % 100);
  50.   printf("array before:%d\n", plist->arr[i]);
  51.  }
  52.  insert(plist);
  53.  printf("\n");
  54.  for (i = 1; i < MAXSIZE+1; i += 1)
  55.  {
  56.   printf("array after:%d\n", plist->arr[i]);
  57.  }
  58.  return 0;
  59. }
算法分析:折半插入排序比直接插入排序明显减少了关键字之间的比较次数,但记录的移动次数没有改变。因此,折半插入排序的时间复杂度仍为O(n*n),但是因为减少了比较次数,所以该算法仍然比直接插入排序好一点。
 
阅读(1136) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~