吴军老师的《得到》专栏谷歌方法论中，有几节课是讲排序算法的。排序，作为算法里面最为基础的一种，看似简单却非常值得深入研究，并且在研究算法的过程中也能感悟出一些平时做人做事的道理。上周我写过一篇文章，算是复盘学习到的最基本的两种排序算法知识，从最基本的选择排序和插入排序算法的对比中了解到，要想提高做事的效率，就要尽量少做事情，尽量把握现有条件，把时间和精力花在最值得投入的地方。
在这周，我学习了更为高级的排序算法，归并排序和快速排序，这两种算法在理论上的时间复杂度为O(nlogn)，通过数学证明能够证明这种复杂度是无序数组排序时间复杂度最优的极限。但在实际应用中，这两种算法又有自己的问题。人们会根据实际情况对其进行各种适用于特定场合的特殊优化处理。通过学习，我除了更加深入了解这两种排序算法之外，更有这样的感触：
1、如果能够根据实际情况，对不同的事划分出不同的优先级，分类进行处理，然后再归总，效率要比同等对待高得多。也许这就是从计算机算法的角度诠释了《高效能人士的七个习惯》中“要事优先”的原理。
2、不同的情况下，没有哪种方法是放之四海而皆准的。没有高端方法和低端方法之分，实践是检验真理的唯一标准，能高效解决问题的就是好方法。
归并排序算法：自顶向下分解问题，自底向上合并答案
首先通俗介绍一下归并算法的原理。归并算法本质上是不断将数组二分的过程。假设待排序数组的个数为8，第一次将数组从中间分为两段，每段长度为4（如果数组长度为奇数，那么就分成长度相差1的两段）；第二次将两段长度为4的数组再次二分；第三次将四段长度为2的数组再次2分，数组退化成为8段长度为1的数组。请注意，当数组长度为1的时候，它就退化成一个不需要排序的数组了。接下来，关键的是做“归并”操作，即先把2个已经有序的元素长度为1的“归并”成长度为2的有序数组。接下来，再把两段长度为2的有序数组“归并”成长度为4的有序数组。最终，再把两段长度为4的有序数组“归并”成最终有序的数组。因此“归并排序”本质上就是自顶向下分解问题，自底向上合并答案。
那么如何把两段已经有序的数组A和B归并成一大段有序的数组呢？其实也很简单。这里，我们需要首先申请一段长度为两小段待归并数组长度之和的内存空间C。首先，比较比较A和B的第一个元素，谁更小，就把这个元素拷贝到内存空间的第一个。假设是A的第一个元素更小，那么就把A的第一个元素拷贝过去，接下来比较A的第二个元素和B的第一个元素，依次类推。如果A先遍历完，即A的元素已经全部拷贝到新数组C中，那么接下来，就把B中剩下的元素按B中原封不动的顺序拷贝到C中（A、B已经有序保证了这样操作后，C一定是有序的）。
最后，来考虑一下“归并排序”的时间复杂度。首先，上一段介绍的“归并”过程是一个O(n)复杂度的操作，因为只需要完成一次遍历A和B。而层层细分过程，复杂度是O(logn)（长度为n，求能被多少次二分，因此复杂度是2为底，n的对数）。所以总体上的时间复杂度为O(nlogn)。（数学上的证明可以证明这个复杂度是排序算法的理论最优）
“归并排序”的特点是时间复杂度很“稳定”，无论原始数组是“完全顺序”的还是“完全逆序”的，完成排序的时间几乎是相同的。因为都是反复从数组自顶向下二分，然后从底向上“归并”。这样就导致了当数组元素很少或者只有很少数据是逆序的时候，它所化的时间还比不上之前所提到过的“插入排序”（接近完全顺序的情况下插入排序的时间复杂度接近O(n)）。这就说明了数学上看似厉害的高级算法在某些场景会“水土不服”。
那么如何解决这个问题呢？一个明显的改善就是我们其实不需要一直将数组二分到底。当二分到一定程度，子数组长度已经很短的时候，就可以考虑用简单的插入排序了（当长度很短时，实际情况中数组中逆序元素个数应该很少）。实际情况中，这种“归并加插入”的算法能显著提高效率。实践是检验真理的唯一标准，能高效解决问题的就是好方法。
快速排序算法：将数组元素分成几类，区别对待，最后合并答案
快速排序的思想是在数组中随机选择一个“排头兵”。然后把数组分成三部分，把小于这个“排头兵” 的放在最左侧，把“排头兵”放在中间，把等于“排头兵”的数放中间，把大于“排头兵”的数放右边，然后再对小于和大于“排头兵”的两段数组进行同样的操作，直到最后把整段数组排序完毕。
这种把一个复杂问题先按一定标准划分，再分而治之的思想在解决问题的时候非常有效。在实际测试中快速排序方法的所用的时间甚至能超过归并排序，而且快速排序方法不需要为“归并”而开辟额外的空间，因此比归并排序来说能节省空间。根据实际情况，优化“排头兵”的选择，则能够进一步提高效率。在工程应用中，快速排序仍然是使用的最为广泛的排序算法。
吴军老师对快速排序算法有自己独特的感悟：如果我们讲求绝对的公平，对每一个人，每一件事都完全平等对待，那么效率就不可能做得很高。只有允许区别对待，分类处理，才能做到最整体效率提升最大。就像一所学校，想要提高整体水平，必须对不同水平的学生进行“分班”，因材施教。而我们日常生活中对待每件不同的事情，也需要按照一定规则进行分类，比较重要的事情放在一起，很不重要的事情放在一起，这样才有利于高效处理事情。
计算机算法，看上去是“冷冰冰”的逻辑推理和代码，但实际上也蕴含着不少哲理在里面。总的原则还是想要提高效率，就得少做事情。根据事情不同的优先级，分轻重缓急进行处理，分而治之，能够显著提高效率。同时，还需要根据实际情况进行变通，高级的方法不代表任何情境下都能取得最好的效果。实践是检验真理的唯一标准。
网友评论