目录
1.更好的理解插入排序
2.实现插入排序
3.代码实现
4.完整代码
1.更好的理解插入排序
在开始前我们先了解一下直接插入排序的思想
假设我们在打扑克牌,我们在摸牌的时候就要进行排序
第一张牌是3
第二张牌是6,我们应该放到3的右边
第三次摸到5,我们应该放在3的右边,6的左边
再摸到4,应该放在3的右边,5的左边
2.实现插入排序
今天的插入排序,与我们平时打扑克是一样的
假设我们有这样一个数组来排序
我们采用扑克摸牌的思想
先摸5
我们摸4的时候发现,4比5要小,所以我们把5在数组中的位置向后挪动一格,将4插入
挪动6发现比5大,所以我们把6放到5的后面
挪动多次之后,我们就得到了排列好的数组
3.代码实现
那么接下来我们用代码实现
首先我们向将需要插入的那张牌拿起来
复制代码
1int tmp = arr[end + 1];
然后对原有的手牌进行判断
复制代码
1
2
3
4
5
6
7
8
9
10while (end >= 0)//手牌数一定是大于等于0的 { if (arr[end] > tmp)//如果第end张手牌比你要插入的牌大 { arr[end + 1] = arr[end];//我们将这张牌向后挪 --end;//遍历下一张牌 } else break;//此时end处的手牌要比你插入的那张牌小,结束掉循环 }
当循环走完的时候有两种情况
1.此时end处的手牌要比你插入的那张牌小
2.遍历完也没有找到比他小的牌,说明他是最小的,应该插在最前面
但是无论是那种情况,我们在循环结束时需要做的都是在end+1处插入这张牌
复制代码
1arr[end+1] = tmp;
当然这只是插入了一张牌,你的牌还有很多,我们需要一张一张的去摸然后再进行排序
我们这时引入摸牌,n代表你需要摸的总数,因为数组下标是从0开始的
复制代码
1
2
3for (int i = 0; i < n - 1; i++) { int end = i;
4.完整代码如下
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19void InSertSort(int* arr,int n) { for (int i = 0; i < n - 1; i++) { int end = i; int tmp = arr[end + 1]; while (end >= 0) { if (arr[end] > tmp) { arr[end + 1] = arr[end]; --end; } else break; } arr[end+1] = tmp; } }
最后
以上就是淡定秀发最近收集整理的关于排序——直接插入排序1.更好的理解插入排序2.实现插入排序3.代码实现 4.完整代码如下的全部内容,更多相关排序——直接插入排序1.更好内容请搜索靠谱客的其他文章。
本图文内容来源于网友提供,作为学习参考使用,或来自网络收集整理,版权属于原作者所有。
发表评论 取消回复