排序算法

维基百科,自由的百科全书
跳转至: 导航搜索

計算機科學數學中,一個排序算法(Sorting algorithm)是一種能將一串資料依照特定排序方式进行排列的一種算法。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法(例如搜尋算法合併算法)中是重要的,如此這些算法才能得到正確解答。排序算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上,排序算法的輸出必須遵守下列兩個原則:

  1. 輸出結果為遞增序列(遞增是針對所需的排序順序而言)
  2. 輸出結果是原輸入的一種排列、或是重組

雖然排序算法是一個簡單的問題,但是從計算機科學發展以來,在此問題上已經有大量的研究。舉例而言,氣泡排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題,有用的新算法仍在不斷的被發明。(例子:圖書館排序在2004年被發表)

分類[编辑]

计算机科学所使用的排序算法通常被分類為:

  • 計算的複雜度最差平均、和最好表現),依據串列(list)的大小(n)。一般而言,好的表現是O(n log n),且壞的表現是O(n2)。對於一個排序理想的表現是O(n)。僅使用一個抽象關鍵比較運算的排序算法總平均上總是至少需要O(n log n)。
  • 記憶體使用量(以及其他電腦資源的使用)
  • 穩定度:穩定排序算法會依照相等的關鍵(換言之就是值)維持紀錄的相對次序。也就是一個排序算法是穩定的,就是當有兩個有相等關鍵的紀錄RS,且在原本的串列中R出現在S之前,在排序過的串列中R也將會是在S之前。
  • 一般的方法:插入、交換、選擇、合併等等。交換排序包含冒泡排序和快速排序。選擇排序包含希尔排序堆排序

穩定度[编辑]

當相等的元素是無法分辨的,比如像是整數,穩定度並不是一個問題。然而,假設以下的數對將要以他們的第一個數字來排序。

(4, 1)  (3, 1)  (3, 7)(5, 6)

在這個狀況下,有可能產生兩種不同的結果,一個是依照相等的鍵值維持相對的次序,而另外一個則沒有:

(3, 1)  (3, 7)  (4, 1)  (5, 6)  (維持次序)
(3, 7)  (3, 1)  (4, 1)  (5, 6)  (次序被改變)

不穩定排序算法可能會在相等的鍵值中改變紀錄的相對次序,但是穩定排序算法從來不會如此。不穩定排序算法可以被特別地實作為穩定。作這件事情的一個方式是人工擴充鍵值的比較,如此在其他方面相同鍵值的兩個物件間之比較,(比如上面的比较中加入第二个标准:第二个键值的大小)就會被決定使用在原先資料次序中的條目,當作一個同分決賽。然而,要記住這種次序通常牽涉到額外的空間負擔。

排列算法列表[编辑]

在這個表格中,n是要被排序的紀錄數量以及k是不同鍵值的數量。

穩定的[编辑]

不穩定[编辑]

不實用的排序算法[编辑]

平均时间复杂度[编辑]

平均时间复杂度由高到低为:

说明:虽然完全逆序的情况下,快速排序会降到选择排序的速度,不过从概率角度来说(参考信息学理论,和概率学),不对算法做编程上优化时,快速排序的平均速度比堆排序要快一些。

实际测试结果[编辑]

OS: winxp, Compiler: vc8, CPU:Intel T7200,  Memory: 2G
不同数组长度下调用6种排序1000次所需时间(秒)

length          shell           quick           merge           insert          select          bubble
100             0.0141          0.359           1.875           0.204           0.313           0.421
1000            0.218           0.578           2.204           1.672           2.265           4
5000            1.484           3.25            14.14           41.392          63.656          101.703
10000           3.1             7.8             23.5            253.1           165.6           415.7
50000           21.8            40.6            121.9           411.88          6353.1          11648.5
100000          53.1            89              228.1           16465.7         25381.2         44250


结论:
数组长度不大的情况下不宜使用归并排序,其它排序差别不大。
数组长度很大的情况下Shell最快,Quick其次,冒泡最慢。

简要比较[编辑]

名称 数据对象 稳定性 时间复杂度 空间复杂度 描述
平均 最坏
插入排序 数组、链表 是 O(n^2) O(1) (有序区,无序区)。把无序区的第一个元素插入到有序区的合适的位置。对数组:比较得少,换得多。
直接选择排序 数组 否 O(n^2) O(1) (有序区,无序区)。在无序区里找一个最小的元素跟在有序区的后面。对数组:比较得多,换得少。
链表 是
堆排序 数组 否  O(nlogn) O(1) (最大堆,有序区)。从堆顶把根卸出来放在有序区之前,再恢复堆。
归并排序 数组、链表 是  O(nlogn) O(n) +O(logn) ,如果不是从下到上 把数据分为两段,从两段中逐个选最小的元素移入新数据段的末尾。可从上到下或从下到上进行。
快速排序 数组 否 O(nlogn) O(n^2) O(logn) ,O(n) (小数,枢纽元,大数)。
Accum qsort 链表 是 O(nlogn) O(n^2) O(logn) ,O(n) (无序区,有序区)。把无序区分为(小数,枢纽元,大数),从后到前压入有序区。
决策树排序 是 O(logn!) O(n!) O(n)<O(logn!) <O(nlogn)
计数排序 数组、链表 是 O(n) O(n+m) 统计小于等于该元素值的元素的个数i,于是该元素就放在目标数组的索引i位(i≥0)。
桶排序 数组、链表 是 O(n) O(m) 将值为i的元素放入i号桶,最后依次把桶里的元素倒出来。
基数排序 数组、链表 是 O(k*n),最坏:O(n^2) 一种多关键字的排序算法,可用桶排序实现。
  • 均按从小到大排列
  • k代表数值中的"数位"个数
  • n代表数据规模
  • m代表数据的最大值减最小值

参考文献[编辑]

外部链接[编辑]