排序算法好像是程序員學習編程最多的算法，也可能是算法研究者們最喜歡研究的算法瞭。排序有很多很多的算法，比如，冒泡，插入，選擇，堆，快速，歸並等等（你可以看看本站以前的那些文章：可視化的排序，排序算法比較，顯示排序過程的python）這裡向大傢介紹一個“巨NB”的排序算法——Sleep Sort。
閑言少說，請看下面的代碼（用Shell腳本寫的）
1234567891011 #!/bin/bash function f() { sleep “$1” echo “$1”} while [ -n “$1” ] do f “$1” & shiftdonewait
用法如下：
./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（時間可能相當長，不過依然工作）。對於浮點數，看看下面的代碼.
1234567891011 #!/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) & shiftdonewait
3）我們來看看各種語言版本的實現吧。
Java
123456789101112131415161718192021222324252627 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
123456789 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)); } };
Brainfuck (關於這門語言，請參看這篇文章)
,>,>++++++++[<——<——>>-]
<<[>[>+>+<<-]>>[<<+,>,>++++++++[<——<——>>-]
<<[ ———-[++++++++++>———-]++++++++++
>[>+>+<<-]>>[<<+>>-]<<<-] >>>++++++[<++++++++>-]<.>.>>-]<<<-]
,———-[———————-.,———-]
,—<<<+>>>——-[———————-.,———-]
>> ———-[++++++++++>———-]++++++++++
>++++++[<++++++++>-]< ———-[++++++++++>———-]++++++++++
.>. ———-[++++++++++>———-]++++++++++
>++>+<<-]>>[<<+>>-]<<<-] >>[>[>+>+<<-]>>[<<———-[++++++++++>———-]++++++++++
>++,>,>++++++++[<——<——>>-]
<<
（全文完）
