本頁使用了標題或全文手工轉換

排序演算法

維基百科,自由的百科全書
(已重新導向自 排序)
前往: 導覽搜尋

計算機科學數學中,一個排序演算法(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是不同鍵值的數量。

穩定的排序[編輯]

不穩定的排序[編輯]

不實用的排序[編輯]

平均時間複雜度[編輯]

平均時間複雜度由高到低為:

說明:雖然完全逆序的情況下,快速排序會降到選擇排序的速度,不過從機率角度來說(參考資訊學理論,和機率學),不對演算法做編程上最佳化時,快速排序的平均速度比堆排序要快一些。

簡要比較[編輯]

名稱 資料物件 穩定性 時間複雜度 空間複雜度 描述
平均 最壞
氣泡排序 陣列 O(n^2) O(1) (無序區,有序區)。從無序區透過交換找出最大元素放到有序區前端。
選擇排序 陣列 O(n^2) O(1) (有序區,無序區)。在無序區里找一個最小的元素跟在有序區的後面。對陣列:比較得多,換得少。
連結串列
插入排序 陣列、連結串列 O(n^2) O(1) (有序區,無序區)。把無序區的第一個元素插入到有序區的合適的位置。對陣列:比較得少,換得多。
堆排序 陣列  O(n\log n) O(1) (最大堆,有序區)。從堆頂把根卸出來放在有序區之前,再恢復堆。
合併排序 陣列  O(n\log n) O(n) +O(\log n) ,如果不是從下到上 把資料分為兩段,從兩段中逐個選最小的元素移入新資料段的末尾。可從上到下或從下到上進行。
連結串列  O(1)
快速排序 陣列 O(n\log n) O(n^2) O(\log n) ,O(n) (小數,樞紐元,大數)。
希爾排序 陣列 O(n\log^2n) O(n^2) O(1) 每一輪按照事先決定的間隔進行插入排序,間隔會依次縮小,最後一次一定要是1。
計數排序 陣列、連結串列 O(n) O(n+m) 統計小於等於該元素值的元素的個數i,於是該元素就放在目標陣列的索引i位(i≥0)。
桶排序 陣列、連結串列 O(n) O(m) 將值為i的元素放入i號桶,最後依次把桶里的元素倒出來。
基數排序 陣列、連結串列 O(k\times n) O(n^2) 一種多關鍵字的排序演算法,可用桶排序實作。
  • 均按從小到大排列
  • k代表數值中的"數位"個數
  • n代表資料規模
  • m代表資料的最大值減最小值

參考文獻[編輯]

外部連結[編輯]