排序算法

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

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

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

[编辑] 分類

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

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

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

(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²)
• 鸡尾酒排序 (Cocktail sort, 雙向的冒泡排序) — O(n²)
• 插入排序 （insertion sort）— O(n²)
• 桶排序 （bucket sort）— O(n); 需要 O(k) 額外 記憶體
• 计数排序 (counting sort) — O(n+k); 需要 O(n+k) 額外 記憶體
• 歸併排序 （merge sort）— O(n log n); 需要 O(n) 額外記憶體
• 原地歸併排序 — O(n²)
• 二叉树排序 （Binary tree sort） — O(n log n); 需要 O(n) 額外記憶體
• 鸽巢排序 (Pigeonhole sort) — O(n+k); 需要 O(k) 額外記憶體
• 基數排序 （radix sort）— O(n·k); 需要 O(n) 額外記憶體
• Gnome sort — O(n²)
• Library sort — O(n log n) with high probability, 需要 (1+ε)n 額外記憶體

[编辑] 不穩定

• 選擇排序 （selection sort）— O(n²)
• 希爾排序 （shell sort）— O(n log n) 如果使用最佳的現在版本
• Comb sort — O(n log n)
• 堆排序 （heapsort）— O(n log n)
• Smoothsort — O(n log n)
• 快速排序 （quicksort）— O(n log n) 期望時間, O(n²) 最壞情況; 對於大的、亂數串列一般相信是最快的已知排序
• Introsort — O(n log n)
• Patience sorting — O(n log n + k) 最坏情況時間, 需要 額外的 O(n + k) 空間, 也需要找到最長的遞增子序列（longest increasing subsequence）

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

• Bogo排序 — O(n × n!) 期望時間, 無窮的最壞情況。
• Stupid sort — O(n³); 遞迴版本需要 O(n²) 額外記憶體
• Bead sort — O(n) or O(√n), 但需要特別的硬體
• Pancake sorting — O(n), 但需要特別的硬體

[编辑] 排序的算法

排序的算法有很多，对空间的要求及其时间效率也不尽相同。下面列出了一些常见的排序算法。这里面插入排序和冒泡排序又被称作简单排序，他们对空间的要求不高，但是时间效率却不稳定；而后面三种排序相对于简单排序对空间的要求稍高一点，但时间效率却能稳定在很高的水平。基数排序是针对关键字在一个较小范围内的排序算法。

• 插入排序
• 冒泡排序
• 选择排序
• 快速排序
• 堆排序
• 归并排序
• 基数排序
• 希尔排序

[编辑] 插入排序

插入排序是这样实现的：

1. 首先新建一个空列表，用于保存已排序的有序数列（我们称之为"有序列表"）。
2. 从原数列中取出一个数，将其插入"有序列表"中，使其仍旧保持有序状态。
3. 重复2号步骤，直至原数列为空。

插入排序的平均时间复杂度为平方级的，效率不高，但是容易实现。 它借助了"逐步扩大成果"的思想，使有序列表的长度逐渐增加，直至其长度等于原列表的长度。

[编辑] 冒泡排序

冒泡排序是这样实现的：

1. 首先将所有待排序的数字放入工作列表中。
2. 从列表的第一个数字到倒数第二个数字，逐个检查：若某一位上的数字大于他的下一位，则将它与它的下一位交换。
3. 重复2号步骤，直至再也不能交换。

冒泡排序的平均时间复杂度与插入排序相同，也是平方级的，但也是非常容易实现的算法。

[编辑] 选择排序

选择排序是这样实现的：

1. 设数组内存放了n个待排数字，数组下标从1开始，到n结束。
2. i=1
3. 从数组的第i个元素开始到第n个元素，寻找最小的元素。
4. 将上一步找到的最小元素和第i位元素交换。
5. 如果i=n－1算法结束，否则回到第3步

选择排序的平均时间复杂度也是O(n²)的。

[编辑] 快速排序

现在开始，我们要接触高效排序算法了。实践证明，快速排序是所有排序算法中最高效的一种。它采用了分治的思想：先保证列表的前半部分都小于后半部分，然后分别对前半部分和后半部分排序，这样整个列表就有序了。这是一种先进的思想，也是它高效的原因。因为在排序算法中，算法的高效与否与列表中数字间的比较次数有直接的关系，而"保证列表的前半部分都小于后半部分"就使得前半部分的任何一个数从此以后都不再跟后半部分的数进行比较了，大大减少了数字间不必要的比较。但查找数据得另当别论了。

[编辑] 堆排序

堆排序与前面的算法都不同，它是这样的：

1. 首先新建一个空列表，作用与插入排序中的"有序列表"相同。
2. 找到数列中最大的数字，将其加在"有序列表"的末尾，并将其从原数列中删除。
3. 重复2号步骤，直至原数列为空。

堆排序的平均时间复杂度为nlogn,效率高（因为有堆这种数据结构以及它奇妙的特征，使得"找到数列中最大的数字"这样的操作只需要O(1)的时间复杂度，维护需要logn的时间复杂度），但是实现相对复杂（可以说是这里7种算法中比较难实现的）。

看起来似乎堆排序与插入排序有些相像，但他们其实是本质不同的算法。至少，他们的时间复杂度差了一个数量级，一个是平方级的，一个是对数级的。

[编辑] 平均时间复杂度

• 插入排序 O(n²)
• 冒泡排序 O(n²)
• 选择排序 O(n²)
• 快速排序 O(n log n)
• 堆排序 O(n log n)
• 归并排序 O(n log n)
• 基数排序 O(n)
• 希尔排序 O(n^1.25)