技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 排序算法 Sleep Sort

排序算法 Sleep Sort

浏览:3157次  出处信息

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

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

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

     <<[ ----------[++++++++++>----------]++++++++++

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

     ,----------[----------------------.,----------]

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

     >> ----------[++++++++++>----------]++++++++++

     >++++++[<++++++++>-]< ----------[++++++++++>----------]++++++++++

     .>. ----------[++++++++++>----------]++++++++++

     >++>+<<-]>>[<<+>>-]<<<-] >>[>[>+>+<<-]>>[<<----------[++++++++++>----------]++++++++++

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

     <<

    (全文完)

建议继续学习:

  1. 如何使用1M的内存排序100万个8位数    (阅读:10901)
  2. 快速排序(Quicksort)的Javascript实现    (阅读:10089)
  3. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读:9042)
  4. 深入浅出插入类排序算法(直接插入, 折半插入, 希尔排序)    (阅读:6188)
  5. 深入浅出交换类排序算法(冒泡排序,快速排序)    (阅读:5986)
  6. Java程序员必知的8大排序算法    (阅读:4458)
  7. Mysql中的排序优化    (阅读:4359)
  8. Vim(gVim)对排序的妙用    (阅读:4221)
  9. 快速排序详细分析    (阅读:3955)
  10. 深入浅出选择类排序算法(简单选择排序,堆排序)    (阅读:3753)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1