尤瑟纳而女士借阿德里安之口云，当一个人写作或计算时，就超越了性别，甚至超越了人类——当你写作和计算时，就是在思考。
聊聊<<大话>>中直接插入排序的那些坑
我就不说为什么要学习直接插入排序,那样岂不是太老套了.今天我就说说看<<大话数据结构>>中的直接插入排序算法的坑,一开始看大话数据结构的时候,就曾经有很多人跟我说,这本书有很多的坑,别跳进去,今天我就义无反顾的跳了进去.而且是不带回头的😭.整整四页纸的直接插入排序算法,我搞了一天(可能是我太笨了)!一开始我在Xcode(Mac上OC语言的编译器)上按照OC的方式把大话数据结构的代码撸了一遍.还没编译运行呢,我就看出一个问题来,数组越界....我的内心是崩溃的.但是我稍稍的修改了一下.一运行,还是不对,没办法,我只好从网上找各种关于直接插入排序算法的技巧.然后,我就发现问题的原因是哨兵的问题,好了,我原谅他了..因为函数不同,所以,我只好重新用在本子上演算过程.里里外外花了一下午左右吧.下面我就把不同的位置标记出来,为后来之人指一条明路.不说了美图我会这么说?直接上图!
这个错误是导致数组越界.
哨兵问题
直接插入排序算法概念及基本思想
直接插入排序(Insertion Sort)的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录插入完成为止。
直接插入排序算法的实现
首先我们看一下,用文字是如何表达实现过程.
设数组为dataArray[0…n-1]。
1. 初始时，dataArray[0]自成1个有序区，无序区为dataArray[1..n-1]。令i=1
2. 将dataArray[i]并入当前的有序区dataArray[0…i-1]中形成a[0…i]的有序区间。
3. i++并重复第二步直到i==n-1。排序完成。
文字说的还是有点生硬,看一下用OC语言代码是如何实现直接插入排序算法的.代码的注释已经很详细,需要加断点自己查看控制台的打印信息.这里我写在了ViewController的ViewDidLoad中.
- (void)viewDidLoad {
[super viewDidLoad];
//数据源数组
NSMutableArray *dataArray = [NSMutableArray arrayWithArray:@[@0,@5,@3,@4,@6,@2]];
int i,j;
NSNumber *temp = [[NSNumber alloc]init];//这里就是要修改过的哨兵(OC版本的,其他语言自行探索😁)
for (i = 1; i< dataArray.count; i++) {
NSLog(@"%@",dataArray);//打印每一次的变化,不管是否有新的元素插入有序表中(需要断点打印查看)
//判断当前的下标i的数组元素是否大于下标i-1的数组元素,如果大于,那么不做操作..反之~~~
if (dataArray[i]<dataArray[i-1]) {
temp = dataArray[i];
//找到合适位置,插入有序表中
for (j = i-1 ; dataArray[j] > temp; j--) {
dataArray[j+1] = dataArray[j];
NSLog(@"%@",dataArray);//打印每一次元素移动之后,数组的变化情况(需要断点查看)
}
dataArray[j+1] = temp;
NSLog(@"%@",dataArray);//打印每一次元素插入有序表中之后数组的变化(需要断点打印)
}
}
NSLog(@"%@",dataArray);//排序完成打印数组(需要断点查看)
}
直接插入排序算法代码过程部分讲解
第一次遍历( i = 1 , j= 0,temp = nil )
- 第一步,判断dataArray[1]和dataArray[0],因为5> 0,所以不走if里面的所以条件,也就是可以这么说,现在5已经插入了有序表中,有序表为{0,5}(假装有图片,不对,是假装有有序表...);现在的数组没有发生改变,为{0,5,3,4,6,2};跳出第一遍循环.
第二次遍历( i = 2 , j= 0,temp = nil )
第一步,判断dataArray[2]和dataArray[1],因为3< 5,所以走if里面的所有代码.
-
第二步,if里面的代码,首先把dataArray[2]赋值给temp,所以temp = 3;接下来就是for循环插到有序表表{0,5}中,j = 1,for循环的条件dataArray[j] > temp,即为5> 3,条件成立. dataArray[3] = dataArray[2] = 5 ; 接着j-- , j = 0, 判断for循环的条件dataArray[j] > temp,即为0> 3,条件不成立.跳出循环.dataArray[j+1] = dataArray[1] = 3,这次的插入操作就完成了.插入操作完成的数组为{0,3,5,4,6,2};控制打印如下.
数组元素3完成插入操作之后的打印信息
往后的数组元素4以及数组元素2都需要做插入移动操作,数组元素6不需要做操作,往后的步骤和上面的步骤类似.我就不做一一详细的讲解了.
各位看官,在查看上面的代码之前 , 你需要做的一件事情,那就是准备好一张纸📋和一支笔✏️,来记录每一次的变化.这样才能更好的了解直接插入排序算法的全过程.就如同这样....(书写请无视,谢谢😂..)
最后附上OC版的Demo,各位看官自行断点查看,如果有任何疑问请在评论去回复,谢谢.
