排序算法 Sleep Sort 多線程、多進程排序啊

排序算法好像是程序員學習編程最多的算法，也可能是算法研究者們最喜歡研究的算法了。排序有很多很多的算法，比如，冒泡，插入，選擇，堆，快速，歸并等等（你可以看看本站以前的那些文章：可視化的排序，排序算法比較，顯示排序過程的python）這里向大家介紹一個“巨NB”的排序算法——Sleep Sort。

閑言少說，請看下面的代碼（用Shell腳本寫的）

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

用法如下：

./sleepsort.bash 5 3 6 3 6 3 1 4 7

相信你可以會去試一下這個腳本，也相你你試完后你一定會說——“我擦，真TMD排序了！”，我還是不要解釋這段代碼了，過多的解釋會不如代碼那么直接，而且解釋會影響你對這個排序算法的NB性。只想說——這是正二八經的多線程、多進程排序啊。我們的Bogo排序也黯然失色啊。

下面我們需要對這個算法做一些分析——

1）讓我們來分析一個這這個程序的算法復雜度，太簡單了，不就是O(最大數的秒數)，呵呵。所以，如果出現這樣的數列將是惡夢的——2 1 4 3 2 1 99999999

2）這個排序好是好，但對于負數或浮點數就有bug了。負數的解決方案是，我們可以這樣來：x/2+MaxInt/2（時間可能相當長，不過依然工作）。對于浮點數，看看下面的代碼.

 #!/bin/bash
function f() {
sleep $(echo "($2 - 1) + $1 / 10 ^ $2" | bc -l)
echo "$1"
}
while [ -n "$1" ]
do
f "$1" $(echo -n "$1" | wc -c) &
shift
done
wait

3）我們來看看各種語言版本的實現吧。
Java

 public class SleepSort { 
public static void main(String[] args) { 
int[] ints = {1,4,7,3,8,9,2,6,5}; 
SortThread[] sortThreads = new SortThread[ints.length]; 
for (int i = 0; i < sortThreads.length; i++) { 
sortThreads[i] = new SortThread(ints[i]); 
} 
for (int i = 0; i < sortThreads.length; i++) { 
sortThreads[i].start(); 
} 
} 
} 
class SortThread extends Thread{ 
int ms = 0; 
public SortThread(int ms){ 
this.ms = ms; 
} 
public void run(){ 
try { 
sleep(ms*10+10); 
} catch (InterruptedException e) { 
// TODO Auto-generated catch block 
e.printStackTrace(); 
} 
System.out.println(ms); 
} 
} 

Javascript

function sleepsort() { 
for (var i = 0, il = arguments.length; i < il; i++) { 
(function(args, index) { 
setTimeout(function() { 
document.body.innerHTML += args[index] + ', '; 
}, args[index]); 
}(arguments, i)); 
} 
}; 

類似這樣的文章,很有意思,包括評論哦.
http://coolshell.cn/articles/4883.html