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

2012年(6)

2011年(62)

分类: C/C++

2011-09-04 10:17:35

------------------------------------------
本文为本人原创,欢迎转载!
转载请注明出处:snowboy.blog.chinaunix.net
雪夜流星
------------------------------------------
希尔排序又称缩小增量排序,它也是一种属插入排序类的方法,但时间效率上较直接插入排序有一定的改进。实现代码如下:

#include
#include


/*****************************************************************

 *功能描述:希尔排序算法

 *传入参数:num:需要排序的数组首地址, n:数组的长度

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

 *返回值: 无

 ****************************************************************/


void insert_sort(int *num, int len)
{
int tmp, i, j, d;
/*如果指针为空,或者长度小于2直接返回*/
if ((num == NULL) || len < 2)
{
return;
}
d = len;
/*当增量d<=1时,排序完毕,退出循环*/
while (d>1)
{
d = d/3+1;//增量计算公式
/*依次对数组中间隔为d的元素组成的有序表进行一趟冒泡排序*/
for (i=0; i
{
if (num[i+d] < num[i])
{
tmp = num[i];
num[i] = num[i+d];
num[i+d] = tmp;
}
}
}

return;
}

int main(void)
{
int i;
int num[5] = {5, 4, 3, 2, 1};
printf("before:\n");
for(i=0; i<5; i++)
{
printf("num[%d]:%d\n", i, num[i]);
}
insert_sort(num, 5);

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

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