在計算機科學與數學中，一個排序算法（）是一種能將一串資料依照特定排序方式排列的算法，排序後的資料即可放在有序陣列。最常用到的排序方式是數值順序以及字典順序。有效的排序算法在一些算法（例如搜尋算法與）中是重要的，如此這些算法才能得到正確解答。排序算法也用在處理文字資料以及產生人類可讀的輸出結果。基本上，排序算法的輸出必須遵守下列兩個原則：
輸出結果為遞增序列（遞增是針對所需的排序順序而言）
輸出結果是原輸入的一種排列、或是重組
雖然排序算法是一個簡單的問題，但是從計算機科學發展以來，在此問題上已經有大量的研究。舉例而言，泡沫排序在1956年就已經被研究。雖然大部分人認為這是一個已經被解決的問題，有用的新算法仍在不斷的被發明。（例子：圖書館排序在2004年被發表）
分類
在计算机科学所使用的排序算法通常依以下標準分類：
- 計算的時間複雜度（最差、平均、和最好-{zh-cn:性能; zh-tw:表現;}-），依據串列（list）的大小(n)。一般而言，好的-{zh-cn:性能; zh-tw:表現;}-是O(n\log n)（大O符号），壞的-{zh-cn:性能; zh-tw:表現;}-是O(n^2)。對於基於比較的排序，存在 \Omega(n\log n)的下界；而在鍵值範圍受限等條件下，非比較排序可達到線性時間。基於比較的排序算法對大多數輸入而言至少需要O(n\log n)。
- -{zh-cn:内存; zh-tw:記憶體;}-使用量（以及其他電腦資源的使用）
- 穩定性：穩定排序算法會讓原本有相等鍵值的紀錄維持相對次序。也就是如果一個排序算法是穩定的，當有兩個相等鍵值的紀錄R和S，且在原本的串列中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是不同鍵值的數量。
穩定的排序
- 冒泡排序（bubble sort）— O(n^2)
- 插入排序（insertion sort）—O(n^2)
- 鸡尾酒排序（cocktail sort）—O(n^2)
- 桶排序（bucket sort）—O(n)；需要O(k)額外空間
- 计数排序（counting sort）—O(n+k)；需要O(n+k)額外空間
- 归并排序（merge sort）—O(n\log n)；需要O(n)額外空間
- 原地归并排序— O(n\log^2 n)如果使用最佳的現在版本
- 二叉排序树排序（binary tree sort）— O(n\log n)期望时间；O(n^2)最坏时间；需要O(n)額外空間
- 鸽巢排序（pigeonhole sort）—O(n+k)；需要O(k)額外空間
- 基數排序（radix sort）—O(nk)；需要O(n)額外空間
- 侏儒排序（gnome sort）— O(n^2)
- 圖書館排序（library sort）— O(n\log n)期望时间；O(n^2)最坏时间；需要(1+\varepsilon)n額外空間
- （block sort）— O(n\log n)
- Tim排序（Timsort）—O(n\log n)平均、最坏时间；O(n)最优时间；需要O(n)額外空間；是目前已知最快的排序算法，在Python、Swift、Rust等语言的内置排序功能中被用作默认算法
不穩定的排序
- 選擇排序（selection sort）—O(n^2)
- 希爾排序（shell sort）—O(n\log^2 n)如果使用最佳的現在版本
- 克洛弗排序（Clover sort）—O(n)期望时间，O(n^2)最坏情况
- 梳排序— O(n\log n)
- 堆排序（heap sort）—O(n\log n)
- （smooth sort）— O(n\log n)
- 快速排序（quick sort）—O(n\log n)期望時間，O(n^2)最壞情況
- 內省排序（introsort）—O(n\log n)
- 耐心排序（patience sort）—O(n\log n+k)最坏情況時間，需要額外的O(n+k)空間，也需要找到最長的遞增子序列（longest increasing subsequence）
不實用的排序
- Bogo排序— O(n \times n!)，最壞的情況下期望時間為無窮。
- Stupid排序—O(n^3);遞迴版本需要O(n^2)額外記憶體
- 珠排序（bead sort）— O(n) 或 O(\sqrt{n}),但需要特別的硬體
- 煎餅排序—O(n),但需要特別的硬體
- 臭皮匠排序（stooge sort）算法简单，但需要约n^{2.7}的时间
简要比较
- 均按从小到大排列
- k代表数值中的"数位"个数
- n代表数据规模
- m代表数据的最大值减最小值
参考文献
外部链接
评论 (0)