day07_数组/14-尚硅谷-Java语言基础-算法和排序算法的概述

好，那关于这个二分法，哎，我们呢就说到这儿了，然后接着呢，我们往后来看啊，那关于算法这块的这个这个几项啊，我们最后一项的话呢，叫做排序啊，排序算法，那实际上我们刚才讲的这个叫搜索或者叫检索，其实也是一个算法了哈，就属于最基本的这个算法里边的两类，第一类呢就叫排序，对第二类呢，就是叫做查找，呃，搜索检索都是一个意思啊，那排序这个操作呢，在我们实际开发当中用的其实也比较多啊，大家呢，其实也能想到啊，就是很多时候呢，我们都有这个排序的诉求啊，比如说大家呢，呃，中午呢，你需要点餐的时候呢，美团外卖或者是饿了么啊这呢又排序，你可以按照这个距离的远近牌，可以按照这个别人评分这个高低牌啊，这的就是一种排序了啊，包括呢，我们你要是登录这个京东也好，或者是这个淘宝也好，你买一个东西，买个东西呢，它其实默认也有一个顺序，它这个默认的一个顺序呢，它是可能是柔和了很多种情况啊，比如说它默认的按照。

呃，这个比如大家的这个信誉牌，或者呢，有些人呢，他可能又做广告了是吧，然后给他靠前一点，但是但是融合了很多种情况了，那我们呢，可以显示的也给他按照价格就是从低到高，从高到低销量，还有这个这个具体的这个商品的这个评价啊，从高往低啊，这样的一个情况排序，这都是一些排序的需求。啊，这个我们都会用得到的，那一方面呢，是我们直接要用排序，另外一方面呢，诶我们呢，有的时候在查找的时候，咱们经常要查个数据是吧，查找的时候呢，呃，也需要先给它排下序，那就涉及到咱们上午讲的这个叫二分法了，哎，咱们上午讲这个二分法的时候提到说它的一个前提呢，得是先有序的，所以有的时候呢，我们为了查找更快一些啊，你要用线性查找，那太慢了，我们为了更快一些呢，就是先排序，排完序以后呢，用二分法。啊，就这样个思路啊，就相当于这个时候的我们排序呢，就是为二分法查找呢做了一个铺垫啊，基于这样的一些原因吧，哎，我们呢，都需要讲这个排序操作啊，是这样子的，首先呢，我们来看一下什么叫排序，说假设呢，还有N个记录的这个序列为R1 R2，一直到RN，这一个呢，就相当于N个数据，呃，我呢，按照它相应这个关键字的序列啊这里边这个对应的关键字的序列呢，就K1K21直到KN，呃，将这些记录呢，重新排列为排列成他，呃重新给咱们排个序哈，排完以后呢，使得它是按照我们这个，呃关键字呢，从小到大的一个顺序排的。

这个可能大家看起来稍微有点费劲哈，稍微的给你解释一下，就比如说呢，我们这里边假设呢，就是整形的数据啊，这要是整形的数据呢，它的关键字你可以理解为就是我们这个数本身。哎，我们希望呢，他是从小到大的。那我们知道这个真正咱们排序的呢，可能不一定就是一个纯看你看到的就是一个纯数字了，就比如说呢，我们你去这个点餐也好，或者你要买一个水杯吧，比如说啊，那下边呢，就会你在页面中看到很多的这个项，这一项呢，我们称作叫一个item，那每一个item呢，实际上是一个对象。

就是我们下一章要讲的这个对象，每一个item都是一个对象，你可以列解成就是一个水杯的对象，这有很多的对象啊，这些对象呢，也是可以排序的，只不过不能，只不过呢，我们不是说就是纯拿这个对象去排了，你说拿它地址去排，那没有意义啊，谁地址大谁地址小，不是那个意思了哈，那我们呢，就按照你这个对象里边它有很多的属性啊，在这儿来看呢，就叫做关键字了，比如说你这个水杯呢，有价格，有别人购买的这个数量，有别人这个评价，都作为我们这个水杯的一个属性出现，咱们呢，诶，就把你这里边的每一个水杯看成是一个二，我就按照你这个水杯里边的某一个关键字啊，是按照价格啊，还是销量啊，进行一个从小到大的排序，相当于重新去组合我们这些水杯，让它形成一个2I1 I2，一直到in这样的一个顺序。就是这个概念的话呢，就更通用一些哈，不光是针对咱们这个数值型的，针对于后边我们讲的这个对象呢，也是适用的啊是这个意思，那这呢也提到说排序的目的呢，很多时候呢，都是为了我们快速去查找，哎这个做准备的啊行，那么下边呢，先提到一个就关于衡量这个排序算法优劣的一个指标，呃，咱们前边讲课的时候呢，呃，我记得咱们是讲那个质数输出的时候呢，提过一下啊说呢，我们如何衡量一个算法的优劣，主要呢，是有两个指标，从时间上，从空间上，哎，我们呢，追求的叫高效率和低存储。

啊，那么这个高效率呢，就是和时间上的，哎，我们用时间复杂度呢来进行衡量。哎，通常呢，我们都判断它跟咱们这个容量的一个关系啊，这叫时间复杂度，呃，这个详细的话呢，我就不在这展开去给大家去，呃，比如说复杂度怎么去判别啊，怎么一点点推出来啊，呃，这个呢，大家后期可以关注一下这个数据结构的这个视频，到时候咱们会这个专门来讲这个问题啊，然后呢，这个空间复杂度的话呢，就是我们这个排序呢，你又需要呃额外多少的辅助内存。

啊，像咱们排序呃，这个上午讲的，包括这个上午比如说这个反转，反转的话呢，咱们这就需要额外的你开辟一个空间，呃，让我临时存储这个变量就可以了啊，这也算是叫额外开辟的这个空间啊，这就叫空间复杂度，那这儿呢，因为你就开辟这一个跟容量没有关系，所以这种我们一般都集成叫O1了，就是常数级别的这种啊，有的呢，可能是随着你这个容量的增加呢，它跟这个N有关系了啊，就涉及到其他的一个复杂度的情况啊，那么通常一个算法的话呢，我们都通过这两个指标去衡量，但是针对于咱们排序算法的话呢，又多一个。多一个叫做稳定性。诶，和为稳定性，说两若两个记录A和B的关键字值相等，但排序后呢？AB的先后顺序呢保持不变，我们就称它是稳定的。这个能看懂吗？这个稍微有点迷糊是吧？举个例子啊，比如说呢，我这有一个数组，我就诶举一个例子，比如说这这是一个三啊，然后四，然后一呃五，然后二三好这呢，就是我们这样的一个数组了，这个数组里边呢，这有一个三，这有一个三啊这个为了稍微区分一点，我这个三呢，打一个小撇哈，就是一个竖三，哎，那么这个数值型的一个数组，我们排序以后呢，肯定是123，然后三，然后四五是这样子了哈，那这里边你看这两个三。

如果原来这个不带撇的三呢，排序以后呢，这个三还在前面，带撇的还在后边，我们就把这个叫稳定的，如果你排完以后呢，你发现这个带撇这个呢，有可能就跑到前面了。跑到这个三的前边了，我们把这种呢，就叫做不稳定的排序。哎，就要不稳定的啊，那么前两个好说，就是时间要快一点，这个空间呢要少一点，那稳定性这块呢，有这么个指标有啥用啊。

你说衡量就是你排完以后呢，这个你俩相同的这个数位置有没有变有啥用。谁的钱对猛音响可能还想不出来是吧，那我们举个例子哈，比如说呢，咱们一开始的话呢，这个商品，一开始这个商品呢，已经按照这个销量呢，从高到低排了，已经这个销量从高到低了，但是在这里边呢，可能会有一些价格相同的，对吧？诶价格相同的，那么我们接下来的话，或者这个价格都不一样啊，我们除了按照从高到低这个销量排之外呢，我们再指定一层排序，就是按照这个价格呢，比如说从低到高排。就是在销量从高到低的基础之上呢，价格呢，我们让它从低到高，那这个时候呢，如果两个商品的价格一样，商品的价格一样啊，那我们是不是就希望他原来人家那个销量高的是不是就还在上边，销量低的你还在下边，那本身人家就是从高到低的顺序，你不要变这个顺序，那不就是希望呢，你就看你关不关心这个事儿了哈，你要关心的话呢，是不是就让他稳定一下得。

啊对啊，就是你这俩价格一样的话呢，让那个销量高的还在上面啊，那这种呢，就是你需要是一个稳定的一个排序，那就意味着我们现在讲排序算法拿出这个指标来了，那就说明有的是稳定的，有的就不稳定。啊，就这个意思啊好，呃，这呢是我们先了解一下这个问题，呃，再者呢，我们对这个排序呢，进行了一个分类，这个分类呢，其实也很好理解啊，内部排序呢，简单来说就是在内存中完成的，称作叫内部排序啊外部排序。内存中搞不定了啊，比如我们现在这个，呃，数据呢，是这个数据呢，比如是两个G的数据，但我现在内存呢，假设就只有一个G。啊，你这时候不可能把两个G的内存，这个数据呢，全部加载到内存中也盛不下呀，诶那这时候呢，我们就需要依赖于这个叫外部的设备了，诶我们呢，先存到这个磁盘当中，诶我先取其中的一部分数据呢，进行排序，诶排完以后呢，再写出啊写出比如说你要写到另外一个文件中，然后呢，我们再取这一部分数据再排。

啊，就是呃，需要借助外部存储设备的，这样的排序呢，我们就称作叫外部排序。哎，很好理解这个问题啊。行，这呢是关于这个排序的一个分类啊，这就过了，哎，下边的话呢，列举出来咱们呢，叫十种排序算法。注意，这跟Java也没有太大关系哈。那不是说Java中有十大排序算法，放到C语言，放到tython语言，Go语言等等，就不是十种了，这不是这个呢，跟具体的哪个语言没有关系啊，就跟咱们之前说那个数据结构一样啊，诶这呢是这个算法层面的算法呢，你就看你讲了一个排列算法，你就看用某个语言怎么去实现啊，这样它是两个层面的这个内容啊，那么整个在排序这块呢，哎，比较全的话呢，就是有十种，哎比较全的话就是十种，那十种里边你又往下再砍一砍呢，算是有比较常用的呢，是上边的这八种。

你看啊，12345678啊，然后下边呢90是吧，这两个呢，用的稍微少一点啊，就是说全的话是十种，但是通常呢，大家去网上啊，或者这个你看一些帖子啊或书上的时候呢，通常他要讲的话，可能是呃，都要讲这八种啊，这八种呢，算是这个频率稍微高一点啊，然后每一种排序方法呢，都有它不同的排序的思想。啊，都有它不同的排序的思想啊，整体上呢，都是以这种选择为主的，我们叫做选择排序啊，以交换这种为主要特点体现的啊，我们叫交换排序，还有插入的叫插入排序啊，这个shell排序也叫做希尔排序，哎，翻译过来也可以啊，希尔排序。那这是一个音译啊，有个人叫shell是吧？嗯，那详细的话呢，关于排序操作呢，这我给大家提供了一个文件啊，诶把这个打开。

啊里边呢，关于每一种排序的，呃，它的实现的思想，包括呢，具体的举例子啊，在这边都有啊这个咱们先不看啊，先回过来，那么对于大家来讲，我们关于这十种排序的一个要求是什么呢？就是知道有十种，这要求好低啊是吧？哎知道有十种，然后的话呢，我这标红的这两个，哎标红的这两个呢，需要大家呢会手写。哎，冒泡排序我们一会儿就讲，哎冒泡排序为什么讲它呢？因为它特别简单啊，就是你正常来讲都能够手写出来的啊，然后快速排序为什么要讲他呢？或者需要大家掌握呢，因为他快，这个嗯，对于男生来讲不要太快是吧？嗯，快速排序呢，这个是我们开发中基本上都用它啊，所以说我们这块呢，也需要大家看一看这个怎么写是吧？但是这个话呢，我现在先不讲啊，就是我只是给大家这个思路说清楚，为啥呢？因为这快派里边呢，我们需要讲方法，用方法，但方法呢咱们还没有具体涉及，所以呢，只是把这个思想呢给大家说一下啊，另外的话，就现在讲的话呢，你回头你写一写，到面试的时候也就忘了，所以这个呢，比较适合于突击一下是吧，啊或者最起码呢，你把这个快拍这个思想能知道它是怎么一种想法进行排序的啊，这个呢又比较重要，然后另外的话呢，放了两个这个黄色的，一个叫堆排序，一个叫归宾。

排序，哎，这两个排序呢，就是知道它是什么样的一个排序思想就可以了，不用大家去手写了。啊，这个笔试面试的时候，可能人家会问你哈，说关于排序这块的话呢，诶你都了解什么排序方法啊，你说呢，我知道冒泡排序，知道快速排序，知道归并排序，知道堆排序，或者你说还有别的什么希尔排序，折半折半这个插入等等，你可以说很多，但是他不会说，诶那你说一下折半插入是怎么实现的，他不会问的啊。

啊，他不会问的，他问了呢，你就告诉他，你说不知道，就没有人这么无聊的，他就天天把这几个排序，每一个都整的很清楚的，是吧？啊就完了，哎，但是他有可能会问你说规定排序是怎么设计的，哎，你能说一说吗？哎，这时候你得能说一说啊，或者人说快排你能写吗？啊，你要你要真能，你就说我能啊你那那你写一下，那你写写，你要说我不能，但是我能跟你说一下它的一个实现思想也可以啊就这样子啊，就是最起码呢，就是这里边，呃，画红的包括黄的，你能给他说一说它是怎么样一种思想实现排序的就可以了啊，因为咱们真正在开发当中啊，实际上咱们都不会自己去手写这个排序的了啊对于Java来讲的话呢，都给你写线程封装好了，我们直接调就可以了啊，但是呢，咱们也得知道最基本的你能写一个是吧，那就冒泡排序你也得能够自己实现一个啊，就这意思，嗯好呃，在下边呢，我这提到一个关于算法的几大特征，这是咱们顺便呢说一下啊，讲到这个。

个排序了，排序呢属于算法的一种啊，这个算法的概念呢，是很抽象的啊，就是凡是呢，你完成一个具体的功能啊，有固定的几个步骤实现的这样一个结构，我们都可以称作叫算法了，算法呢满足这五个特征，第一个呢叫做输入。诶，通常呢，我们需要零个或多个的输入数据，这些输入呢，必须要有清楚的描述和定义算法，你要做个事儿，你得给我提供点原材料，所谓的原材料呢，就是你有输入的东西啊，然后输出，诶我们算法呢，给你算了半天，那通常呢，你都会有一个输出的结果，你不能算完以后啥事也没有啊，那不行啊，哪怕呢，我们说那个，呃，反转一样是吧，你反转的话呢，反转完以后，那就是你对原本的这个数组进行了修改，那原本的这个数组修改以后，它就也算是个输出的结果了啊下一个呢，叫做有情有穷性，或者叫有限性，就是我们这个算法呢，必须在有限的步骤之内呢，你得能够结束啊，不能是一个无限循环，那就死循环了。

而且呢，每一个步骤呢，都可以在可接受的时间范围内完成，你不能告诉我说，告诉我说是是有限的，但是呢，需要十年的时间，我等不了十年哈，哎，那你必须得在可接受的时间范围内去完成啊，下一个呢，叫做确定性或者叫明确性啊，就是算法中的每一步呢，都要有确定的含义，不会出现二异性。你不能有歧义，所以这个到底怎么去解释啊，你自己要是都不清楚的话呢，计算机执行起来，那就更不知道该怎么执行了啊，这叫确定性，下个呢叫做可行性，或者叫有效性，就是算法的每一步骤呢，都是清楚可行，清楚且可行的，哎，能够用纸跟笔呢，呃，这个能够算出来的，就是你要不借入计算机，我们呢，按照你写的这个步骤呢，也是可以给大家计算出来的啊，就这种啊啊，其实越说呢，越像是数学题一样。

啊，其实这个算法呢，就像原来大家积累的这么长时间的这个数学的功底一样啊，那其实都可以体现在你这个算法层面上啊，是这种，那下边呢又额外的说了，说说满足确定性的这个算法呢，也称作叫确定性算法，现在呢，人们也开始关注更广泛的概念啊，就是这是最传统上对算法的五个特征的定义啊，后来的话呢，发现这个范围我们可以在拓拓展拓展，就是也会有一些所谓的叫非确定性的算法啊，比如叫并行算法呀，概率算法呀啊等等啊，尤其像这个概率统计，呃，大家呢，这个这个。不知道原先上大学有没有学过这个概率统计啊，学学过吧，学过或者至少说这个考研的这个同学，诶考研你们考应该是数二是吧，数二好像没有概率统计，对啊，其实这个概率统计的话呢，其实还是可以值得学习学习，尤其是现在这个人工智能火起来以后呢，人工智能最初都是用机器学习算法来做的，那里边儿呢，这概率统计那是必须要掌握的了，呃，然后深度学习以后，那也是基于这个机器学习展开的啊，那你像这个概率统计里边呢，就很有意思哈，嗯，比如说呢，统计最初呢，其实不把它归到数学的一个门类，或者不认为这个统计呢是一门科学。

啊，什么叫科学呢？就是这个科学本身这个词呢，其实也是西方定义的，咱们哪有这个科学这个词啊是吧？呃，这个科学呢，就是说他能够说出因为所以来，因为所以然啊，因为什么所以什么啊，就是能够解释的很清楚的，它叫一种科学。啊，就是这不也好多说说中国的这个中医说是不科学的是吧，或者叫伪科学等等啊，就是大家呢，也不要被这个词所误导了，好像说这个东西要是不科学，它就一定是假的，一定是骗子，也不一定，只不过这个词呢，就是我们能够清晰的解释出来的，你可以把它就认为叫科学了，那中医的话呢，事实上它也确实有效，那你可能这几种药也不知道它到底是干什么，咔咔往里边一怼，然后咔一煮，然后喝了又好使是吧，这是实验科学，或者你不要让科学，那就是实验，通过大量的统计，我们发现吃这种药它就是对什么什么有效。

啊，你要非要说他有什么原因，可能也说不出来，就是通过实践出来的啊，它不像西医里边跟你都画，画到那个分子链上了是吧，说就是那个链的成分啊，它就是有效的或者无效的，它能说的很清楚，把那个它叫科学了，那不能因为中医你说它不科学，说中医它就是假的，是骗人的，那不对是吧？那统计学呢，其实一开始也是啊，你比如说说这个人的身高和体重，哎，经过大量的这个样本统计数据，结果呢，一发现他们满足一个线性关系啊，说身高越高体重就越重，举个例子啊，哎，身高越高体重就越重，哎结果他就能够通过一个函数图像，哎可以去给他拟合出来，然后呢，你再随便给我一个人的身高，我大概就能算出来他的体重在什么范围内。哎，这就是统计学其实可以解决的问题，你要非要说说为什么说身高越高体重就越重，可能解释不了，反正呢，就是这个关系是吧，哎嗯，有的一开始就说这个统计学说不科学，假的怎么着的是吧？啊其实后来呢，呃也也使用数学的方法，把这个统计学概率论都给它量化了啊，后来又归进来了啊但里边呢，还会有一些呃，所谓的叫不确定性的这种，你可能写不出来，因为所以的这种啊啊但是呢，我们也把人家称作是一种算法啊，其实现在大家如果关注关注这个人工智能的话呢，人工智能现在这个为什么现在又崛起了，就是因为这个深度学习的崛起啊，深度学习的话呢，我们这儿呢，给这个计算机很多的这个数据，让他去参考，然后他就一层一层的这样去算。

一层层的去算，然后最后呢，给你得出个结论，比如说你给了很多张图片，然后那计算机开始就模拟去计算，然后最后呢，诶，你给大家的一个指令，说你告诉我这些图片里边哪一张是猫。诶，他就给你算出来啊，说这张图片是猫，其他的都不是，那这个过程当中呢，其实具体这个计算机怎么算呢，说实话现在呢，有些时候我们不太清楚。

啊，正因为人现在不清楚，所以说呢，现在才会产生说这个计算机有一天会不会超过人啊，会被这个这个人就被计算机给主宰了，很多科幻片里边都有啊，现在包括霍金在内哈，就是对这个人工智能的发展呢，都是持这个悲观态度啊，还有那个马斯克好像也是哈，就持悲观态度的啊，为什么说持悲观态度，按说的话呢，这个算法我们都能够清晰的知道它执行的是什么，那就不用担心了，但关键呢，就是，呃，对对，在深度学习里边呢，它有很多呢，是我们不确定性的。当然呢，它也是算法。啊，就是这个我们让计算机呢去迭代，去运算，在这个运算过程当中，比如下围棋一样，啊，他确实告诉我们说这个子应该放在这儿，但是他除了告诉我们子在这之外，他还获取了哪些其他的信息，还得到了哪些其他的信息，这个我们不知道，哎，正义你不知道，所以我们就很担心说是不是他明确知道什么东西，但是他故意不告诉我们是吧，那一旦要这样的话，那就坏了，那说明说明人工智能他就具有了意识，他一旦具有意识这个事儿就非常恐怖了，是吧？啊，而且的话呢，它要一旦迭代到那个程度，它的迭代速度会极快极快的哈。

啊，就像当时当时打败这个李世石的那个阿尔法狗，呃，当时这个柯洁还说说说这个李世石不行啊，我要跟他PK的时候呢，肯定不会打成那样是吧？啊，但是没想到就是阿尔法狗呢，在这个几个月的时间，后来跟这个柯洁在下强季的时间，它又大量的迭代，所以人家迭代几个月，那相当于人类可能几十年甚至上百年才能迭代的一个效果，那这个科阶一打都哭了都是吧，没法玩啊，就根本就计算机就打不过计算机啊，那计算机一旦要超过人以后呢，它后期的迭代速度那就极快了，就怕这个时候是失控的是吧？啊，就是因为里边它有很多是非确定性的啊，但是呢，他确实能够完成我们的需求。啊，那那就是这样的一个现实是吧，好这呢就是提到这个算法的几大特征啊，另外呢，说这也关注一下，就是呃，有的时候呢，这个呃不是说马上要求他把数据算出来，我们也关注于在这个过程当中的这个得到的一些数据啊，把这个称为一个过程，行这呢是咱们对这个算法呢，先进行了一个概述啊。