八大排序·希尔排序
【摘要】
大家好,我是安然无虞。
文章目录
希尔排序1.基本思想预排序
2.算法实现3.时间复杂度
遇见安然遇见你,不负代码不负卿。
插入排序分为两...
|
希尔排序
1.基本思想
希尔排序是在直接插入排序基础上的优化,属于非常牛掰的一个排序。
核心思想:
- 先进行预排序,让数组接近有序;
- 直接插入排序
预排序
预排序步骤:
分组排,假设gap==3,间隔为gap的为一组,然后分别使用插入排序的思想对这gap组数据进行排序
多组间隔为gap的预排序,gap由大变小,gap越大,大的数可以越快的到后面,小的数可以越快得到前面,gap越大,预排完越不接近有序,gap越小,预排完越接近有序,gap为1时就是直接插入排序
动图演示:
预排序代码:for (int i = 0; i < gap; i++)//有gap组需要排 { for (int j = i; j < n - gap; j += gap)//内层循环,先排红,再排绿,最后排蓝 //注意内层循环的写法 { //跟直接插入排序很像,不同的是需要使用gap int end = j; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
这是最初的写法,其实这个代码是可以优化的:
//预排序优化 for (int i = 0; i < n - gap; i++) //把间隔为gap的多组数据同时排 //当到n-gap-1的位置就终止了 { int end = i; int tmp = a[end + gap]; while (end >= 0) { if (a[end] > tmp) { a[end + gap] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
2.算法实现
//希尔排序
void ShellSort(int* a, int n)
{
//一开始初始化gap为n
int gap = n;
while (gap > 1)//gap大于1都是预排序,gap==1时为直接插入排序
{
//为保证gap最终结果为1,可以gap/=2,也可以是gap=gap/3+1;
gap /= 2;
//预排序优化
for (int i = 0; i < n - gap; i++)
//把间隔为gap的多组数据同时排
//当到n-gap-1的位置就终止了
{
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (a[end] > tmp)
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
完整代码:
3.时间复杂度
希尔排序的时间复杂度是:O(N*logN)
遇见安然遇见你,不负代码不负卿。
文章来源: bit-runout.blog.csdn.net,作者:安然无虞,版权归原作者所有,如需转载,请联系作者。
原文链接:bit-runout.blog.csdn.net/article/details/124702416
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)