【大话数据结构C语言】67 希尔排序
【摘要】
众所周知，排序算法最重要的就是速度，但是前边介绍的几个算法时间复杂度都是n的平方
这个问题其实困扰了计算机界前辈们很久，一度有人认为“排序算法时间复杂度不可能突破n方”
但是，终有一天还是有科学家发现了，并且接连就出现好几种可以超越n方的排序算法，把内培训算法的时间复杂度提升到了nlogn
...
众所周知，排序算法最重要的就是速度，但是前边介绍的几个算法时间复杂度都是n的平方
这个问题其实困扰了计算机界前辈们很久，一度有人认为“排序算法时间复杂度不可能突破n方”
但是，终有一天还是有科学家发现了，并且接连就出现好几种可以超越n方的排序算法，把内培训算法的时间复杂度提升到了nlogn
希尔排序的时间复杂度是
，比前边几种的要好
，比前边几种的
要好
希尔排序
事实上还是直接插入排序，然后分成几个小组分别排序
-
#include <stdio.h>
-
-
void InsertSort(int k[], int n)
-
{
-
int i, j, temp;
-
int gap = n;
-
-
do
-
{
-
gap = gap/3 + 1;
-
-
for( i=gap; i < n; i++ )
-
{
-
if( k[i] < k[i-gap] )
-
{
-
temp = k[i];
-
-
for( j=i-gap; k[j] > temp; j-=gap )
-
{
-
k[j+gap] = k[j];
-
}
-
-
k[j+gap] = temp;
-
}
-
}
-
}while(gap > 1);
-
}
-
-
int main()
-
{
-
int i, a[10] = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8};
-
-
InsertSort(a, 10);
-
-
printf("排序后的结果是：");
-
for( i=0; i < 10; i++ )
-
{
-
printf("%d", a[i]);
-
}
-
printf("\n\n");
-
-
return 0;
-
}
文章来源: allen5g.blog.csdn.net，作者：CodeAllen的博客，版权归原作者所有，如需转载，请联系作者。
原文链接：allen5g.blog.csdn.net/article/details/117173262
【版权声明】本文为华为云社区用户转载文章，如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）