排序算法简单小结

最近开始准备算法。本来看的是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

Leave a Reply

Your email address will not be published.