363_尚硅谷_Go核心编程_数据结构和算法-选择排序.avi原创

那么排序呢，我们说实话，排序是一个比较说实话还是比较重要的一个知识点，对吧，因为它可以锻炼我们这个一些一些编程的思想在里边。那么排序呢，最常见的呢，有这么四种啊，第一种呢叫冒泡排序法，第二种呢叫选择排序法，第三种叫插入排序法，第四种呢叫快速，这四种呢是是比较经典的，就是大家作为这个编程人员呢，我们必须掌握的经典的四个排序算法，那关于冒泡排序法呢，我在前边儿已然讲过了，这里呢就不再多说。啊，冒泡排序啊，大家想一想哈，以前我们在讲的时候，你们现在还能不能把它默写出来。第二个呢，选择排序法和插入排序法，快速排序法，今天我们来讲一讲，而且呢，我是要求同学们选择插入快速必须把它默写出来啊，快速呢可以不做默写，因为快速确实稍微难一点，但是选择和插入也需要同学们把它能够就说不参考任何的这个代码也能把它写出来，OK，那么我们来看看这个排序的这这。

后面的这这三种方式。好，跟上老师思路啊，排序的介绍，那排序呢，我们来走一个排序。好，写到这了。排序，OK。给他一个标题二。给他一个标题二。好排序的介绍，我们来看一下它的基本介绍是什么，OK？那么排序呢，我们说到呃，是一种将一组数据按照指定的顺序排列的一个过程，常常见的呢有这么四种。好，我把它排一下，第一个叫冒泡排序法，这个是同学们需要掌握的，第二个呢，选择排序，第三个叫插入排序，第一个是叫快速排序，那么从它的速度上来看呢，这个选择排序要。

快与冒泡，插入排序呢又比选择要快一些，快速排序呢是最快的，就是说这四个方法里面它最快的。好，我们来看一下，呃，下面的具体的排序冒泡我就不再讲了，因为前面呢，我们已经讲过这块呢，大家过一下就行了，好，我把这个板述一下就行了，因为这个呢在前面说过，所以说我这板述一下就行。冒泡排序。来一个标题三，把它放到这儿。爆八排序，大家想一想是怎么排的啊同学们。OK，我在这儿呢，给它截一个板书的，紧接着我们往下继续看，冒泡完了过后呢，我们又讲了一个选择排序，那么选择排序呢，我们来看一下它什么意思，选择式排序它也是属于内部排序法，什么叫内部排序呢？就是说它把这些数据呢都调入到内存里面，然后呢进行这个排序。

那么它从排序的数据呃数据中按指定的规则选出某一个元素，经过和其他元素的重整，再一原则交换位置后，达到排序的目的。但这句话呢，说完了过后，大家也可能不太清楚他说的什么意思，我们就来看他的一个思想吧，这样子大家可能看起来比较简单一点。那选择排序它是一个什么样的思想呢？它是这样子的啊，选择排序是这样子的，它基本是是第一次从R0到RN减一选取一个最小的数字，就说我先从整个这个数组里边选一个最小的与R0进行交换。什么意思？就是在整个数组里面把最小的找出来，跟第一个元素进行交换，第二次呢，从这个R1到RN减一中选取最小值，再跟R1交换。

其他依此类推，经过多少次呢？N减一次，我们就得到一个顺序了，这个顺序呢，可能是从大到小，也可能是。从小到大。OK。那我们来看它的一个一个图解，大家一看就清楚了，比如说同学们看这里啊。这地方有个数组，这个数组，这个数组呢是第一个是83217465，假设我们要从小到大，就是从小到大排。它的思想是这样子的，先从这第一次它的初始状态是这样子的啊，同学们看初始状态是这样子，然后呢，他找到这个数里面的最小这个数谁呢一。让这个一和第一个元素进行交换。那相当于说这个一和八交换就变成了一和八交换，变成这个德行了，变成这个完了后呢，再找第二个元素。

就是说再从这后面的这个元素，呃，元素里面找到一个最小的，跟谁交换呢？跟第二个元素交换，那大家想一想，328745465里面最小的显然是二，那就说二和三交换形成的一个这样的数据，紧接着呢，再从这个数组里面交，这里面再找一个最小的，显然是三，三呢，因为它本身已最小的，所以说相当于自己跟自己交换不交换好，紧接着呢，又在从这个数组里面。找出一个最小的，这里面最小的是四，四和谁交换？四和八交换，紧接着再从这里面找出最小的是五，五和谁交换？七交换变成这个东西了，紧接着再从这里面交。依此类推，最后呢，形成一个顺序，就123456789啊，没有酒。当然这个是从小到大，如果从大到小呢，你判断的时候只需要说把最小的找到最大的就可以了，好，我们来把这个思路也讲清楚了，下面呢，同学们，我们走一段代码，来一起写一写代码啊。

这个也是要求同学们能够把它写出来的，那么我们就根据刚才老师这个思路，一步一步完成。好，现在有一个选择排序的应用实例，实例这样子的啊，有预情有。啊，颜值分别是十三十四十九，100和80，这这个不是公斤啊，80分。80分。好嗯，假设我121个两个三个四个五个，请使用选择排序，从高到低就从高到低来排，那么现在我们来想想这个怎么做来走代码了，直接走代码啊同学们，我们现在呢，走一个新建文件叫select。选择排序，这个是要求同学们必须掌握的main.go。好，现在呢，我们打一个包包打一个包，Package主包。

然后import走form。好，现在呢，我们写一个主函数。好，首先我们先定义一个数组，我们定义一个数组。定义的数组。好，这个数组呢，哎，我们就这样写吧。Right。等于我们就定五个元素的一个数组。啊，数字的数据呢，我们就就用这个吧，好吧，我也不去想了，就是这么五个数，这么五个数，同学们注意听。好，十。34。19。100和80好，稍微的反述一下。好可以了，那现在呢，我专门写一个函数来解决它啊，编写一个函数，编写函数select so。

啊，完成排序，那么完成排序的时候呢，你还是根据老师以前写冒泡排序的事项来完成，你第一次可能想不到怎么做。所以说呢，你就根据老师刚才第一个思路，我们先来完成这样一个思路，就是说完成第一个排序，就说你能不能先把一个最小的或者叫最大的排在第一个，你能先把这个东西给我讲搞定好，我现在是不是这样子啊，我们要是从大到小排。从大到小盘，那么你看我我写这个代码的思路怎么写的，大家学习这个select short，首先你把数组传给我，你把数组传给，那么你给我一个A，好数组呢，是五个元素的数组，注意听这时啊，同学们看到。我们都知道构元里面呢，这个数组它是值传递，默认是传递，那你如果是希望在一个函数里面改变外面的函数，你得需要用指针。

好，这个我们以前讲过的啊，讲过的OK，那么在指针里面呢，我们来看看我在里面改变能不能影响到外边啊，同学们看一下。我先把这个AR打开，然后呢，我调它一下。我调他一下。好，把这个地址传进去，我们来测一下。然后呢，我在这写一个东西，因为你是指针了，理论上说标准的访问方式应该这样的啊，标准的访问方式应该是仙。先把它取出来。然后再取出第几个元素，比如说第一个元素，我们给它改成一个600。好。好，同学们看到我现在我现在已经把它改成600了啊，标准的访问式应该是这样写的，因为你是指针嘛，所以说星就相当于是取出这个指针所指向的数据空间里面的第一个元素，这样子呢，应该可以改变第一个元素，把十改成了200，十改成600，我们先跑一跑。

CD点点CD到刚才我们写的select short，好，Go run，命点go跑起来，我们看一下效果。我们可以看到。哎，对，改改变了啊，因为我是改变的第一个，那就相当于把34改成600，把34改成600了，对的，但是呢，这种写法因为比较繁琐，所以说呢，我们构语言的设计者呢，他也支持一种简化的写法，也是可以的，这样写也可以说老师我这样写行不行，太麻烦了，这样子我能不能这样写呢，我就直接。这样改行不行也可以也可以，他也支持，就说你这种写法，朱婷你这种写法也可以达到改变外面的就是这种写法等价于这种写法，就你可以这样这样理解啊，它等价于。等价于什么写法呢？它也等价于这种写法，因为go语言的编译器在底层里面呢，做了一个优化，它会自动的把这个信号给你加进去，好，那我们看看这个有没有变化，走我们发现呢，仍然变化了。

对，我发现仍然变化了，对的啊，所以先把第一个给大家说清楚，好，这个说清楚过后呢，我们接着往下继续讲我们的选择方法。好，我们来分步分阶段去分阶段走啊，第一步，第一步先完成，将第一个最大值。最大值，最大的这个值和和谁交换，和他交换这个对于我们来说应该没有难度，周老师你为什么要分分步走呢？因为希望你们理解的，将来说哪一天突然你有将近半年没有选选择选择排序了，突然有一个面试官说来写一个，你也想用这种方法。因为我们人的思维呢，最好就是一般有个过渡的，所以说我先给你们完成一个最简单，一看规律马上就套出来了，好，所以说仍然使用我们的先易后难法，先易后难。后来，然后呢，层层分解啊，先于后难。

就是你一定要学会这种这种编程的方法，先易后难，先呃先死后活，以前我讲过啊好，那现在呢，我们就来开始完成第一件事情，那你要把第一个最大值，第一个最大值和。这个地方交换难不难呢？其实一点都不难，你可以这样做，你先假设你的第一个元素，就是最大值。对，我们以前就这么干的，所以说我的市面上是的啊，先假设。好，先假设。假设我们的这个就是最大值二零就最大值，这个没问题。最大值，我假设最大值，所以说max。等于二零，这个没有毛病，然后呢，我把它的这个最大值的下标也记录下来，因为待会呢要发生交换嘛，所以说我把最大值的下标也交换记录下来，就是几呢，就是零。没问题，但是你这假设的这个最大值是不是最大值呢？不一定，因此呢，你要开始变利，第二步便利。

便利，后面的后面的一到哪里呢？到二。嫩。减一，注意听是N减一这么的元素。因为你的长度呢，那个下标它是要减一的，说便利后面数进行比较。比较。好，那这个再说对吗？特别的简单，那就I等于几呢？一，但是这个一是怎么来的？贵位同学，这个一其实准确项是零加一，为什么我这么去写，就代表我这个便利的时候是第一个，就说你假设这个字呢，不需要再参与比较了，你自己跟自己比较不是很有意思，很无聊吗？就是我已经假设它是最大的，我就认为它最大，但是它跟后面的进行比较，所以说这个呢，我是零加一，这个零其实就是代表的这个值，就待会就能把这个规律找出来，好，然后I小于多少呢？

它小于这个嫩二位就可以了。啊，因为我是小于没有取等于，所以说相当于这个它本身这个是取不到的，然后呢，I加加。好，现在开始比较。如果。你认为的最大值，它还小于了你的这个值，就说如果这个条件成立。就说明什么呢？说明你认为的是最大值，它不是最大值，是这意思吧，就你认为最大，它不是最大，那你怎么办呢？你就交换啊，你现在不要交换啊，注意选择排序法，它最经典的地方是先不交换，先找到最大，然后最后再交换一次。这是它的一个效率提升的关键，如果你这马上交换就没有意义了，所以这地方是就是说假设最大值不是最大值，这个就开始这样比较，那就交换。那你就max等于多少呢？O，注意听I，同时下标也进行一个改进，你变成什么？变成I了？

对是变成L，说现在呢，就说比较看看找到最大值啊，这个就是找找真正的最大值。找到真正的真正的最大值。好经过。经过你的这个for循环，同学们经过你的这一层for循环，那么你就应该找到了这个一，下边为一，到这个下边N，呃，二减一，这个呢，最最大值，是不是最大值，好，如果是这样子的话呢，我们就交换一次就交换。就说你这做完了过后，你相当于说这个最大真正最大值就找到了吗？那就交换。但是交换有没有一个判断呢？什么情况下交换？什么情况下交换就说。这个max。这个max不等于零的时候才交换。如果马克思你你结果你假定的最大值就是最大值，那就不要交换了吗？说这边应该有一个判断条件，你看啊，如果。

如果我们的这个最后得到这个max下标，它不等于我假设这个零。那如果它等于零，说明我们假设的就对了。它如果不等于我们再交换，对不对？这样可以节省一次交换，因为交换本质它是很费时间的，交换是尽量少发生，同学们比较可以比较，相对来说比交换的效率要高。所以说你看它有效的利用了这个这个特点，那么怎么交换呢？非常简单，大家想怎么交换二位。零。阿。Max index。等于2MAX index，然后二零，大家看这个人能否理解。好，我相信同学们应该能理解这句话哈，我们以前是写过这种写法的，这种写法就是相当于把这个值。给到了零，把这个零给到了它，这个写法我们以前写的是用了中间变量，这个呢我就不用了，其实它底层，它的底层也会用这个中间变量来处理，或者是用地址来处理了，肯定我们就用它的方式就可以了，这效率呢也相对高一点，就用它啊，以后发生交换，咱们就用这种写法，这个呢是构语言的一种比较有意思的一种语法现象，大家记住就可以了，好，整个整完了过后，我们看到底有没有发生变化，来做一下第一次搞定了没有。

第一次搞定没有我们不知道啊，我输一下。我们第一次啊，第一次的大循环吧，第一次循环。第一次循环。我们第一次啊，第一次确定了，所以第一次我们就写第一次啊第一次。好，第一次，第一次这个结果变成什么了呢？来输出看一下。来朋友们，我们看看这个效果到底如何啊，到底如何我们把这个也打出来呢，走这个呢，是主函数里面的啊。

主函数。主函输入它应该，呃，如果没有出任何问题的话啊。如果没出问题的话，那就应该把这个100，这个100和十发生交换了，如果没有我们代码正确的话，是100变到了这个位置，把十找到这儿了，那么我们执行一下代码。跑起来跑起来，我们可以看到效果跟我们想的应该是。看一下，等一下。好的。好的，同学们可以看到他在第一次做完了以后，第一次做完以后，它的确100和适发生交换了，这个是对的啊，这个是对的，好，这个是没有问题的，好，这个发生交换原来是这样子的，变成这个了，我们把原原先这个也打印出来，最早的这个打印出来，PT。这是他最早的排序前的，再看一下。好，这地方是写个信号吧，这样看起来应该更更清晰一点。啊，大家看效果好，最早是这样子。

好，第一次做完了以后，十和100发生交换了，最后做函数里面也发生交换，说明里面的改变会影响到外面的，这个做完了，第一次做完了啊说老师那下面怎么办呢？下面给我复制粘贴。来找第二个，哎，同学们看，当我第二次的时候，你们看规律就来了，这个就换成一了，我假设下边唯一的又是最大值，然后这个时候找的应该是二到最平，那就是相当于说是一加一。改变它这个地方不需要变化，这样不需要变化，然后这个地方变成几呢？变成一。写完了，这是第二次。代码写完啊，这个要要变化啊，这边也改成一，这边也改成一。这个我相信同学们能反应过来啊。什么意思呢？就是我第一次做完了过后，我再找第二个元素的最大值。这个逻辑又重新走一遍吗？大家看是不是这个意思，肯定是这个意思，走，我发现第二次呢，它这个34和10U交换，诶大家看啊不是啊，第二次是这样子的，在这个基础上。

你原先是这样子的，那么34和后面的数进行比较，发现80是最大的，所以说80和34交换，又搞定又搞定好，紧接着这个逻辑继续往下玩，复制一次。好，大家可以看到规律已经跃然纸上了，紧接着找第二个，找第二个好，下面呢，就是从第三个往下找好，那这地方变成了二加一，二加一完了过后呢，这不需要变化，这改成二。这份改成二。诶，这边改成二走，把这个改成二，这边呢也改成二，看看规律，同学们这是第三次，第三次呢，相当于说把第三一个最大值又确定下来看效果。看效果，那也就是说第三次他是在第二次的基础上，把这个十九十九十里面最大的找到，就是34往前面调，十四十九调到这最后比较这两个最后一次了，同学们还有最后一次。

那么最后一次呢？我就假设这个是最大值，那么它比较的次数应该是四，从第四个开始，那地方应该是三加一。好三加一，然后呢，这边改成三，这边也改成三。这边也改成三。好，这个做完了过后呢，就是我们第四次，好，第四次完了过后看最后结果。OK，我看效果。看到大家看到最后第四次180 30 40 90，最后外面也变成最大了。那么我们可以从这个规律我们可以看出来，我们一共要进行四次大的循环。40大的循环就搞定了。对，那大家也可以想象到啊，规律居然有了，我们有发现一个特点，第一次。

第二次。第三次，他们的代码几乎是相同的，几乎是相同，他们唯一改变的就是这个字，那既然如此，你没有必要写这么多次，于是乎，我们就可以做一个改进，怎么改进呢？把这后面的代码通通干掉。说不要了。但不是真正的不要啊，不真正的不要先注销，我们就对它进行一个负循环的处理，怎么循环处理呢？显然要把老师高亮这一部分for循环起来，负，我写成一个节等于几呢？从几开始，显然是从。是从诶这个写错了啊，刚才这个应该注销出错，出错了还得往这面再来一下啊，同学们可以看到在这里。好代码从这开始，负循环来了，For循环。解等于零，因为是从零开始走的嘛，那么解小于多少呢？我们应该是一共大循环有几次，大家可以看出来是四次，我有五个元素，我就四次循环123次，那么相当于说你的嫩子减去一个，一看规律已经有了嫩。

R减去一个一。因为最后一个元素不需要再去排序了，它没法跟谁比较，佳佳整个包起来，把谁包起来，把这段代码它。到我们的负循环里边去，没问题吧，没问题。好，那么这个时候把这个零改成勾，把这个零改成勾，把这个地方同学们想一想，是不是也应该改成勾，没问题，下面也是一样的道理，把这个零改成勾，把这个零改成勾。好，把这个零也改成勾，那现在呢，我们可以把这个打出来了。百分低。把这个改成F，然后呢，这样来一个换行，这个D呢，其实。

这个哎，那我就这样做，做一个处理啊，那这方先把这个值打出来RV，数组打出来VV好，那现在呢，我们这个D少了一个东西D呢。其实就是我们的勾加一。对的，勾加一，好写完了。那也就是说你原先的那段很复杂的代码就变成了一个负循环就搞定了。看看大家看老师是怎么一步一步演变过来的啊，这个思路还是比较清晰的，其实说白了就是把原先的这段代码套起来了。对，你得想想老师是怎么一步步做过来的，来执行一下，看代码有没有问题。跑起来。跑起来，我们看效果。哦，我们发现几乎是一样的，对吧，100第一次100和十交换，第二次，呃，是34和80交换，最后这个结果也是正确的，没问题，主要是看这个思路啊，同学们思路怎么做，那么现在我们来验证一下代码到底对不对呢？我增加几个数据。

比如说我在地方增加一个，比如说我增加一个789，那么我把这个稍微的改变一下，同学们改成六，改成六，改成六过后呢，我把这个地方也改成六就可以了，我们看看代码有没有问题。好，改改完了，我们考跑一跑。好，现在应该应该有五次。对，一杆有五次看代码。好，果然是五次，然后这个结果呢，跟我们想的也是一样的，看原先是这样一个顺序，现在从大到小呢是789 180 30 40 90正确。啊，就一步一步演变过来了，同学们这个选择排序呢，也是一个考点，就是它这个现在出出这个排序啊，一般就是这四种里面选一个。啊，当然最难的是快速排序，我们待会再说快速排序的事儿，好，现在呢，选择排序老师就讲到这儿了，我希望同学们就是能够把这个地方作为核心的代码，能够把它记下来。

就说你不要记，你要理解的记忆，说老师怎么一步步写出来的呢，你看我是怎么一步步写出来的，如果说我没有，我没有一个推导的过程，我就是直接上来，就直接这么干了一票，可能有些同学有点不好理解了。但是你现在再回过头来想想，怎么一步过来的，你应该觉得还是比较轻松啊，还是比较轻松，来，我把这个代码给它整理到这里。刚才我们讲的是什么呀，讲的是这个选择排序的一个，呃，讲解。来选择排序的介绍。把这一个板书啊，同学们这个是选择排序的一个基本介绍，然后呢，讲了选择排序的它的一个思路，他的思路其实我就我就是按照他的思路来实现的啊，一步一步实现的啊，同学们呢，也应该能够把它很好的理解出来。好，这是它的标题三，然后呢，呃，它这有一个示意图。

选择排序的。选择排序的一个示意图来，同学们，我把这个呢也写到这里来，各位朋友。那示意思路是什么样子的呢？诶，思路就是这样子的。好，就这样子，第一次怎么怎么做，第二次怎么做怎么做，对不对，好，我把这个呢来写到这里，同学们好，最后这个代码呢，我们把它叫代码实现。代码实现啊，代码实现，我把它的核心代码放到这就可以了，哎，把核心代码放到这就可以了，其实这一段就是它的核心代码。啊，把这个函数拿过来就可以了啊。好，那从这开始截取。第34行。啊，33行。放这儿。呃，其他的地方我就没结了，344往下走。啊，34啊，应该应该就可以了，好像就。好你就可以了，就这一块是最重要的，对吧。

这块是最重要的。好，同学们，那么关于选择排序呢，老师就先讲到这里，讲到这里。