輸入：n個(gè)待排序的數(shù)組成的數(shù)組。
輸出：按順序從小到大排列好的數(shù)組。

1. 睡眠排序（Sleep Sort）

構(gòu)造n個(gè)線程，它們和這n個(gè)數(shù)一一對(duì)應(yīng)。初始化后，線程們開(kāi)始睡眠，等到對(duì)應(yīng)的數(shù)那么多個(gè)時(shí)間單位后各自醒來(lái)，然后輸出它對(duì)應(yīng)的數(shù)。這樣最小的數(shù)對(duì)應(yīng)的線程最早醒來(lái)，這個(gè)數(shù)最早被輸出。等所有線程都醒來(lái)，排序就結(jié)束了。能腦洞大開(kāi)想出此算法的，絕壁天才啊。。。
于是我一本正經(jīng)地試著實(shí)現(xiàn)一下這個(gè)Idea:

public class SleepSort {
    public static void main(String[] args){
        int[] nums={9,7,2,6,15,8,9,9,9,9,9};
        SleepSort.sort(nums);
        for(int n:nums)
            System.out.printf("%d   ",n);
    }
    
    public static void sort(int[] nums){
        Sleeper.idx=0;
        Sleeper.output=new int[nums.length];
        for(int i=0;i<nums.length;i++)        //[1]
            new Sleeper(nums[i]).start();
        
        try {
            Thread.sleep(100);                //[2]
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        for(int i=0;i<nums.length;i++)
            nums[i]=Sleeper.output[i];
    }
}

class Sleeper extends Thread{
    public static int[] output;
    public static int idx;
    
    private int sleep_time;

    public Sleeper(){
        this.sleep_time=0;
    }
    public Sleeper(int sleep_time){
        this.sleep_time=sleep_time;
    }
    @Override
    public void run(){
        try{
            Thread.sleep(this.sleep_time);
        }catch(InterruptedException e){
            e.printStackTrace();
        }
        output[idx++]=this.sleep_time;
    }
}

注釋：
[1] 當(dāng)線程不太多的時(shí)候，基本可以認(rèn)為它們是同時(shí)啟動(dòng)的。
[2] 主線程睡眠足夠長(zhǎng)時(shí)間，等所有Sleeper線程都執(zhí)行完畢?？梢园褧r(shí)間設(shè)成比最大輸入稍大。
上面的代碼很粗略，很多八阿哥啦。比如(1) 搞不定負(fù)數(shù) (2)比如輸入數(shù)據(jù)很相近時(shí)會(huì)有誤差 (3)輸入數(shù)據(jù)很多時(shí)，這些線程不能看作是同時(shí)啟動(dòng)等等...對(duì)于(1)，可以用一個(gè)在恒正的函數(shù)把輸入映射成時(shí)間；(2)，可以乘個(gè)系數(shù)，放大數(shù)據(jù)間的差，但是依然搞不定重復(fù)的數(shù)據(jù)；(3)，試著讓算法在多個(gè)物理核上真正的并行起來(lái)？

2. 面條排序(Spaghetti Sort, 意面排序)

首先去買一捆面，是意面掛面還是手搟面請(qǐng)按個(gè)人口味決定，最好是硬的。找到數(shù)組中最大和最小的兩個(gè)數(shù)(O(n))，讓最大的數(shù)對(duì)應(yīng)一根很長(zhǎng)的面條，最小的數(shù)對(duì)應(yīng)一根很短的面條。重新遍歷數(shù)組，每遇到一個(gè)數(shù)，就取一根面條，把它切成這個(gè)數(shù)對(duì)應(yīng)的長(zhǎng)度，可以得到n根面條。這里的數(shù)與面條長(zhǎng)度的對(duì)應(yīng)可以用一個(gè)嚴(yán)格遞增的函數(shù)來(lái)映射。接下來(lái)，一手握住這n根面條，稍微用力，別握太緊，在平放的桌面上直立著放下，讓所有的面條底端接觸到桌面。另一只手平行于桌面，從面條上方緩慢往下移動(dòng)，每當(dāng)這只手碰到一根面條，移走它，并把對(duì)應(yīng)的數(shù)輸出到結(jié)果數(shù)組中，直到移走全部面條。
用完的面條還可以煮夜宵哦。
面條排序的思想基本上跟睡眠排序一樣樣的，代碼不造咋寫...

3. 猴子排序（Bogo Sort）

隨機(jī)打亂數(shù)組，檢查是否排好序，若是，則輸出，否則再次打亂，再檢查...最佳情況O(n)，平均O(n*n!)，最壞可執(zhí)行直到世界的盡頭。
算法代碼主體部分基本上就是這樣的：

while(! isOrdered(nums))
    shuffle(nums);

See also 無(wú)限猴子定理 ：一只猴子隨機(jī)敲打打字機(jī)鍵盤，如果時(shí)間足夠長(zhǎng)，總是能打出特定的文本，比如莎士比亞全集。

本文遵守知識(shí)共享協(xié)議：署名-非商業(yè)性使用-相同方式共享 (BY-NC-SA)及簡(jiǎn)書協(xié)議轉(zhuǎn)載請(qǐng)注明：作者曾會(huì)玩