排序是非常基本的并且是非常重要的算法知识,是每个程序员都应该掌握的内容。
概述
排序算法的分类
一般来说,常见的排序算法分成两大类,一是内部排序,一个是外部排序。内部排序是最为常用的,今天且来讨论内部排序。
内部排序分成4类 :12A(插入排序) --> B(直接插入排序)A --> C(希尔排序)
|
|
|
|
|
|
排序算法的实现
直接插入排序
|
|
希尔排序
|
|
直接选择排序
|
|
堆排序
|
|
冒泡排序
|
|
快速排序
|
|
二路归并排序
|
|
排序算法的性能比较
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 是 |
希尔排序 | o(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 否 |
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 是 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 否 |
简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 否 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 否 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 是 |
就时间性能而言,在希尔排序、堆排序、快速排序和归并排序等改迸算法当中.快速排
序目前被认为是最快的一种方法,而在待排序元素个数比较多的情况下,归并排序较堆排
需更快。
就稳定性而言,直接插入排序、起泡排序和归并排序是稳定的排序方法,而简单选择
排序,希尔排序、快速排序和堆排序是不稳定的排序方法。
因此考虑到以上各种因素,在选取排序方法的时候可以采用如下原则。
① 若排序元素的数目n较小(如n<=50时,可采用直接插人排序或简单选择排序。
由于直接插人排序所需的移动操作较简单选择排序多,因而当元素本身信息量较大
时,用简单选择排序比较好。
② 若元素的初始状态已经按关键码基本有序,可采用直接插入排序或冒泡排序。
③ 若排序元索的数目n较大.则可采用时间复杂度为o(nlogn)的排序方法如快速
排序,堆排序或归并排序等。快速排序的平均性能最好,在待排序序列按关键码随机分
布吋.快速排序最适合。快速排序在最坏情况下的时间复杂度是o(n^2),而堆排序在最坏
情况下的时间复杂度不会发生变化,并且所需的辅助空间少于快速排序。但这两种排序
方法都是不稳定的排序.若需要稳定的排序方法,则可采用归并排序。
(注:本文参考了 北京邮电大学出版社《数据结构与STL》,侵删)