排序算法:計算機語言的邏輯基礎-中文百科頻道

概述

所謂排序，就是使一串記錄，按照其中的某個或某些關鍵字的大小，遞增或遞減的排列起來的操作。

計算的複雜度（最差、平均、和最好表現），依據串列（list）的大小（n）。一般而言，好的表現是O。(n log n)，且壞的行為是Ω(n2)。對於一個排序理想的表現是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(n2)

雞尾酒排序(Cocktail sort,雙向的冒泡排序)—O(n2)

插入排序（insertion sort）—O(n2)

桶排序（bucket sort）—O(n);需要O(k)額外記憶體

計數排序(counting sort)—O(n+k);需要O(n+k)額外記憶體

歸併排序（merge sort）—O(n log n);需要O(n)額外記憶體

原地歸併排序—O(n2)

二叉樹排序（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(n2)

Library sort—O(n log n) with high probability,需要(1+ε)n額外記憶體

不穩定

選擇排序（selection sort）—O(n2)

希爾排序（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(n2)最壞情況;對於大的、亂數串列一般相信是最快的已知排序

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(n3);遞迴版本需要O(n2)額外記憶體

Bead sort—O(n) or O(√n),但需要特别的硬體

Pancake sorting—O(n),但需要特别的硬體

排序的算法

排序的算法有很多，對空間的要求及其時間效率也不盡相同。下面列出了一些常見的排序算法。這裡面插入排序和冒泡排序又被稱作簡單排序，他們對空間的要求不高，但是時間效率卻不穩定；而後面三種排序相對于簡單排序對空間的要求稍高一點，但時間效率卻能穩定在很高的水平。基數排序是針對關鍵字在一個較小範圍内的排序算法。

插入排序

冒泡排序

選擇排序

快速排序

堆排序

歸并排序

基數排序

希爾排序

桶排序

插入排序

插入排序是這樣實現的：

首先新建一個空列表，用于保存已排序的有序數列（我們稱之為"有序列表"）。

從原數列中取出一個數，将其插入"有序列表"中，使其仍舊保持有序狀态。

重複2号步驟，直至原數列為空。

插入排序的平均時間複雜度為平方級的，效率不高，但是容易實現。它借助了"逐步擴大成果"的思想，使有序列表的長度逐漸增加，直至其長度等于原列表的長度。

冒泡排序

冒泡排序是這樣實現的：

首先将所有待排序的數字放入工作列表中。

從列表的第一個數字到倒數第二個數字，逐個檢查：若某一位上的數字大于他的下一位，則将它與它的下一位交換。

重複2号步驟，直至再也不能交換。

冒泡排序的平均時間複雜度與插入排序相同，也是平方級的，但也是非常容易實現的算法。

選擇排序

選擇排序是這樣實現的：

設數組内存放了n個待排數字，數組下标從1開始，到n結束。

i=1

從數組的第i個元素開始到第n個元素，尋找最小的元素。

将上一步找到的最小元素和第i位元素交換。

如果i=n－1算法結束，否則回到第3步

選擇排序的平均時間複雜度也是O(n²)的。

快速排序

現在開始，我們要接觸高效排序算法了。實踐證明，快速排序是所有排序算法中最高效的一種。它采用了分治的思想：先保證列表的前半部分都小于後半部分，然後分别對前半部分和後半部分排序，這樣整個列表就有序了。這是一種先進的思想，也是它高效的原因。因為在排序算法中，算法的高效與否與列表中數字間的比較次數有直接的關系，而"保證列表的前半部分都小于後半部分"就使得前半部分的任何一個數從此以後都不再跟後半部分的數進行比較了，大大減少了數字間不必要的比較。但查找數據得另當别論了。