Chinaunix首页 | 论坛 | 博客
  • 博客访问: 591065
  • 博文数量: 92
  • 博客积分: 5026
  • 博客等级: 大校
  • 技术积分: 1321
  • 用 户 组: 普通用户
  • 注册时间: 2008-02-28 11:04
文章分类

全部博文(92)

文章存档

2011年(9)

2010年(17)

2009年(12)

2008年(54)

我的朋友

分类: C/C++

2008-03-31 11:42:37

//算法分析:平均时间复杂度o(n2),空间复杂度o(n),正序时时间复杂度为o(n),反序时为o(n2),是稳定性的算法(相同记录的相对位置不会改变)
 
void insert_sort(int* buf, int len) {
 int compare_count = 0;
 int move_count = 0;
 for(int i=1; i  int now = buf[i];
  compare_count++;
  if(now > buf[i-1])continue;
  //引入哨兵
  int temp = buf[-1];
  buf[-1] = now;
  int j=i-1;
  do {
   compare_count++;
   move_count++;
   buf[j+1] = buf[j];
   j--;
  } while(now < buf[j]);
  move_count++;
  buf[j+1] = now;
  //恢复哨兵
  buf[-1] = temp;
 }
 printf("compare_count:%d\nmove_count:%d\n", compare_count, move_count);
}
 

int main() {

 int arr[10];
 int len = sizeof(arr)/4;
 for(int i=0; i  arr[i] = 10-i;
 }
// quick_sort(arr, len);
 insert_sort(arr, len);
 for(int i=0; i  printf("%d\t", arr[i]);
 }
 printf("\n");
 getchar();
 return 0;
}
阅读(1135) | 评论(0) | 转发(0) |
0

上一篇:快速排序

下一篇:文件同时读写

给主人留下些什么吧!~~