八大排序·直接插入排序
【摘要】
文章目录
直接插入排序1.基本思想2.算法实现3.时间复杂度
遇见安然遇见你,不负代码不负卿。
大家好,我是安然无虞。
插入排序分为两种:直接...
|
插入排序分为两种:直接插入排序&希尔排序
直接插入排序
1.基本思想
直接插入排序是一种简单的插入排序算法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。
说得通俗一点就是:
|
生活中我们玩扑克牌时,就用了插入排序的思想。
在这里,我们以排升序为例。
|
动图演示:
2.算法实现
|
//[0, end]已经有序,将end+1位置的值插入到[0,end]中,使得[0,end+1]依旧保持有序
//有一个有序区间,插入一个数据,依旧保持有序
void InsertSort(int* a, int n)
{
for (int i = 0; i < n - 1; i++)
//控制摸牌的过程,一开始从仅一张开始
//注意循环结束条件,只需要到n-2的位置,若将其改成i<n,则会出现越界的情况
{
int end = i;
int tmp = a[end + 1];
while (end >= 0)//保证牌是有序的
{
if (a[end] > tmp)
{
a[end + 1] = a[end];//往后挪,注意画图感受哦
end--;
}
else
//有两种可能:(现想常规的,再考虑特殊情况)
//一是找到了比它小的数,放到其后;
//二是没有比它小的数,直到end为-1才结束
{
break;
}
}
a[end + 1] = 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
完整代码:
3.时间复杂度
直接插入排序时间复杂度是O(N^2),注意哦,不是因为双重循环,需要实际计算来得出时间复杂度。
最坏情况:逆序有序,1+2+3+……+n - 1;O(N^2)
最好情况:顺序有序,1+1+1+……+1。O(N)
遇见安然遇见你,不负代码不负卿。
文章来源: bit-runout.blog.csdn.net,作者:安然无虞,版权归原作者所有,如需转载,请联系作者。
原文链接:bit-runout.blog.csdn.net/article/details/124698830
【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱:
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论(0)