关闭菜单
四少爷的blog
by Jermey
V 1.0
打开菜单

排序算法--睡眠排序、面条排序、猴子排序 (非常严肃)

输入:n个待排序的数组成的数组。 输出:按顺序从小到大排列好的数组。

睡眠排序(Sleep Sort)

构造n个线程,它们和这n个数一一对应。 初始化后,线程们开始睡眠,等到对应的数那么多个时间单位后各自醒来,然后输出它对应的数。 这样最小的数对应的线程最早醒来,这个数最早被输出。 等所有线程都醒来,排序就结束了。能脑洞大开想出此算法的,绝壁天才啊。。。

于是我一本正经地试着实现一下这个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] 当线程不太多的时候,基本可以认为它们是同时启动的。

[2] 主线程睡眠足够长时间,等所有Sleeper线程都执行完毕。可以把时间设成比最大输入稍大。

上面的代码很粗略,很多八阿哥啦。比如(1) 搞不定负数 (2)比如输入数据很相近时会有误差 (3)输入数据很多时,这些线程不能看作是同时启动等等…对于(1),可以用一个在恒正的函数把输入映射成时间;(2),可以乘个系数,放大数据间的差,但是依然搞不定重复的数据;(3),试着让算法在多个物理核上真正的并行起来?

面条排序(Spaghetti Sort, 意面排序)

首先去买一捆面,是意面挂面还是手擀面请按个人口味决定,最好是硬的。 找到数组中最大和最小的两个数(O(n)),让最大的数对应一根很长的面条,最小的数对应一根很短的面条。 重新遍历数组,每遇到一个数,就取一根面条,把它切成这个数对应的长度,可以得到n根面条。 这里的数与面条长度的对应可以用一个严格递增的函数来映射。 接下来,一手握住这n根面条,稍微用力,别握太紧,在平放的桌面上直立着放下,让所有的面条底端接触到桌面。 另一只手平行于桌面,从面条上方缓慢往下移动,每当这只手碰到一根面条,移走它,并把对应的数输出到结果数组中,直到移走全部面条。

用完的面条还可以煮夜宵哦。

面条排序的思想基本上跟睡眠排序一样样的,代码不造咋写…

猴子排序(Bogo Sort)

随机打乱数组,检查是否排好序,若是,则输出,否则再次打乱,再检查…最佳情况O(n),平均O(n*n!),最坏可执行直到世界的尽头。

算法代码主体部分基本上就是这样的:

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

See also 无限猴子定理 :一只猴子随机敲打打字机键盘,如果时间足够长,总是能打出特定的文本,比如莎士比亚全集。