V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Sponsored by
LinkedIn
不坐班的神仙工作 · 去任何你想去的地方远程,赚一线城市的工资
2000 个不用出门 Social 的全球远程工作,帮助 V2EX 的小伙伴开启全新的工作方式。
Promoted by LinkedIn
a1310747
V2EX  ›  程序员

今天看到一个新的排序法 睡排序 真的是脑洞大开。。。

  •  3
     
  •   a1310747 · 2017-03-02 15:24:21 +08:00 · 21291 次点击
    这是一个创建于 2035 天前的主题,其中的信息可能已经有所发展或是发生改变。

    估计有大部分人不知道把,原理是构造 n 个线程,它们和这 n 个数一一对应。初始化后,线程们开始睡眠,等到对应的数那么多个时间单位后各自醒来,然后输出它对应的数。这样最小的数对应的线程最早醒来,这个数最早被输出。等所有线程都醒来,排序就结束了。 放个例子:

    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;
        }
    }
    
    107 条回复    2018-12-12 23:29:44 +08:00
    1  2  
    bp0
        1
    bp0  
       2017-03-02 15:27:02 +08:00 via Android
    会不会睡一辈子,(手动斜眼
    awolfer
        2
    awolfer  
       2017-03-02 15:27:52 +08:00
    线程开销很大吧, 这个太不划算了
    a1310747
        3
    a1310747  
    OP
       2017-03-02 15:28:01 +08:00
    @bp0 哈哈哈哈 你这么一说还真有可能...
    easyzhao
        4
    easyzhao  
       2017-03-02 15:28:34 +08:00
    跟存数据库里 select order 一下有什么区别
    a1310747
        5
    a1310747  
    OP
       2017-03-02 15:28:34 +08:00
    @awolfer 但是你不能否定这也是一种排序法 反正让我想我是想不出来
    langmoe
        6
    langmoe  
       2017-03-02 15:30:21 +08:00
    其实还是相当于桶吧
    jasonlz
        7
    jasonlz  
       2017-03-02 15:35:52 +08:00
    怎么保证所有线程同时开始运行?
    wmhx
        8
    wmhx  
       2017-03-02 15:38:08 +08:00
    coolshell.cn 看排序的时候就见过的, 听说这是复杂度最低的排序了, 没有之一.
    xjtlujoe
        9
    xjtlujoe  
       2017-03-02 15:44:12 +08:00
    这思路不错
    a1310747
        10
    a1310747  
    OP
       2017-03-02 15:47:48 +08:00
    @wmhx O(n)的时间复杂度的确是最低的....
    knightdf
        11
    knightdf  
       2017-03-02 15:49:21 +08:00   ❤️ 1
    时间复杂度在这个排序上已经毫无意义,哈哈哈
    nbndco
        12
    nbndco  
       2017-03-02 15:53:48 +08:00   ❤️ 3
    这个方法显然不是 O(n)的, event loop 的调用过程显然还是要排序了,不然每次遍历变 n^2 了。
    如果这个是 O(n),那么 sort(int *arr, int len)应该算是 O(1)的了。
    qdwang
        13
    qdwang  
       2017-03-02 15:54:46 +08:00
    @langmoe 没错
    linboki
        14
    linboki  
       2017-03-02 15:55:32 +08:00 via Android
    大概本质就是是带阻塞的堆排序。
    linboki
        15
    linboki  
       2017-03-02 15:56:30 +08:00 via Android
    因为内核的定时器普遍用小根堆实现
    dreasky
        16
    dreasky  
       2017-03-02 15:57:47 +08:00
    请比较 1 和 10000000000000000000
    AsherG
        17
    AsherG  
       2017-03-02 15:58:01 +08:00
    哈哈哈,莫名感觉好萌
    wellsc
        18
    wellsc  
       2017-03-02 16:00:21 +08:00
    又是一道面试题
    a1310747
        19
    a1310747  
    OP
       2017-03-02 16:01:16 +08:00
    @AsherG 对啊 哈哈哈 这个排序法还被称为天才排序法
    a1310747
        20
    a1310747  
    OP
       2017-03-02 16:01:24 +08:00
    @dreasky 我选择死亡
    a1310747
        21
    a1310747  
    OP
       2017-03-02 16:01:38 +08:00
    @wellsc 这个不是面试了喂!
    xielemon
        22
    xielemon  
       2017-03-02 16:05:23 +08:00
    @jasonlz countdownlatch cylicbarrier
    coderluan
        23
    coderluan  
       2017-03-02 16:06:24 +08:00   ❤️ 1
    不扩展的话,排个负数就得开时光机了吧。
    4ever911
        24
    4ever911  
       2017-03-02 16:07:24 +08:00
    哈哈,果然是开脑洞。
    kindjeff
        25
    kindjeff  
       2017-03-02 16:10:39 +08:00 via iPhone   ❤️ 1
    IJustmaogepao
        26
    IJustmaogepao  
       2017-03-02 16:15:32 +08:00
    @coderluan 23333
    noNOno
        27
    noNOno  
       2017-03-02 16:17:19 +08:00
    炫酷,没毛病
    sorcerer
        28
    sorcerer  
       2017-03-02 16:18:48 +08:00 via iPhone
    厉害 脑洞大开
    loryyang
        29
    loryyang  
       2017-03-02 16:19:43 +08:00
    恩,挺有意思的啊,开了脑洞
    dreamcountry
        30
    dreamcountry  
       2017-03-02 16:21:40 +08:00
    是一种方法,但效率不高
    ibufu
        31
    ibufu  
       2017-03-02 16:26:19 +08:00
    这个在 js 里可以用 setTimeout 了
    ```
    function sort(nums) {
    for (let i = 0; i < nums.length; i++) {
    setTimeout(() => {
    console.log(nums[i]);
    }, nums[i]);
    }
    }
    ```
    Crossin
        32
    Crossin  
       2017-03-02 16:28:55 +08:00
    求 真·时间复杂度
    noNOno
        33
    noNOno  
       2017-03-02 16:31:31 +08:00
    精确度最多到毫秒,就算数字作为毫秒值转成时间,仍旧无法进行相差太大的数字排序。.......
    vingz
        34
    vingz  
       2017-03-02 16:32:19 +08:00
    时间,要等超时后,黄花菜都凉了
    CFMY
        35
    CFMY  
       2017-03-02 16:37:08 +08:00   ❤️ 1
    线程挂机后的唤醒顺序取决 cpu
    这个方法在 cpu 忙碌情况下很可能给出错误结果
    我觉得算不上一个排序
    Phariel
        36
    Phariel  
       2017-03-02 16:40:58 +08:00 via Android
    这,睡眠再唤醒就跟精确 setTimeout 一样不靠谱,中间万一有一环阻塞了一下就全盘完蛋。。。
    pythonee
        37
    pythonee  
       2017-03-02 16:42:06 +08:00
    这个有点意思
    rocksolid
        38
    rocksolid  
       2017-03-02 16:53:03 +08:00
    本质还是计数排序,不过蛮好玩的
    a1310747
        39
    a1310747  
    OP
       2017-03-02 16:54:38 +08:00
    @rocksolid 是的 今天突然看到 把我震到了
    neosfung
        40
    neosfung  
       2017-03-02 17:16:37 +08:00
    贡献一个猴子排序吧。。。
    https://zh.wikipedia.org/wiki/Bogo%E6%8E%92%E5%BA%8F
    mnzlichunyu
        41
    mnzlichunyu  
       2017-03-02 17:19:25 +08:00
    haha, 非常诙谐
    zwzmzd
        42
    zwzmzd  
       2017-03-02 17:24:25 +08:00 via Android
    这相当于把排序工作交给操作系统了吧
    licraft
        43
    licraft  
       2017-03-02 17:25:43 +08:00
    感觉和桶排序原理一样吧。。。占空间
    mozutaba
        44
    mozutaba  
       2017-03-02 17:30:19 +08:00
    桶排序
    wellsc
        45
    wellsc  
       2017-03-02 17:33:23 +08:00
    @a1310747 可以拿这题来面试对创建线程的掌握度
    oldj
        46
    oldj  
       2017-03-02 17:43:25 +08:00   ❤️ 7
    还有一种「 twitter 排序」(也可以换成「微博排序」、「朋友圈排序」),原理是调用 API 把要排序的数字发到 twitter 上,请好友帮忙排序,每当有人回复时,检查回复内容是否正确,如果是则输出,否则继续等待。
    weyou
        47
    weyou  
       2017-03-02 17:48:22 +08:00
    利用时间的有序单向性,将数值转化成等待时间。只是一个小技巧,但没有实际意义。
    1. 不能对大量的数据排序,起线程都占用了时间了。
    2. 数值之间不能相差太大

    由这个脑洞,突然想到一个利用空间的排序:
    >>>numbers = [234,425,56,654]
    workspace = [None] * 1024 # must be greater then maximum value
    for i in numbers:
    workspace[i] = i
    >>>print([i for i in workspace if i is not None])
    aleen42
        48
    aleen42  
       2017-03-02 18:28:35 +08:00
    不忍直视,这线程得占用多少效率。线程通信也需要时间的吧,不划算。
    cy18
        49
    cy18  
       2017-03-02 18:35:04 +08:00
    @weyou 这基本上就是桶排序- -
    wy315700
        50
    wy315700  
       2017-03-02 18:39:26 +08:00
    这不就是珠排序
    tideline
        51
    tideline  
       2017-03-02 18:40:07 +08:00   ❤️ 1
    guokeke
        52
    guokeke  
       2017-03-02 18:40:09 +08:00
    @oldj 笑死了。
    xcatliu
        53
    xcatliu  
       2017-03-02 19:05:33 +08:00
    计算机科学家之间的一个笑话说:量子计算机能够以 O(n) 的复杂度更有效地实现 Bogo 排序。这将使用真正的量子的随机性来随机打乱列表。根据量子物理学的多世界诠释,量子的随机性分别在无限的宇宙序列中展开,其中的一些将会提供一个排好序的列表。因为需要重新排列的次数虽然很大但仍然是有限的。这个列表接着就被测试出来(需要 n-1 次比较)。接着,计算机就应该实施“摧毁宇宙”的操作,使得在剩下的宇宙中的观察者能够得到一个排好序的列表。
    ibufu
        54
    ibufu  
       2017-03-02 19:09:48 +08:00
    @Phariel settimeout 的执行时间确实不精确,但是可以保证是按顺序排出来的
    TIGERB
        55
    TIGERB  
       2017-03-02 19:12:56 +08:00
    时间空间都没了。。
    siriussilen
        56
    siriussilen  
       2017-03-02 19:29:56 +08:00
    我就问一个问题:
    排序中出现负数怎么办?
    pubby
        57
    pubby  
       2017-03-02 19:46:42 +08:00   ❤️ 1
    @siriussilen “我就问一个问题:
    排序中出现负数怎么办?”

    其他数会问它:你为啥不睡?
    mringg
        58
    mringg  
       2017-03-02 19:54:49 +08:00 via iPhone
    数太多,我直接 mapreduce 了
    whyvans
        59
    whyvans  
       2017-03-02 19:57:07 +08:00
    一亿个数据呢
    blanu
        60
    blanu  
       2017-03-02 20:12:56 +08:00 via iPhone
    珠排序
    ob
        61
    ob  
       2017-03-02 20:17:40 +08:00 via Android
    @siriussilen 无解???
    iheshix
        62
    iheshix  
       2017-03-02 20:27:53 +08:00
    完全没效率吧?且不说排序的种类,万一其中一个数特别大,那说不定别的排序算法都跑完了,这个还在 Sleep 呢。:-D
    HarveyDent
        63
    HarveyDent  
       2017-03-02 20:29:40 +08:00
    当然很好,教官吹完哨,等待新兵们自己排好队。
    ihuotui
        64
    ihuotui  
       2017-03-02 20:36:55 +08:00 via iPhone
    我想说楼主多线程也一知半解
    immrwk
        65
    immrwk  
       2017-03-02 20:37:10 +08:00 via iPhone
    倒是有点意思
    quericy
        66
    quericy  
       2017-03-02 20:37:40 +08:00
    其实就是桶排序的特殊实现
    每个时间单位就是一个单元素的桶,按时间流逝进行顺序的收集
    a1310747
        67
    a1310747  
    OP
       2017-03-02 20:51:51 +08:00
    @ihuotui 的确,工作 2 年多 请大牛多多指点
    siriussilen
        68
    siriussilen  
       2017-03-02 21:18:18 +08:00
    对了,再提出一个问题:
    如何确保线程在某一个时刻一起 run 呢?
    linux 调度单位是进程,对应的是多级反馈队列算法
    windows 调度单位是线程,对应的是一个基于优先级的算法
    请问在 windows 和 linux 的情况下,分别可能会发生哪些情况呢?
    siriussilen
        69
    siriussilen  
       2017-03-02 21:19:59 +08:00
    ^_^不过确实脑洞大开!
    cdsama
        70
    cdsama  
       2017-03-02 21:21:19 +08:00
    不如量子猴排序法好
    jsq2627
        71
    jsq2627  
       2017-03-02 21:39:55 +08:00 via iPhone
    🤔是不是这个能配合变速齿轮玩
    syv2
        72
    syv2  
       2017-03-02 21:57:37 +08:00 via iPad
    知道猴子排序么:每次随机遍历整个数组,直到取到正确排序为止,复杂度为 O(n!)
    think2011
        73
    think2011  
       2017-03-02 22:01:56 +08:00
    @ibufu 惊呆了 ( ̄△ ̄;) 这个好玩
    ZRS
        74
    ZRS  
       2017-03-02 22:31:40 +08:00
    感觉和珠排序有点像
    wangjie
        75
    wangjie  
       2017-03-02 22:33:50 +08:00
    感觉火星了...实际上内核里进行了插入排序,并没有什么卵用...还不如下标排序


    @siriussilen 都增加一个基数就好了
    wizardoz
        76
    wizardoz  
       2017-03-02 22:41:43 +08:00
    然而真是情况是往往要对多个不是数字的属性组合排序,请问用睡眠排序怎么破?
    tianice
        77
    tianice  
       2017-03-02 22:46:20 +08:00
    一个集合保存着恒星的寿命,请排序这个集合。。。
    cuzfinal
        78
    cuzfinal  
       2017-03-02 23:46:57 +08:00 via Android
    时间复杂度和数字的大小有关吧,除了创建线程时是 O(n)
    coldear
        79
    coldear  
       2017-03-03 01:29:58 +08:00
    Sleep(8) 确定比 Sleep(9)先添加到结果吗? 明显有很多多线程的问题
    ryd994
        80
    ryd994  
       2017-03-03 01:53:21 +08:00
    内核定时器有 1ns 的精确度,然而随便一个上下文切换就能到几 us
    你排个 short int 光理想情况就要半小时多了
    然而实际上进程调度器的调度间隔有 100ms …………
    说白了不就是利用 timer 么
    "
    The suspension time may be longer than requested because the argument value is rounded up to an integer multiple of the sleep resolution or because of the scheduling of other activity by the system. But, except for the case of being interrupted by a signal, the suspension time shall not be less than the time specified by rqtp, as measured by the system clock CLOCK_REALTIME.
    "
    所以这方法完全不可行
    考虑如果系统因为某些原因卡了 n 秒,那多个线程同时满足唤醒条件。调度器可没说保证时间短的就先唤醒。完全有可能按任何顺序唤醒所有满足条件的线程。
    msg7086
        81
    msg7086  
       2017-03-03 03:34:08 +08:00
    Sleep 不就是让内核来帮你做排序么。学过操作系统的话应该知道吧。
    nagato
        82
    nagato  
       2017-03-03 03:46:39 +08:00
    @wmhx
    @a1310747

    任何需要比较的排序算法都至少需要 O(nLogn), 这是经过证明的

    任何 O(n)的排序算法都是带条件的

    这个根本不是“排序算法”,谈时间复杂度更是没有意义
    Perry
        83
    Perry  
       2017-03-03 06:19:24 +08:00
    大三的课学过,当时是 bash 的版本
    johnny23
        84
    johnny23  
       2017-03-03 08:07:55 +08:00 via iPhone
    不同操作系统对线程可不见的能按照这个去时间来处理哦...不可靠
    CareiOS
        85
    CareiOS  
       2017-03-03 09:12:50 +08:00
    不可取,空间与时间复杂度太大。
    loveuqian
        86
    loveuqian  
       2017-03-03 09:50:16 +08:00 via iPhone
    麻烦,帮我排个倒序
    waruqi
        87
    waruqi  
       2017-03-03 09:51:27 +08:00
    这个算法是用来搞笑的。。 = =
    RickyIT
        88
    RickyIT  
       2017-03-03 09:57:14 +08:00
    这个排序算法实际意义不太大,不过是一种很不错的思路。。。很有意思
    zacard
        89
    zacard  
       2017-03-03 10:15:51 +08:00
    我被量子猴排震惊了
    xilanhasnoflower
        90
    xilanhasnoflower  
       2017-03-03 10:41:00 +08:00
    这排序有 bug 吧,线程不是同一时间启动的
    irenicus
        91
    irenicus  
       2017-03-03 10:59:03 +08:00
    以前就听说过这个中二的排序法。。。。
    listkun
        92
    listkun  
       2017-03-03 11:43:26 +08:00
    有意思
    rrfeng
        93
    rrfeng  
       2017-03-03 12:01:32 +08:00
    这不是 O(n) 是 O(MAX(N)) ……
    ibegyourpardon
        94
    ibegyourpardon  
       2017-03-03 12:41:20 +08:00   ❤️ 1
    @xcatliu 我仔细想想,引申开来,细思恐极。

    我们宇宙中不是目前还有一堆 XX 常数为什么是这么巧,恰好能被观察到,能形成生命,能这个能那个,感觉设定的那些参数精确到匪夷所思。然后追究起来都说人择原理 blahblah 。

    结合你这个宇宙毁灭一想……
    xcatliu
        95
    xcatliu  
       2017-03-03 12:49:24 +08:00 via iPhone
    @ibegyourpardon 说明我们比较幸运哈哈
    imbahom
        96
    imbahom  
       2017-03-03 13:06:32 +08:00
    这个排序需要 ryzen
    memorycancel
        97
    memorycancel  
       2017-03-03 14:17:53 +08:00
    $r = []
    threads = []
    arr = [2,4,5,6,1,3,9,8,7,0]
    arr.each do |e|
    threads << Thread.new {sleep e; $r << e}
    end
    threads.each {|t|t.join}
    puts $r
    wshcdr
        98
    wshcdr  
       2017-03-03 18:09:59 +08:00
    对线程的把控有那么精确么?
    XadillaX
        99
    XadillaX  
       2017-03-03 18:11:36 +08:00
    这个很早就有了吧?
    fanta
        100
    fanta  
       2017-03-03 19:13:49 +08:00
    如果时钟准确,可以把睡的时间减小,秒改毫秒,微秒, ns
    1  2  
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   3059 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 62ms · UTC 10:59 · PVG 18:59 · LAX 03:59 · JFK 06:59
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.