【求解释】排序算法 Sleep Sort

排序算法 Sleep Sort
2011年6月23日陈皓发表评论阅读评论 2,701 次点击   
排序算法好像是程序员学习编程最多的算法，也可能是算法研究者们最喜欢研究的算法了。排序有很多很多的算法，比如，冒泡，插入，选择，堆，快速，归并等等（你可以看看本站以前的那些文章：可视化的排序，排序算法比较，显示排序过程的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));
    }
};


Brainf*** (关于这门语言，请参看这篇文章)

,>,>++++++++[<------<------>>-]
<<[>[>+>+<<-]>>[<<+,>,>++++++++[<------<------>>-]
<<[ ----------[++++++++++>----------]++++++++++
>[>+>+<<-]>>[<<+>>-]<<<-] >>>++++++[<++++++++>-]<.>.>>-]<<<-]
,----------[----------------------.,----------]
,---<<<+>>>-------[----------------------.,----------]
>> ----------[++++++++++>----------]++++++++++
>++++++[<++++++++>-]< ----------[++++++++++>----------]++++++++++
.>. ----------[++++++++++>----------]++++++++++
>++>+<<-]>>[<<+>>-]<<<-] >>[>[>+>+<<-]>>[<<----------[++++++++++>----------]++++++++++
>++,>,>++++++++[<------<------>>-]
<<

（全文完）

额 用了sleep()
小trick 不算nb吧
调用了sleep之后，线程会"休息"一段时间（就是参数指定的），等这段时间过了之后才会重新执行之后的代码。 而且一堆线程是并行执行的，好比一群人在同一起跑线上都睡过去了，谁先醒来谁就赢了。。。

的确如果是一堆特别大的数字，那这个算法得等死了

哈哈。。虽然不实用，但还是挺好玩的。。

哈...这个挺有意思的...让我想起来我的一个脚本了, 用sleep之后明显快了很多, 伪多线程阿, 哈哈.

啊哈哈哈，明白了！
用这种稀奇古怪的语言……伪代码或者C我就懂了的嘛
真好玩…………

这算法无聊啊，有个数字特别大的是不是要等一年啊，再说还有race condition地存在