排序解析

╰+攻爆jí腚メ 2022-06-13 07:36 115阅读 0赞

![019be08e-7563-3404-9422-72edf5a89534.png][]

假设有那么一群富豪，需要将他们的资产排名。（从少到多）

以下9个想法，分别代表一种排序逻辑。

想法1:

最普通的的想法是除了富豪们之外，有个助理一趟一趟的找，每趟找最富的，出列。---- 直接选择排序

想法2： 想法1改进一点点

想法1中，每趟找的时候，你都得做比较，这个避免不了，但是你不能白比较啊，比较了的话你可以让比较的俩人交换位置，这样起码部分人已经排好序了，进一步就可以整个标志，记录你这趟比较是否交换位置，如果没交换说明已经排好了，这算是一定程度上利用了你做比较，防止浪费精力啊。---- 冒泡排序。

想法 3:

还有一个很正常的想法是，不用助理，就让富豪们中间的一个人（假如排在第一个的），喊一声谁的钱少于1000万的站在我的左边，大于1000万的站在我右边。（这个富豪就是有1000万），排好后，这个人就不动了，两边的人再分别找第一个人喊，直到排玩。--- 快速排序

想法4：

你也可以这样，先让第一个出列，再让第二个出列，肯定先和第一个出列的比较下看排在哪，接着让第三个出列，再先和当前排第二的比，比他钱多的话，就站他后面否则跟第一个比较。依次类推。--- 直接插入排序

想法5：想法4再改进一点点

想法4中有的时候还可以更快点，就是利用有序数列的特点进行二分查找。假如已经排了7个，第8个人出列了，他可以先和前7已经排好的中间的那个人开始比，即第3个人，比他有钱的话再从他后边的4个人的中间的那个人比较。直到找到正确的位置。-- 折半插入排序（二分插入排序）

想法6：想法5再改进一点点（字挺多，但是逻辑很简单）

其实对于插入排序的话，如果最初始的队伍比较有序的话，对于接下来的排序肯定有好处的，极端情况下是本来就是排好的，第一出列了，第二出列和第一比较直接插在后面，第三出列和第二比较直接插在后边….假如有一两个没排好，排的话依然很快。所以可以想个办法让队伍再进行最后一次直接插入排序之前队伍有序一些。但是又不能花费太大（主要还是利用直接插入，想的这个办法只是起到辅助作用），所以先有个间隔gap，让第1和第6先比较，第2和第7比较…

这样他们间隔挺大的，每个子序列只有2个人比较，会很快，然后缩小gap，让1和4和7比较，这样每次子序列的人多了，但是gap量少了，比较还是比较快的，当然gap选取很重要啦，需要智慧的。--- 希尔排序

想法7：

你还可以这样想，两个人，两个人组成组，你们内部先比较，比较完之后，再和别的组比较，这个逻辑很普通，就像我们tao.哥如果想统计全国哪个县长最有money，肯定显示交给各个省长，各个省长交给市长，各个市内部先比较，再往上交个省。省里在比较各个市的最多的….这就是 归并排序。 当然不同两个市里的县长还是要比较的。这样其实是有好处的，毕竟每个市还是比较小的，比较的很快，同时能保证全国这样一个队伍中，这一部分是有序的。效率可想而知，相对还是比较不错的，因为生活中到处再用（ 适者生存 ）！！

想法8：

这个思维的跨度有点大， 堆排序是选择排序的一种，直接选择是普通人最正常的想法，但是又是很笨的。

![4c0c992c-3164-3f54-a10a-2e26231f219f.png][]

可以想像人站成这种形状（完全二叉树）。第一步，50和97交换位置，第二步，（13，27，65）这3个人找出最小的放在现在65的地方，显然13会代替65，之后是（38，50，76）这3个人，如果此时50是最小的（假如38被99代替）那么50上去之后，对（50，97）这两个人有影响的，需要将换下来的99和97再调整。这个过程叫做建堆，这个堆特殊点，父节点都比孩子节点大，但是左右孩子节点没特殊要求。每次从堆顶取出最小的，让最后的一个补上去，此时会再调整堆。但是这个时候调整的话就是沿着某一条线走下去，如（49，38，97，50）这条线或者是（49，38，76）有点二分查找的味道。

想法9

其实不同的事情，排序肯定依照情况而定。上述方法有限，举个最常见的例子，假如想将扑克牌排序，黑>红>梅>方，1>K>Q…

这个时候，上述排序好像不太好用，常见办法先是分成4组，黑、红、梅、方。再利用上面的排序方法排序，这个是 基数排序的一种。

[019be08e-7563-3404-9422-72edf5a89534.png]: /images/20220613/9c1899b24ce4422eb05190f2d46ab17a.png
[4c0c992c-3164-3f54-a10a-2e26231f219f.png]: /images/20220613/27c245a202eb4e059de6752bd8e79c5c.png