内部排序算法汇总<五>（希尔排序）

------------------------------------------

本文为本人原创，欢迎转载!

转载请注明出处: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;

}

阅读(377) | 评论(0) | 转发(0) |

0

上一篇：n年前传说中华为面试题(8分钟写出代码)

下一篇：内部排序算法汇总<四>（快速排序）