365_尚硅谷_Go核心编程_数据结构和算法-插入排序实现.avi原创

就考察这个人到底代码就是就是这个算法怎么样，这是最基本功啊，最基本功好，那现在呢，根据刚才老师的这个分析呢，我们就来一步一步，我们先搞第一个，再搞第二个，再到第三个，第四个，诶你一下就明白是怎么做的了啊同学们打开我们的这个，呃，V code，我们新建一个文件夹叫insert sort。Insert插作排序，然后呢，我们新建一个文件叫main.go没问题，问点go问题啊。好的，那现在呢，老规矩，Package，主函数import引入包包引入什么包不清楚，这个form包先引进去，放主函数。各位同学，那现在呢，呃，我把这个我们就用刚才这个数，我们就用这个数组，因为我们刚才分析的就这个数组，我还用这个数组比较好好讲哈，那还是老规矩，我们来写个二位。给它一个五个元素的数组，打开它。

好，这是五个元素的一个数组，那现在呢，我们在这里写一个insert sort。好，给它一个数组，然后呢，用指针指向对不对5INT。好，写完了，那现在呢，我们来看看怎么排序，怎么排序，先完成第一次吧。完成第一次，第一次就是给第二个元素找到一个合适合适的位置，对吧，第二次第一次就是给给第二个元素，大家可以理解啊，给第二个元素，给第二个元素找到找到合适的位置。并插入合适的位置。并插入。那么根据刚才老师的分析呢，我们首先先定义两个变量，一个是值。Values显然是or？一。因为你第二元素下标为一嘛，然后呢，它的这个索引就是刚才我们讲的索引，始终是你这个带插入的元素的前一个下标。

那也就是说现在应该是一，它应该是等于一减去一个一。那就是你这个数下边减去一个一啊，OK，那找到这个位置过后呢，我们就开始找位置了，For循环这个地方是逆过来走的，首先我要我要我要比较的时候，我要保证in inside的value要大于等于零才可以，因为你不大于等于零五我没办法比较了，如果它不大于它的整个还就说最后它小于零的说明它找不到位置，那就是第一个，那么并且还要满足一个什么条件呢？就是你的。就是你的insert这个index这个值。因为你是从大到小啊，Insert这个下边注意听。就是我们现在是从大到小，他如果说他比你大。啊，比如他他在他如果比我比比我小的话啊，如果我比你大，我就继续应该往往前面走嘛，所以说那我就说这个insert value。

就说什么意思呢，就说我这个要插入的比你还大，我就应该继续继续往往前走，大家能理解这意思吧，就说因为我是从大到小嘛，如果你反过来就是从小到大了啊，这个方是我如果插入的比你比你当前这个还大。说明我应该继续往前走，好，这个大家要理解啊，所以说我现在是要清楚是从大到小。好，也也就刚才说，那怎么办呢？就要做一个这样的动作，就是后移的动作，就是你要把这个值往后移，后面移动，后面移动的话呢，非常的简单，就是刚才那句话啊，就是刚才我不是每次移动吗？移动的时候其实就这句话，如果我画这个图，大家肯定比较不太好理解啊，Insert index加一。等于二位。Insert index，这个就是往后移。

后音注意啊，In inside index先不要去动它啊，就是说加一不是在后面，后面这个值等于前面这个值，不是相当于把它覆盖了吗。覆盖了，但是你不用担心，因为你你ser value已经被保存下来了，好紧接着往前走一下，这个数据后移啊。这个是数据后移，但是你移完了过后呢，你这个index要往前面再探一位，那这个时候还要做一个动作，就是你的insert。Insert insert这个这个index要减减。Index要减减注意啊，要减减减减的话，就是说再往前面看看啊，当然你如果减减到最后实在找不到，就相当于说它都不大于零了，那说明这个应该是负一了，负一就说就到了最后了啊，最后那个最前面都还找不到，那你就这样吃啊好，这个循环完了过后呢，我们就找到位置了，加入。

添加添加就是插入啊，就叫插入就行了，插入的时候呢，咱们也应该做一个判断。啊，插入的时候就嗯，就有可能他是他如果就是刚好就最后一个啊，比如说哎，我们先写进去吧，先写进去它应该怎么加进去呢？二。大家看这个应该怎么理解，是不是insert？Index加一等于这个值啊。那大家可能有点有点有点有点懵了是吧？为什么要加一呢？想吗？因为你你你你就以这个为例，比如说第一次这个零，这个零它就是比你直接大，你你设一百六不是在前面吗？加一不就刚刚在这相当于不动吗。对不对啊，所以说这个地方呢，要有个加一的动作啊，要加一，但是这地方这个动作呢，有点有时候是多余的，什么时候多余呢？假设你排的这个，你比较这个数刚好就是它就是最小的，那你没有必要比，所以说这么还要加一个条件什么呢？如果我们这个inser的。

Index加了一个一，它等于这个一。他他如果就说他加完这个一过后，它不等于一。不等于什么呢？不等于你当前这个这个一就说因ER加一不等于你要要最后这个值好说明这个时候要去添加，否则我就不加了，嗯，就相当于说它本身就在原来的位置，你加他干什么呢？好这个就写完了。这就写诶这代码写写的有点问题啊。我再我再把这个描述一下，再把思路再走一走啊。第一次先先找到第一个元素。Insert value，这个是插入的，这个是他的一个下标，就是呃下标。下标，我下标呢，总是呃这个元素的，呃前一个前一个值，然后呢，我进行一个从大到小的排序，只要你这个ins大于等于零，我就可以一直找，因为为什么要这个条件，因为我要防止。

你一直找不到，你就顶到最前面去了，我要防止这个问题，第二个什么时候才往前面找呢？就说我要插入的这个纸比你这个比你这个纸还大，说明我应该继续往前走啊，走的时候就后移，后移的动作就是移动一下，然后后移完了过呢，我这个inser的value再往前面移动一下，因为我要看前面有没有更合适的，好等到整个这个循环便利结束过后，至少说明了这个值位置，就找到了它的位置就应该是in射的应该值加一，就是这个这个插入这个值就应该是这个这个下表。因为我总是在前面跟你比较什么，但是呢，为了提高效率，你要判断一下，就是你你ins射的下标到底到底有没有必要做，因为有可能就是最后一个打个比方，打个比方就是零，打个比方看啊，比如这个情况零。他上来过这个零，他一比较，他发现我23就比你小，那我位置就找到了，找到的时候其实就没有必要再自己再加入一次了嘛，所以把这个条件排除一下啊，排除一下好，这个代码就写完了，我们看看代码有没有问题，我们跑一下。

Format。能，我们看看这个代码啊，同学们。好，这是第一次，第一次插入，插入后的结果。好，那么现在呢，我把它打印出来，二位为了好看，取一个星号，同学们看效果啊，同学们看效果好，我这里进行一个调用。我这里进行一个调用，那调用的时候呢，显然我传的应该是一个地址，OK，好，这个做完了之后呢，我们把它打出来给大家看一下啊，这个是主函数里面的数组。主函数的主函数组组呢，我就直接输出。PRPTL好直接输出啊，同学们。啊，那么在插入之前呢，我们也把它打印出来给家看一下，就两个呢，做一个比较，这是main函数啊，就main函数里面的到这也打出来，这个插入之前。

原始数组吧。好，原始数组是原始数组等于好看一下。好，同学们，现在呢，我们来玩一把，看看这个代码到底跟我们想的是不是一样的啊，同学们打起精神。CD点点CD到insert这里面去，然后呢，Go run main.go跑起来。跑起来。好，同学们可以看到，同学们看到原始数组是这样子的。好，第一次给这个零找位置，零呢，它本身就是这个位置，说零呢，它它就在原先位置没有动，但是你你你不变的，你是不知道的，所以你还是比较了一次，那比较完了之后，相当于这个是效率最高的，他比了一次刚好，诶就最后比一次就就就完事了，而且呢，连这个动作都没有做，因为你比较完那个in inside应该本身零嘛，零加一。

它就等于一，所以说我连这个动作都没做。好，第一次就完事了，那第二次怎么办呢？同学们看到啊，那下面代码我们就知道了，诶第二次诶同学们可以想象，那跟这个逻辑很像啊。那第二次完成，第二次给第三，相当于是给第三个元素找位置了，对不对，那这个应该变成二。那这变成二的下边变成二减一，这个不用变，这个不用变，这个同样加一，只要不等于二，我就要去进行替换到这个地方。把它改成这个不改啊，这个仍然是加一就写完了。啊，当然这地方不要再再定值了。有，现在是给第二第三个元素找位置。好，这个做完了已经，那做完了以后呢，我们来看看第二次插入以后结果是什么样子的，各位朋友请看代码。好，当我们运行完毕过后呢，我们发现第二次插入过后，给我们想象的应该是正确的，你看这里。给12找位置，12。

他一找，哎，发现零我比你大，零就往后面移一下，再比23，发现我没有你大了，好位置找到那查到这这个二十三十二零这个就是一个有序的，其他依次类推。那肯定还有第三次和第四次对不对？好，那这个就是第三次。第三次，第三次是给我们的第四个元素找位置，那第四个元素下边应该为三啊，往前面定一个位置，好，这个不动。这地方只要不等于三就可以。好，这是我们的第三次。好，同学们，现在呢，我们再跑一把。好，我们再跑一把，我们发现效果呢，跟我们想的是一样的，第三次，第三次是你看这个是56最大，啪啪啪啪，你到最前面去了，血压全部后移。啊，后移好，最后还有最后一次就30次，好，这是第四次了啊同学们第四次，那第四次的话呢，呃，我们是相当于给第五个元素找位置，注意最后这个元素是要参与。参与找位置的啊。啊，参与位置，那第五个元素下边为四，这个就变成四减一，这个呢变成不等于四就可以了，好同学们，现在呢，我们来把它跑起来，这是第，呃，没忘写错了啊，我把这个改一下，改成第四次插入。

第四次插入过后呢，我们看这个结果跟我们想的是一样的吗？我们发现完全正确再看。就相当于给34找位置，34诶刚好是比23要大一点，抄到前面去了，好代码就写完了，代就写完了，那一共有四次，我五个元素有四次，好同学们看。你突然发现，你发现这些代码的几乎是一样的，只有一个东西在变化，就是。这个是在变化，那既然如此，我们可以把它包起来，对不对？好，现在呢，我们来进行一个简单的处理。那既然如此，我们把这个就注销。哎，把它注销，注销完了过后呢，我们用一个for循环，把整个这个代码包起来，应该从哪包呢？肯定。

从这地方开始包说说开始玩了啊，Four。那你这个下标显然应该是从一开始走，你看这为什么这是一了，不是零了，哎，你看又变了，那你看冒泡的时候，它是从零开始走的，对吧？所以每个同学呢，大家要知道它的含义，那小于等于多，它小于多少次呢？显然是我们这个嫩。啊，OK，是你的数组这么的，因为你这个最后是要参与比较的，所以说不能再减一。因为你最后元素你不参与比较，那不行呢，所以这种为什么不减一道理大家要清楚啊，那我I加加，I加加完了过后呢，我把这一段代码整个包到我们这个for循环里边去，大家理解。好拍一下，那现在要改变的只是这个值了，把它改成I，这个也改成I，这边不需要改，这边呢，加完一个一过后，只要不等于I就可以了，代码写完了。那这个地方呢，把它改一下就是百分D，我们把它数出来看一下。

好了，各位朋友。那这个时候呢，这个百分V把它输出来，那这个D呢，就应该就是I啊，就刚好和该保持一致的代码写完了。负循环写完了啊，对不对呢，我们来看一下。好，各位朋友请看代码。请还在吗？我们发现这个代码呢，应该是没有什么问题啊，大家可以看到第一次。没有动，第二次把12定最后是正确的，那我们为了测试这个代码的正确性呢，我们可以把这个数组啊，呃，增加，再增加一个，看效果对不对，好，那我增加一个吧，增加两个吧，负一再来一个90，呃呃，整到中间去啊，比如说来一个比55小一点的，就55吧。OK，那这边改成七。改成七，朋友们好，这个改成七过后呢，我在接收的时候也要改成七，因为我们这个指针这个塞子也是指针变量的一部分，讲过了以前好改成七了，那么同学们跑一下看代码。

好，同学们看代码我们发现呢，也是没有问题的啊，也是没有问题，大家看一下效果对不对啊。OK，我们可以看到，呃，原始速度是这个样子的。嗯，反正看最后一次吧，五六呃五六五五三四二三十二零四正确的，所以代码是OK的OK的好，这个呢，就是老师给大家讲的这个插入排序，大家看这个好不好理解啊。呃，我我感觉有些我以前讲完过呢，有些同学说老师我觉得这个这个插错排序，呃，比那个选择好像好理解，有些同学插错排序不太好理解，但是每个人感受不一样啊，我感觉插入排序呢，效率它是要高一点，但是它理解起来相对有点难度，就说有些同学会在想一个问题，说老师你你他怎么这么去设计的。

这个就很难了。就他这个算法，他是怎么想出来的，这个很难。就说我可以给你们告诉大家，插数排序，这样去写，这样去这样去就能把它排排好，但是是是怎么样设计出这种算法的，这个我们很难想到设计一个严格好一点，这个这个排序啊，它也是需要动脑筋的，就说人家怎么想到用这种方式能够把它排好，是要动脑筋的，你比如说诶选择排序，人家怎么想到用这种方式冒泡，人家想的是这种方式插入，要用这种方式，它本身就是。先是人家设计的算法，然后再去实现的，明白我意思吧，所以说我们现在只能做到我们把插入排序按照他这个思路给他写出来啊，同学们要把这个掌握啊，好，我把代码给大家整理一下。那么刚才呢，我们我们来整理一下一个代码，好的啊，这是代码实现，先截段视频。