OnlyLonely & Marshall’s

最近开始准备算法。本来看的是Algorithms(算法概论)，后来瞄了瞄算法导论，决定还是从基本的数据结构看起。Eric Raymond曾经说过:Show me your code and conceal your data structure, and I shall continue to be mystified. Show me your data structure, and I won’t need your code; it’ll be obvious.

虽然看的是数据结构的书（殷人昆的那本C++），但第一眼还是算法–排序。主要是昨天的IBM笔试，把排序的一些基本知识都给忘光了。下面进入正题。

排序首先分为内排序和外排序。其中内排序是基础，外排序则是在内存不足的情况下，对内排序进行了一些相应的改进。

简单的内排序主要有以下几种：

插入排序

简单插入排序。假定前i个元素有序，从后面不断取出元素插入前面有序数组中。复杂度为O(n2)，最好情况为O(n)(数组原本有序)。稳定排序。

折半插入排序。简单插入排序的改进。在插入过程中，使用折半搜索找到插入的位置，其他方法相同。虽然比较的次数下降到了O(nlogn)，但是移动次数仍然为O(n2)。稳定排序。

链表插入排序。改进简单插入排序，减少了移动次数。但比较次数仍然为O(n2)。稳定排序。

希尔排序（Shell Sort）。每隔几个元素为一组，进行简单插入排序；不断缩小间隔直至对整个数组进行简单插入排序。由于前面阶段每次排序元素数目少，所以开销不大；后面阶段中，每次参与排序的元素或多或少都有点排序的基础了，所以效率也挺高。没有确定的时间复杂度分析结果。Knuth做了大量的实验，结论大概为O(n^1.25-1.6n^1.25)不稳定排序（听说有稳定排序的实现，但先权当不稳定）。

交换排序

冒泡排序。不断交换，每一次Pass都把最小的换到最前面或者把最大的换到最后面。O(n2)。稳定。这是我接触的第一个算法，不过当时死活没明白，因为只有小学3、4年级。老爸倒是明白了，当时无限崇拜。

快速排序。Divide & Conquer思想。面试里很喜欢考的排序算法。把小于数组里某个数（这个数的挑选有学问）的数放到这个数的左边，大于的数放到这个数的右边。然后递归排序其左右两边的子数组。O(nlogn)。不稳定。

选择排序

直接选择排序。每次从后面的数组里挑最小的一个放到最左边。O(n^2)。不稳定排序。

竞标赛排序（胜者树）。改进了选择算法，使用两两比较的算法选择最小数。O(nlogn）。稳定排序。

堆排序。所有的parent < child。O(n)的建堆时间，很适合求一个数组内top n个数。O(nlogn)排序时间。不稳定排序

归并排序（Merge Sort）

2路归并排序。迭代或递归的从小到大不断合并。O(nlogn)。稳定排序。

基数排序

扩展了桶排序(Bin Sort)的思想，把桶分级了。可能需要消耗较多的空间。应用受到局限。O(d(n+radix))，d为级别数，radix为桶数（假定每一级的桶数相等）。稳定排序。

外排序主要在归并排序上做文章。如k路平衡归并，扩大初始归并段，还有借鉴了霍夫曼树的最佳归并树优化，均是为了减少IO次数。值得一提的是，k路平衡归并里使用了败者树。和胜者树不同的是，败者树每次选择了败者进入上级节点，而把胜者信息单独记录。从而简化了每次重构（UpdateTree）的过程，比如不需要判定对手是在左边还是右边，直接和parent做比较（因为上次的败者被选择进了parent）。

另外排序算法还有其他的衡量指标，比如空间复杂度。部分算法是就地排序，使用O(1)的空间，比如插入排序（链表除外），直接选择排序，堆排序，交换排序。

只是简单的整理。更详细的资料可参阅维基百科词条：排序算法，Sorting Algorithm。