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

[a1310747]

估计有大部分人不知道把，原理是构造 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;
    }
}

[bp0]

会不会睡一辈子，（手动斜眼

[awolfer]

线程开销很大吧, 这个太不划算了

[a1310747]

@bp0 哈哈哈哈 你这么一说还真有可能...

[easyzhao]

跟存数据库里 select order 一下有什么区别

[a1310747]

@awolfer 但是你不能否定这也是一种排序法 反正让我想我是想不出来

[langmoe]

其实还是相当于桶吧

[jasonlz]

怎么保证所有线程同时开始运行？

[wmhx]

在 coolshell.cn 看排序的时候就见过的, 听说这是复杂度最低的排序了, 没有之一.

[xjtlujoe]

这思路不错

[a1310747]

@wmhx O(n)的时间复杂度的确是最低的....

[knightdf]

时间复杂度在这个排序上已经毫无意义，哈哈哈

[nbndco]

这个方法显然不是 O(n)的， event loop 的调用过程显然还是要排序了，不然每次遍历变 n^2 了。
如果这个是 O(n)，那么 sort(int *arr, int len)应该算是 O(1)的了。

[qdwang]

@langmoe 没错

[linboki]

大概本质就是是带阻塞的堆排序。

[linboki]

因为内核的定时器普遍用小根堆实现

[dreasky]

请比较 1 和 10000000000000000000

[AsherG]

哈哈哈，莫名感觉好萌

[wellsc]

又是一道面试题

[a1310747]

@AsherG 对啊 哈哈哈 这个排序法还被称为天才排序法

[a1310747]

@dreasky 我选择死亡

[a1310747]

@wellsc 这个不是面试了喂！

[xielemon]

@jasonlz countdownlatch cylicbarrier

[coderluan]

不扩展的话，排个负数就得开时光机了吧。

[4ever911]

哈哈，果然是开脑洞。

[kindjeff]

https://zhuanlan.zhihu.com/p/20644113

[IJustmaogepao]

@coderluan 23333

[noNOno]

炫酷，没毛病

[sorcerer]

厉害 脑洞大开

[loryyang]

恩，挺有意思的啊，开了脑洞

[dreamcountry]

是一种方法，但效率不高

[ibufu]

这个在 js 里可以用 setTimeout 了
```
function sort(nums) {
for (let i = 0; i < nums.length; i++) {
setTimeout(() => {
console.log(nums[i]);
}, nums[i]);
}
}
```

[Crossin]

求 真·时间复杂度

[noNOno]

精确度最多到毫秒，就算数字作为毫秒值转成时间，仍旧无法进行相差太大的数字排序。.......

[vingz]

时间，要等超时后，黄花菜都凉了

[CFMY]

线程挂机后的唤醒顺序取决 cpu
这个方法在 cpu 忙碌情况下很可能给出错误结果
我觉得算不上一个排序

[Phariel]

这，睡眠再唤醒就跟精确 setTimeout 一样不靠谱，中间万一有一环阻塞了一下就全盘完蛋。。。

[pythonee]

这个有点意思

[rocksolid]

本质还是计数排序，不过蛮好玩的

[a1310747]

@rocksolid 是的 今天突然看到 把我震到了

[neosfung]

贡献一个猴子排序吧。。。
https://zh.wikipedia.org/wiki/Bogo%E6%8E%92%E5%BA%8F

[mnzlichunyu]

haha, 非常诙谐

[zwzmzd]

这相当于把排序工作交给操作系统了吧

[licraft]

感觉和桶排序原理一样吧。。。占空间

[mozutaba]

桶排序

[wellsc]

@a1310747 可以拿这题来面试对创建线程的掌握度

[oldj]

还有一种「 twitter 排序」（也可以换成「微博排序」、「朋友圈排序」），原理是调用 API 把要排序的数字发到 twitter 上，请好友帮忙排序，每当有人回复时，检查回复内容是否正确，如果是则输出，否则继续等待。

[weyou]

利用时间的有序单向性，将数值转化成等待时间。只是一个小技巧，但没有实际意义。
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]

不忍直视，这线程得占用多少效率。线程通信也需要时间的吧，不划算。

[cy18]

@weyou 这基本上就是桶排序- -

[wy315700]

这不就是珠排序

[tideline]

珠排序 O(1)

https://zh.wikipedia.org/wiki/%E7%8F%A0%E6%8E%92%E5%BA%8F

[guokeke]

@oldj 笑死了。

[xcatliu]

计算机科学家之间的一个笑话说：量子计算机能够以 O(n) 的复杂度更有效地实现 Bogo 排序。这将使用真正的量子的随机性来随机打乱列表。根据量子物理学的多世界诠释，量子的随机性分别在无限的宇宙序列中展开，其中的一些将会提供一个排好序的列表。因为需要重新排列的次数虽然很大但仍然是有限的。这个列表接着就被测试出来（需要 n-1 次比较）。接着，计算机就应该实施“摧毁宇宙”的操作，使得在剩下的宇宙中的观察者能够得到一个排好序的列表。

[ibufu]

@Phariel settimeout 的执行时间确实不精确，但是可以保证是按顺序排出来的

[TIGERB]

时间空间都没了。。

[siriussilen]

我就问一个问题：
排序中出现负数怎么办？

[pubby]

@siriussilen “我就问一个问题：
排序中出现负数怎么办？”

其他数会问它：你为啥不睡？

[mringg]

数太多，我直接 mapreduce 了

[whyvans]

一亿个数据呢

[blanu]

珠排序

[ob]

@siriussilen 无解？？？

[iheshix]

完全没效率吧？且不说排序的种类，万一其中一个数特别大，那说不定别的排序算法都跑完了，这个还在 Sleep 呢。:-D

[HarveyDent]

当然很好，教官吹完哨，等待新兵们自己排好队。

[ihuotui]

我想说楼主多线程也一知半解

[immrwk]

倒是有点意思

[quericy]

其实就是桶排序的特殊实现
每个时间单位就是一个单元素的桶，按时间流逝进行顺序的收集

[a1310747]

@ihuotui 的确,工作 2 年多 请大牛多多指点

[siriussilen]

对了，再提出一个问题：
如何确保线程在某一个时刻一起 run 呢？
linux 调度单位是进程，对应的是多级反馈队列算法
windows 调度单位是线程，对应的是一个基于优先级的算法
请问在 windows 和 linux 的情况下，分别可能会发生哪些情况呢？

[siriussilen]

^_^不过确实脑洞大开！

[cdsama]

不如量子猴排序法好

[jsq2627]

🤔是不是这个能配合变速齿轮玩

[syv2]

知道猴子排序么：每次随机遍历整个数组，直到取到正确排序为止，复杂度为 O(n!)

[think2011]

@ibufu 惊呆了 (￣△￣；) 这个好玩

[ZRS]

感觉和珠排序有点像

[wangjie]

感觉火星了...实际上内核里进行了插入排序,并没有什么卵用...还不如下标排序


@siriussilen 都增加一个基数就好了

[wizardoz]

然而真是情况是往往要对多个不是数字的属性组合排序，请问用睡眠排序怎么破？

[tianice]

一个集合保存着恒星的寿命，请排序这个集合。。。

[cuzfinal]

时间复杂度和数字的大小有关吧，除了创建线程时是 O(n)

[coldear]

Sleep(8) 确定比 Sleep(9)先添加到结果吗？ 明显有很多多线程的问题

[ryd994]

内核定时器有 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]

Sleep 不就是让内核来帮你做排序么。学过操作系统的话应该知道吧。

[nagato]

@wmhx
@a1310747

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

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

这个根本不是“排序算法”，谈时间复杂度更是没有意义

[Perry]

大三的课学过，当时是 bash 的版本

[johnny23]

不同操作系统对线程可不见的能按照这个去时间来处理哦...不可靠

[CareiOS]

不可取，空间与时间复杂度太大。

[loveuqian]

麻烦，帮我排个倒序

[waruqi]

这个算法是用来搞笑的。。 = =

[RickyIT]

这个排序算法实际意义不太大，不过是一种很不错的思路。。。很有意思

[zacard]

我被量子猴排震惊了

[xilanhasnoflower]

这排序有 bug 吧，线程不是同一时间启动的

[irenicus]

以前就听说过这个中二的排序法。。。。

[listkun]

有意思

[rrfeng]

这不是 O(n) 是 O(MAX(N)) ……

[ibegyourpardon]

@xcatliu 我仔细想想，引申开来，细思恐极。

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

结合你这个宇宙毁灭一想……

[xcatliu]

@ibegyourpardon 说明我们比较幸运哈哈

[imbahom]

这个排序需要 ryzen

[memorycancel]

$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]

对线程的把控有那么精确么？

[XadillaX]

这个很早就有了吧？

[fanta]

如果时钟准确，可以把睡的时间减小，秒改毫秒，微秒, ns