本章内容只是在讲排序,我们需要对已经提到的各个排序算法进行对比来总结回顾。
首先我们讲了排序的定义,并提到了排序的稳定性,排序稳定对于某些特殊需求来说是至关重要的,因此在排序算法中,我们需要关注此算法的稳定性如何。
我们根据将排序记录是否全部被放置在内存中,将排序分为内排序与外排序两种,外排序需要在内外存之间多次交换数据才能进行。我们本章主要讲的是内排序的算法。
根据排序过程中借助的主要操作,我们将内排序分为:插入排序、交换排序、选择排序和归并排序四类。之后介绍的7种排序法,就分别是各种分类的代表算法。
事实上,目前还没有十全十美的排序算法,有优点就会有缺点,即使是快速排序法,也只是在整体性能上优越,它也存在排序不稳定、需要大量辅助空间、对少量数据排序无优势等不足。因此我们就来从多个角度来剖析一下提到的各种排序的长与短。
我们将7种算法的各种指标进行对比,如表9-10-1所示。
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
简单选择排序 | O(n2) | O(n2) | O(n2) | O(1) | 稳定 |
直接插入排序 | O(n2) | O(n) | O(n2) | O(1) | 稳定 |
希尔排序 | O(nlogn)~O(n2) | O(n1.3) | O(n2) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n2) | O(logn)~O(n) | 不稳定 |
从算法的简单性来看,我们将7种算法分为两类:
- 简单算法:冒泡、简单选择、直接插入。
- 改进算法:希尔、堆、归并、快速。
从平均情况来看,显然最后3种改进算法要胜过希尔排序,并远远胜过前3种简单算法。
从最好情况看,反而冒泡和直接插入排序要更胜一筹,也就是说,如果你的待排序序列总是基本有序,反而不应该考虑4种复杂的改进算法。从最坏情况看,堆排序与归并排序又强过快速排序以及其他简单排序。从这三组时间复杂度的数据对比中,我们可以得出这样一个认识。堆排序和归并排序就像两个参加奥数考试的优等生,心理素质强,发挥稳定。而快速排序像是很情绪化的天才,心情好时表现极佳,碰到较糟糕环境会变得差强人意。但是他们如果都来比赛计算个位数的加减法,它们反而算不过成绩极普通的冒泡和直接插入。
从空间复杂度来说,归并排序强调要马跑得快,就得给马吃个饱。快速排序也有相应的空间要求,反而堆排序等却都是少量索取,大量付出,对空间要求是O(1)。如果执行算法的软件所处的环境非常在乎内存使用量的多少时,选择归并排序和快速排序就不是一个较好的决策了。
从稳定性来看,归并排序独占鳌头,我们前面也说过,对于非常在乎排序稳定性的应用中,归并排序是个好算法。
从待排序记录的个数上来说,待排序的个数n越小,采用简单排序方法越合适。反之,n越大,采用改进排序方法越合适。这也就是我们为什么对快速排序优化时,增加了一个阀值,低于阀值时换作直接插入排序的原因。
从表9-10-1的数据中,似乎简单选择排序在3种简单排序中性能最差,其实也不完全是,比如,如果记录的关键字本身信息量比较大(例如,关键字都是数十位的数字),此时表明其占用存储空间很大,这样移动记录所花费的时间也就越多,我们给出3种简单排序算法的移动次数比较,如表所示。
排序方法 | 平均情况 | 最好情况 | 最坏情况 |
---|---|---|---|
冒泡排序 | O(n2) | 0 | O(n2) |
简单选择排序 | O(n) | 0 | O(n) |
直接插入排序 | O(n2) | O(n) | O(n2) |
你会发现,此时简单选择排序就变得非常有优势,原因也就在于,它是通过大量比较后选择明确记录进行移动,有的放矢。因此对于数据量不是很大而记录的关键字信息量较大的排序要求,简单排序算法是占优的。另外,记录的关键字信息量大小对那四个改进算法影响不大。
总之,从综合各项指标来说,经过优化的快速排序是性能最好的排序算法,但是不同的场合我们也应该考虑使用不同的算法来应对它。