排序算法 Sleep Sort

标签: 杂项资源 程序设计 轶事趣闻 Algorithm Sleep | 发表时间:2011-06-23 00:43 | 作者:陈皓 Jeff
出处:http://coolshell.cn

排序算法好像是程序员学习编程最多的算法,也可能是算法研究者们最喜欢研究的算法了。排序有很多很多的算法,比如,冒泡,插入,选择,堆,快速,归并等等(你可以看看本站以前的那些文章:可视化的排序排序算法比较显示排序过程的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));
    }
};

Brainfuck (关于这门语言,请参看这篇文章)

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

(全文完)

相关文章

相关 [排序算法 sleep sort] 推荐:

排序算法 Sleep Sort

- Jeff - 酷壳 - CoolShell.cn
排序算法好像是程序员学习编程最多的算法,也可能是算法研究者们最喜欢研究的算法了. 排序有很多很多的算法,比如,冒泡,插入,选择,堆,快速,归并等等(你可以看看本站以前的那些文章:可视化的排序,排序算法比较,显示排序过程的python)这里向大家介绍一个“巨NB”的排序算法——Sleep Sort. 闲言少说,请看下面的代码(用Shell脚本写的).

wait、sleep、yield区别

- - CSDN博客推荐文章
1、属于Object的本地方法. 2、暂停当前线程,并释放锁. 3、调用notify()或notifyAll()方法唤醒线程. 1、Thread类的静态方法. 2、当前线程休眠,但不释放锁. 3、其他线程可以继续执行,无论该线程优先级高与否. 4、休眠一段时间后,自动执行. 1、Thread类的静态方法.

排序算法

- - 互联网 - ITeye博客
排序算法有很多,所以在特定情景中使用哪一种算法很重要. 为了选择合适的算法,可以按照建议的顺序考虑以下标准: .     对于数据量较小的情形,(1)(2)差别不大,主要考虑(3);而对于数据量大的,(1)为首要.  一、冒泡(Bubble)排序——相邻交换 .  二、选择排序——每次最小/大排在相应的位置 .

“天才”排序算法:Sleepsort

- Sirius - 黑客志
4chan上某位神人发明的天才排序算法:Sleepsort,充分发挥多核威力,评论中还有更多优化版本:. TermKit: 下一代的Mac命令行/终端程序.

SegmentFault问答排序算法

- - 标点符
SegmentFault 参考了 Stack Overflow的热门算法设置了自己的排序算法,具体排序算法如下:. 对于热门文章,使用了如下公式:. views:浏览量,对浏览量做了一次去对数处理,主要是为了防止某些浏览量较大的文章异军突起,待在榜单迟迟不动. recommendScore/collectScore:文章的推荐数和收藏数,直接加和到分子中,作为文章热门程度的考虑因素.

[转]MapReduce:详解Shuffle(copy,sort,merge)过程

- - 芒果先生Mango的专栏
Shuffle过程是MapReduce的核心,也被称为奇迹发生的地方. 要想理解MapReduce, Shuffle是必须要了解的. 我看过很多相关的资料,但每次看完都云里雾里的绕着,很难理清大致的逻辑,反而越搅越混. 前段时间在做MapReduce job 性能调优的工作,需要深入代码研究MapReduce的运行机制,这才对Shuffle探了个究竟.

常用排序算法小结

- - ITeye博客
离开课堂后,排序算法写的比较少了,当有排序的要求时,一般用的比较多的是直接采用Arrays.sort以及Collections.sort结合比较器来实现. Arrays工具类包含了对各种类型数组的排序,以下是Arrays中包括的sort方法:. 以下是 Collections中的sort方法,该sort方法中结合了Arrays.sort来实现的.

Java排序算法:归并排序

- - zzm
 Java排序算法(九):归并排序. 归并排序(Merge)是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的. 然后再把有序子序列合并为整体有序序列. 归 并排序是建立在归并操作上的一种有效的排序算法. 该算法是采用分治法(Divide and Conquer)的一个非常典型的应用.

Java Sleep() 与 Wait()的机制原理与区别

- - CSDN博客推荐文章
Java中的多线程是一种抢占式的机制而不是分时机制. 线程主要有以下几种状态:可运行,运行,阻塞,死亡. 抢占式机制指的是有多个线程处于可运行状态,但是只有一个线程在运行.        当有多个线程访问共享数据的时候,就需要对线程进行同步.        Thread类的方法:sleep(),yield()等.

[转载]java之yield(),sleep(),wait()区别详解

- - 移动开发 - ITeye博客
使当前线程(即调用该方法的线程)暂停执行一段时间,让其他线程有机会继续执行,但它并不释放对象锁. 也就是说如果有synchronized同步快,其他线程仍然不能访问共享数据. 例如有两个线程同时执行(没有synchronized)一个线程优先级为MAX_PRIORITY,另一个为MIN_PRIORITY,如果没有Sleep()方法,只有高优先级的线程执行完毕后,低优先级的线程才能够执行;但是高优先级的线程sleep(500)后,低优先级就有机会执行了.