day07_数组/17-尚硅谷-Java语言基础-排序算法的横向对比

那快排说完以后，呃，剩下的呢，还有一个呢，叫做堆排序，一个归并排序，我们就不讲了，大家如果有兴趣的话呢，你可以参照一下这个PDF，诶你看一看这个，呃，堆排序归并排序大概怎么做的就行，哎，那其实时间呢，现在也比较紧，这个大家也可以就不看了，就哎还是等到最后整体复习的时候呢，你再研究研究堆和归并啊怎么回事就可以了啊行，那我们稍微总结一下。整体来讲排序的话呢，有十种啊，整体来讲有十种，可能真正咱们开发的时候呢，一种也不用写，直接调一个现成的结构就行啊，一会儿咱们说那个数组的工具类啊你就知道了，那毕竟呢，我们是讲到这块内容啊，咱们呢也需要大家呢关注一下，说排序怎么实现的，所以咱们讲了一个冒泡，讲了一个快速，那么整个这有十种，他们这十种呢，有一个对比啊，就是这里边这个表格大家去网上一搜的话呢，也肯定能搜到很多啊，就是提供这个表格的啊，这呢是一个比较全的啊，就是提到了这有十种排序，这个排序算法的话呢，我们很难说，说一个呢出现以后呢，就能把其他的都干掉，说就用这一个就是完美的。

啊，不一定，呃，就是每一种算法呢，它有自己的一个适用的一个特点，其实哈，呃，下边你先看这个图吧，哎，先看这个文字哈，哎这呢，我们关于各种排序呢，有个比较说从这个时间上来讲呢，快排确实快。啊，快拍确实快啊啊，但是它在这个最坏的情况下呢，性能可能不如堆和归并，只是从平均的角度来讲呢，它是最快的啊，只是这样的一个说明啊，这就涉及到关于我们这个算法的一个叫时间复杂度，通常的话呢，大家会看到这个复杂度呢，可能这个数呢都不太理想，都接近于叫N方了。因为像这个冒泡，你看N方，哎怎么理解，哎这呢，你是不是跟这个长度N，你是N减一，但其实相当于还是NN级别的是吧，你这个呢，从前往后减了in，减了个I，其实嗯，减个I也行哈，这两个一乘，我们取它的这个最高次幂是不是还是方啊，所以这个复杂度就是N方。

啊，那么比这个好的呢。哎，比它好一点，你看这有个希尔排序哈，希尔排序你看稍微好一点。是吧，这是这个平均的情况啊，这个又分成有最坏的，有最好的，就是你这个数据呢，要是非常不满足它的特点，那它就属于比较坏的了啊，最好的呢，通常呢，我们这个都不会是最好的啊，咱们一般排序的话呢，要么关注最坏的，要么关注平均啊，一般呢，都不会考虑说最好怎么着啊嗯，然后在这几个里边呢，我画红框的这个呢，这三个你会发现堆排序，快排和归并呢，都是N乘log根。这是平均的复杂度，然后呢，你看这个坏的情况呢，人家这还是N乘老根，这个还是，然后这个坏牌道反而变成N方了，按说呢不理想，就是N乘以log根它的这个，呃，这个这个增长速度肯定比较慢哈，你这个N方这个呢，不是比较快嘛，就我们得挑这种次幂低的。

你要按说的好像是不是应该选堆排序和归并排序了啊，但是呢，我们没有选，为什么呢？就是我们通常也不是最坏的，咱们更多的关注的是平均的，平均的，虽然它俩都是N乘以log，它仨都是N乘log，但是也有区别啊，你就比如说咱们这个复杂度是on吧，然后你可能是2N，也可能是3N，它可能是100N呢，你这些呢，是不是都叫on呢？对，就是虽然说他们仨都要，但是这个系数还不一样呢，就这样去对比的话呢，快排其实系数都比他们要小。我们平时关注更多的还是平均，所以呢，快牌从平均角度来讲比这俩都快，只是说呢，最差的情况呢，不如他俩，但是通常也不会遇到最差的。啊，就是通常都是这种平均的一个情况啊，所以咱们关注比较多的就是快排啊，这两个为什么也爱问呢？就是他们俩的，你看执行效率其实也挺高的，哎，所以呢，有的时候会呃笔试或面试的时候问问你说这两个是怎么设计的，哎，也就问问你的思想就可以了，不用去写哈，好嗯，就是你你像就是别说你写了，你你说我不会写，你给我写写他也不会写啊，他也写不了啊就是你要没有经过特定的这个就得是练它就是为了面试啥去练，其实很难拿起来就能写的，好嗯，这是说的这个叫快排了啊嗯，这里边看我写的没有这种十全十美的这种算法是吧，每种算法它都有这个，它一定的缺陷啊，只是说整体性能上，你关心的是什么，你就用哪一个啊，嗯，从这个简单性上来讲的话呢，这三个呢叫简单的排序，这四个呢，叫做稍微复杂的稳定性来讲啊，有些是稳定的，有些是不稳定的，哎，我们也说这个概。

现了，整个呢，都在这个图当中有个体现，大家呢，没有必要去背这个图啊，你非要说呢，我们需要记住什么呢？记住这样几个事儿，第一个冒号排序N方。

快排N乘以log文。为什么他是恩城老根呢？哎，你看我们这个你你从这个低的这是高的，然后低的高的往这走，实际上你都得遍历一遍是吧，这涉及到呢，是叫on了，就是跟no跟N的一次方是相关的，但是你每次你折半了，折半呢相当于除二了，哎，你就相当于是二的X次方等于N一样，然后我们解这个X，它不就等于LOG2N吗。啊，每次呢，这不都是从大方向来讲，每次拆一半拆一半拆一半，这不就是二的几次方的方式吗。啊，那这个呢，不就是N再乘以这个log n嘛，哎，正好就是这样的一个复杂度，哎大家呢，也就把这两个记一下。就可以了，他可能会问你哈，说快排的复杂度是多少？你说N乘以log log2N。哎，就可以了，行，后边这块呢，还有说在什么情况下呢，用哪个好一点，这个呢，大家看一眼就行啊，不用过多的去关注啊。

好，这就是我们对这样的几种算法呢进行了一个对比。