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

好的同学们，刚才呢，给大家介绍了这个我们叫做什么呀，这个叫做呃，就是选择排序，选择排序，那现在现在呢，我们来看另外一种排序方法叫插入排序，插入排序的这个速度啊，会比选择排序更快，待会儿呢，我们会做一个比较，就待会呢，我们会去构建一个8万甚至是800万的一个111个数组，我们看看哪一个排序方法更快，因为突然发现诶，它真的是有差别的啊，它的差别在哪个地方呢？大家到时可以做一个分析。那么现在我们来看看这个插入排序是什么意思，首先插入排序呢，它也属于啊各位同学，它也属于我们。它也属于这个内部排序，它是对预排序的元素以插入的方式来寻找该元素适当的位置，哎，它是这么一个意思，以达到排序的目的。那么我们来看它的一个思想，同学们看他思想啊，它的思想呢也很简单，但是我跟大家讲插入排序理解起来就是说他从代码的理解难度呢，比选择排序要稍微麻烦一点，但是它的思想很先进。

说它速度呢，一般来讲会比选择排序至少快一倍。那为什么呢？大家看他的思想啊，他这样子的。操作排序基本是这样子的，把N个带排序的元素看成是一个有序表和一个无序表，什么意思？就说我先把第一个元素就当作一个有序的，因为你只有一个元素，无论是从导从小到大，还是从大到小，它都是有序的一个元素嘛。那么开始的时候只有一个元素，无序列表中呢？有几个呢？有N减一，就是我把第一个看成一个有序的，N减一看成一个无序的，然后干什么呢？排序过程是每次从无序表中取出第一个元素。就从无序表中提出第一个元素，把它的排序码依次与有序表的元素码进行比较。

他怎么比较的呢？将它插入到有序表中的适当的位置，使之成为一个新的有序表。但这句话说完了，过后你也不知道他在说什么。因为你很难理解它的这个它的含义，那么这样子啊，我给大家画一个简单的示意图，我把我的思想给他说出来，然后我们走代码来同学们看一个思路，那比如说各位朋友，比如说现在呢，老师给他说一下这个插入排序，注意听啊，插入排序稍微的有点不好理解，插入排序的一个思路分析。嗯，那么还是老规矩，我把它画成两个部分，一个部分呢，是我的一个演示部分，另外一部分是我的思想，这是我的演示，另外一部分呢，是我的思想。这边是我的一个排序思想。哎，所以说你的思想还是很重要的。

那么我的思想是这样子的，假设现在呢，我有一个宿主，这个宿组呢，我就找一个已经准备好的宿主吧，就以这个这个小牛来它的这个成绩排序来来进行啊，现在呢，我们还是以从大到小。假设这个数组呢？最原始的时候是这样子的。原始的这个数组，它是如此这般的啊，大家看清楚了。嗯，他怎么玩呢，他第一步先。先认为先将。姜姜什么呢？将这个23第一个元素，第一个元素当作当作一个有序的，有序的这个数组。好，这是第一步，第二步从后面这个数从这边从它后面呢的第，它是这样子啊，他先给这个零，就是说从第23后面这个数给他找一个适当位置，从零给零。

给零注意还不涉及到后面十二五十六，34没有参与，没有参与给零找一个。找一个位置插入。那么他在找的时候呢，是从哪开始找呢？注意他的思想，这样子的先将注定这话这个地方很重要，思路特别重要，它是先把。诶。先把这个零保存到一个变量中。保存到。一个变量中什么变量呢？比如说我姑且把它叫做insert value。就是这个值呢，是准备我要插入的，能理解我意思吧，就是这个值准备要往哪插呢？往这个23这个有序数字里面插。OK，然后呢，还有一个呃，插入的时候呢，就相当于说这个指已经被保存了，然后呢，插入的时候这个它的它的这个指针是指向谁的呢？指向它前一个位置。

也就是说它的这个指针，这个插入的这个指针，这个指呢，是零的前一个位置。二零的前位置，也就是说这样子的给，然后呢，将插入的位置将。插入的这个位置用一个用一个变量保存。变量保存。那么这个变量是什么呢？我估计叫做insert index，这个这个位置它是什么呢？它是。这个零的前一个元素，也就是说相当于说零零在这嘛，那么相当于它是几呢？它是零呢，就是它是零的零的下标的前一个。前一个那个下标。好，然后从后，从后面开始比较，就从这个有序数组的后面开始比较，从后开始比较。

从后开始比较。从后面开始比较，从后开始比较，找到一个数比，就是说找到什么呢？找到这个给这个insert找到一个位置啊给。给这个insert value。找到。找到一个位置。找到位置，然后插入，但是在找的过程中呢，有一个特别重要的，找的过程中，它的一个数字有后后移的。啊，在在这个找的过程中，在。在找位置的过程中，找位置的过程中，过程中这个有序，有序的这个数组要后移，就是每个只要后移啊有序的有序的这个值，呃，有序数组。数组的元素，数组的元素会后移。会后移，那这个大家肯定有点不好理解，那么我就举例子了，来看第一个原始样子，第一次。

他原来是这样的啊。这个是个有序的。我这样看。他现在怎么找呢，这个是下标。这个是我们的值。这个这个零就是我们要插入的值，注意听。这个值就是我们的index啊，INSERT86，而这个指标这这个下标是谁呢？就是那个insert index。这个就是insert index，他总是在前面比较的，Insert的index，好，那就开始比较了，他先让这个零。跟23:9。二三比较，如果他发现0比23小，那么说明这个位置就找到了，那找到过后相当于这样子的啊第一次。第一次第一次找到插入位置，找到插入位置，找到插入位置过后呢，相当于说因为零它的确比23小，所以说它一下就找到位置了，那找到位置过后呢，这个就变成这个样子了。

这个有序列表就变成23。23，然后零后面呢，还有三个数是无序的。56和34，第一次就找到了第二次，接着来第二次呢，就给这个，那么现在相对这个in value6这个值呢，就变到了12，它的这个index指标变到哪去呢？这个index变成找到这个位置了啊这个注意啊，这个inser的index它是下标，也就这个下标应该是一。啊，然后呢，第二次开始找位置。第二次找位置，找到插入位置，那这个第二次找的时候呢，注意看啊12。它是比这个零大的，它如果比零大的话呢，这个零就往后移。后一式造成一个什么情况呢？变成这个样子了啊。注意这个12已经被保存起来了，所以说它第一次比较发现12它是比这个零零大的，说明这个位置没有找到，因为我要是我是从大到小排。

那就变成这样子，变成什么呢？二十三零零。56。和34，当然有同学会说了，老师，那你这个零往后面移动了一下，那这个这个这个零，这个五十十二不就没有了吗。不要忘了，12已经被保存到一个变量里面了，它已经被保存起来了，所以说这个时候呢，继续让这个index往前面移动一下。前面移动，当然这个时候呢，这个时候这个值，它这个iner值还还是这个什么呀，还还是这个12啊，它没有动过，然后呢，让23跟12进行比较，当然23呢，是大于12的位置找到了。那位置一旦找到好这个地方，只需要在这个地方在inser index加一的位置把它加进去就可以了，也就是说第二次怎么做呢，就在23不动了，因为23已经比这个12大了，所以说你不能再再往后面移动了，那这个时候呢，就把这个位置这个12。

用啊这个零用12替换。那12因为已经保存到in insert value嘛，所以说这个12就被覆盖了。覆盖覆盖过后呢，这个零还还是这个位置，那么56。34所以说第二次做完了以后，这个结果呢，应该是这个有序的，其他以此类推，比如说第三次。我再走，走一个第三次啊，第三次我把这个都写完。第三次也找到这个插入位置，插入位置。位置并插入吧，并插入啊，那么这个时候呢，它的原始数据就这样子，那这个时候同学们想value呢，就变成了。56，然后呢，你这个insert应该，呃，下边在这儿，下边在这的话，56比，那那么我们来画一下这个图啊，画一下56比0大，所以说56比0大，所以零会往后面移动一下，那么就变成23。

十二零零没问题，后面这个34不参与比较，但是放在这的。好，那么这个时候你的这个下标比较下标往前面移动一下，变道指向哪里呢？呃。啊对对，是这样子的啊，他原先是在这儿，那就指到这儿了。直直到这个位置了，直到这个位置，你的这个inser value6还是56，那么56比12大吗？还是比它大，说明没有找到位置，所以说继续往后面移动。那就二十三十二。往后面移动一位12。零。啊，也就相当于说我这个时候往后面移一下，那移下过后呢，我紧接着再让这个一一十二的，呃，Index往下面移动下，再比较23比56大吗？诶我23:56不大，不大的话呢，好，那这个时候继续往后面移动一下，这个难就难在的地方，它在不停的移动，那么23往后移动一下，就相当于拷贝了一下十二零。

好的，这个时候注意听，这个时候呢，好。它再往前面移动，好，发现已经不能再移动了。它已经不能移动了，它不能移动就说明的的确确这个in inside video是最大的，它移动不了了，移动不了的话呢，它会它当它当然啊，它还是仍然会移动一下，才会退出来一个循环，也就这个时候index还是指向负一了，但是这个时候它不参与比较了，这个时候怎么办呢？他让这个，它让这个in inside video直接在这个in inside index加一的位置把它覆盖了，这点很重要，就是加一的位置加进去，也就说这边变成了多少呢？变成了56。二十三十二零三十四。也就是说它其实在不停的找位置，然后呢，找到一个适当位置加进去，就这个道理，那有同学说老师这个有什么好处吗？这个的好处其实大家可以看到，它非常优越的地方是。

因为它总是从一个有序数组在找位置，那么它的比较的次数，比较的次数其实在减少的。因为他比较吃数，因为你想一想这个道理吗？你想这个道理，因为我在我在从后面找，我是容易找到这个有序，有序这个数组，找这个位置加进去，我就不需要遍历整个数组。那你以前那个冒泡也好，包括你以前的那个，包括你以前的那个，就是那个选择排序也好，它总是从一个无序，总是从一个无序里面找的，所以说它比较的是总是便利玩。所以说这个插入排序呢，它的速度绝对是要比这个选择和冒泡快至少一倍。至少一倍，待会我们可以做一个实验，比如说我8万的数据，我用插入排序可能四秒，那么你的选择应该是至少八秒，冒泡就更长了，冒泡一般在九秒十秒左右，好，第四次也是一样的道理了，第四次我们也来走一下啊，我把它走完第四次。

第四次的话呢，呃，相当于在这个基础上，那么你的插入的值就相当于是找这个找这个值了，当然你的这个下标就到这来了，还是他每次都从最后找啊同学们看，每次都从最后找好零三十四好不对，于是乎这个地方就这样移动了，就是56不动，然后23 23不动，12。不动零，不动零往后面移动移位。相对于往后面移动，对移动一位这个音这个指标，这个下标就指向了它12:34，仍然是12:34，然是小的，所以说还没找到位置，紧接着把12往后面移动，就是56。二十三十二十二往后面移的一位零，注意移的时候这个这个地方没有背还是12啊或老师有两个12怎么办？没没关系，没关系，好12，呃，这个移动完了过后呢，这个继续往前面移动，越变23 23跟这个34比较，仍然没有找到位置，因为23呢比34小，34小的话，23继续往后面移动。

那这个变成了56 23 23就把原先12给覆盖掉了，12。零好，那么这个它移动完了过后呢，它这个其实会往往前面移动一下啊，移动一下好56我们，诶走走到这了啊，他发现56比34大，好说明找到位置了，紧接着就在index这个指标的后面这个地方插入这个位置，这点很重要，它是在inser的index后面这个位置插入，那这样子一插进去变成什么呢？变56，你这原先这个是34嘛，34就插入到这个位置，23人还在十二零好完毕。他这样子的，那么至于大家可以看到啊苏老师。那苏老师，那现在有一个问题，就是说他在每一次比较的这个次数到底是多少次，能确定吗？不，不确定。

他可能很快就退出来了，很也有可能把这个便利完才退出，打个比方，你你你这帮运气很好，这个地方是刚好，你这个不是最后不是34是一个负一。他就比较一次就完事儿了。如果你很不幸，这个地方它就是最大的。他就编你完。所以说他每次在这个在这个进行这个比较，就是比较次数是多少次不清楚。它是一个，它是应该除以二这样一个，就是按概率来说应该是除以二的，因此你你就相当于说原先我们冒泡也好，选择也好，我们都是要进行整个数组的便利，但是它变成了除以二，所以它的速度就会变成原先的两倍，因为从概率来说来讲就这样子的，所以它的速度是相对来说是前面三种里面最快的一种。好，那么我把这个事情说完了过后呢，下面同学们我们就来代码实现一下，还是老规矩啊，我们这样做，当你不知道怎么做的时候呢，你先把第一个事情再做第二次，再做第三次，再做第四次，你会发现规律。

就出来了。好，这样你就记得很牢，好，同学们操作排序的思路分析，老师就先讲到这里。