本文无关技术，只是提供一个个人想出来的简单的记忆方法。我随便写写，大家随意看看，能有帮助那是最好。
在学《数据结构》的排序算法这一章的时候，一直有个小小困扰我的问题，就是需要记住几大排序算法的“时间复杂度”和“稳定性”。虽然我不知道对一个不搞算法的程序员，为什么非要记住这些日常工作中几乎用不到的内容，但是对于学生来讲，在日后的考试、考研、找工作笔试、甚至面试环节都有可能会遇到。所以对于这类问题，最好的解决办法就是尽量看一遍就能够长期记住，不要看过一遍马上就会忘掉，考试之前还抱着课本背诵，挺烦人的，费时费力费脑细胞。下面，就说说我的记忆方法，最近刚刚琢磨出来的，个人认为非常好使，用这种方法记忆效率飙升90%（我也不知道这个数字是怎么算出来的(∩_∩)）。
大家先看下面这张图，然后我来讲解。
一、分类方式
我把排序算法分为三类：我能想到的算法、使用“分治策略”的算法、以及其它。
“我能想到的”算法：故名意思，就是合上课本，我这种智商一般的人都能够设计出来的算法。我思来想去，确实只能想起这三种来：插入、冒泡、选择。这三种算法的思想挺简单的，大家一看就能够理解，用不了几个脑细胞，所以我把这三个归为一类。
使用“分治策略”的算法：分治策略大家懂不懂？不懂就上网搜一下，一看就明白是怎么回事。属于这一类的有快速排序和归并排序。
“其它”：属于这一类的就是剩下的我也不知道怎么归类的，就还剩下堆排序和基数排序两个，就放在一起把。
二、时间复杂度的记忆方法
首先，所有算法的时间复杂度加起来就三个：O(n2)、O(nlog2n)、O(d(n+RADIX))。除了基数排序是O(d(n+RADIX))，剩下的均分O(n2)、O(nlog2n)。
属于“我能想到的”这一类的算法的时间复杂度都是O(n2)。为什么？因为我这一般的智商，还能想起来多高效的算法出来，我一拍脑袋就能想起来的，肯定不会有多高的效率。ok，这一类就这么记住了，永远忘不了，因为我就这O(n2) 的水平。
剩下的就不用记了，都是O(nlog2n)。
三、稳定性的记忆方法
首先，这三类中，每一类有且只有一个不稳定的。
属于“我能想到的算法”这一类的，选择排序不稳定。为什么？因为对于一个有选择困难症的人来说，它的选择肯定是不稳定的。
属于“分治策略”这一类的，快速排序是不稳定的。为什么？就因为它快，鱼和熊掌不可兼得，自行车骑得太快就别想着要稳。
属于“其它”这一类的，堆排序不稳定。为什么？因为不知道为什么，每当我看到“堆”这个字的时候，就会联想到“核反应堆”之类的东西上面去。你想想，反应堆那玩意儿，感觉随时就爆炸出一朵蘑菇云出来，那能稳定吗？
PS：1、插入排序我没有再细分，它还包括二分插入、希尔排序，我这里指的是直接插入。
2、时间复杂度是指的“平均时间复杂度”，还有最优和最差的我没列出来。
3、建议大家根据理解，结合图片记忆，反正我现在脑子里只有这张图。
4、字写的很烂很烂，不好改了……
网友评论