標籤：

哪種排序演算法最美？

02-02

覺得快排相當醜陋，不知道為什麼，問下大家，覺得哪種排序演算法最優美

優雅節能的sleep sort

#!/bin/bash
function f() {
sleep "$1"
echo "$1"
}
while [ -n "$1" ]
do
f "$1"
shift
done
wait

微博上看到的。僅做轉發。。。

最漂亮的排序演算法如下：

STOOGE-SORT(a,i,j)

if a[I]&>a[j]

then exchange a[I]&<-&>a[j];

if I+1&>=j

then return

k&<-(j-I+1)/3

STOOGE-SORT(a,i,j-k);

STOOGE-SORT(a,i+k,j);

STOOGE-SORT(a,i,j-k);

這個問題是有辦法回答的，比如可以把演算法可視化一下，並配以音樂。

6分鐘演示15種排序演算法

某種意義上，論美感的話最後的猴子排序（bogosort）默秒全。

快速排序

在所要排序的數字範圍比較小的時候，count sort實現起來非常簡單，還有radix sort 和bucket sort 也是基於counting sort。merge sort演算法複雜度比較穩定。

當然是BOGO排序了！！！

以下是偽代碼：

函數 bogosort(陣列)
當 非 有序(陣列)
陣列 := 隨機排列(陣列)

其平均時間複雜度是 O(n × n!)，在最壞情況所需時間是無限。它並非一個穩定的演算法。

計算機科學家之間的一個笑話說：量子計算機能夠以 O(n) 的複雜度更有效地實現Bogo排序。這將使用真正的量子的隨機性來隨機打亂列表。根據量子物理學的多世界詮釋，量子的隨機性分別在無限的宇宙序列中展開，其中的一些將會提供一個排好序的列表。因為需要重新排列的次數雖然很大但仍然是有限的。這個列表接著就被測試出來（需要n-1次比較）。接著，計算機就應該實施「摧毀宇宙」的操作，使得在剩下的宇宙中的觀察者能夠得到一個排好序的列表。

-----來自wiki百科bogo排序詞條

http://zh.wikipedia.org/wiki/Bogo排序

珠排序...

重力物理實現可以o(sqrt(n))的時間複雜度...

電路硬體實現可以o(n)的時間複雜度...

而且極端簡單明了...

人工排序。。。

radix sort

我反而覺得快排挺優美的，特別是你懂一點資訊理論之後。

這麼有逼格的問題，問的人一定是大牛，要麼是大學生。

就好壞來說，沒有最好的，只有最合適的。說美的話，題主先定義下什麼叫美？難道是穩定性？時間複雜度？還是空間複雜度？還是名字？

滿足一定條件的數組4次for循環即可完成排序，思路是利用下標完成，具體演算法忘了。。。

一會找到了就補上。

並行的 M/B 路歸併 (M為整個緩存的大小，B為緩存塊大小)

或者並行的 funnel sort 吧

我就知道這麼點，再酷炫的就不知道怎麼整了。

題主，必須是初學者。至少於排序問題是。

數據量大了以後，速度快才是硬道理。

從這個角度說，快速排序，是內排序中最美的。

數據量再多。要用外排序。那麼：

如果，記錄長為四位元組，最美的：快速內排序+堆式K路歸併排序。

如果，記錄長度大於四位元組。最美的則是：快速間接內排序+堆式間接K路歸併排序。

論描述的優美簡潔，一般都可以看到遞歸的身影，所以我覺得 Mergesort 算是描述上看起來比較美的：

On input of n elements:
if n &< 2 return else sort left half of elements sort right half of elements merge sorted halves

推薦閱讀：

TAG:演算法 | 演算法設計 | 排序演算法 |