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

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

这是一个创建于 2828 天前的主题，其中的信息可能已经有所发展或是发生改变。

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

2017-03-02 15:27:02 +08:00 via Android

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

awolfer

2017-03-02 15:27:52 +08:00

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

a1310747

2017-03-02 15:28:01 +08:00

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

easyzhao

2017-03-02 15:28:34 +08:00

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

a1310747

2017-03-02 15:28:34 +08:00

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

langmoe

2017-03-02 15:30:21 +08:00

其实还是相当于桶吧

jasonlz

2017-03-02 15:35:52 +08:00

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

wmhx

2017-03-02 15:38:08 +08:00

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

xjtlujoe

2017-03-02 15:44:12 +08:00

这思路不错

a1310747

2017-03-02 15:47:48 +08:00

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

knightdf

2017-03-02 15:49:21 +08:00

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

nbndco

2017-03-02 15:53:48 +08:00

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

qdwang

2017-03-02 15:54:46 +08:00

@langmoe 没错

linboki

2017-03-02 15:55:32 +08:00 via Android

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

linboki

2017-03-02 15:56:30 +08:00 via Android

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

dreasky

2017-03-02 15:57:47 +08:00

请比较 1 和 10000000000000000000

AsherG

2017-03-02 15:58:01 +08:00

哈哈哈，莫名感觉好萌

wellsc

2017-03-02 16:00:21 +08:00

又是一道面试题

a1310747

2017-03-02 16:01:16 +08:00

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

a1310747

2017-03-02 16:01:24 +08:00

@dreasky 我选择死亡

a1310747

2017-03-02 16:01:38 +08:00

@wellsc 这个不是面试了喂！

xielemon

2017-03-02 16:05:23 +08:00

@jasonlz countdownlatch cylicbarrier

coderluan

2017-03-02 16:06:24 +08:00

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

4ever911

2017-03-02 16:07:24 +08:00

哈哈，果然是开脑洞。

kindjeff

2017-03-02 16:10:39 +08:00 via iPhone

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

IJustmaogepao

2017-03-02 16:15:32 +08:00

@coderluan 23333

noNOno

2017-03-02 16:17:19 +08:00

炫酷，没毛病

sorcerer

2017-03-02 16:18:48 +08:00 via iPhone

厉害脑洞大开

loryyang

2017-03-02 16:19:43 +08:00

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

dreamcountry

2017-03-02 16:21:40 +08:00

是一种方法，但效率不高

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

2017-03-02 16:28:55 +08:00

求真·时间复杂度

noNOno

2017-03-02 16:31:31 +08:00

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

vingz

2017-03-02 16:32:19 +08:00

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

CFMY

2017-03-02 16:37:08 +08:00

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

Phariel

2017-03-02 16:40:58 +08:00 via Android

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

pythonee

2017-03-02 16:42:06 +08:00

这个有点意思

rocksolid

2017-03-02 16:53:03 +08:00

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

a1310747

2017-03-02 16:54:38 +08:00

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

neosfung

2017-03-02 17:16:37 +08:00

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

mnzlichunyu

2017-03-02 17:19:25 +08:00

haha, 非常诙谐

zwzmzd

2017-03-02 17:24:25 +08:00 via Android

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

licraft

2017-03-02 17:25:43 +08:00

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

mozutaba

2017-03-02 17:30:19 +08:00

桶排序

wellsc

2017-03-02 17:33:23 +08:00

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

oldj

2017-03-02 17:43:25 +08:00

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

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

2017-03-02 18:28:35 +08:00

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

cy18

2017-03-02 18:35:04 +08:00

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

wy315700

2017-03-02 18:39:26 +08:00

这不就是珠排序

tideline

2017-03-02 18:40:07 +08:00

珠排序 O(1)

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

guokeke

2017-03-02 18:40:09 +08:00

@oldj 笑死了。

xcatliu

2017-03-02 19:05:33 +08:00

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

ibufu

2017-03-02 19:09:48 +08:00

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

TIGERB

2017-03-02 19:12:56 +08:00

时间空间都没了。。

siriussilen

2017-03-02 19:29:56 +08:00

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

pubby

2017-03-02 19:46:42 +08:00

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

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

mringg

2017-03-02 19:54:49 +08:00 via iPhone

数太多，我直接 mapreduce 了

whyvans

2017-03-02 19:57:07 +08:00

一亿个数据呢

blanu

2017-03-02 20:12:56 +08:00 via iPhone

珠排序

2017-03-02 20:17:40 +08:00 via Android

@siriussilen 无解？？？

iheshix

2017-03-02 20:27:53 +08:00

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

HarveyDent

2017-03-02 20:29:40 +08:00

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

ihuotui

2017-03-02 20:36:55 +08:00 via iPhone

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

immrwk

2017-03-02 20:37:10 +08:00 via iPhone

倒是有点意思

quericy

2017-03-02 20:37:40 +08:00

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

a1310747

2017-03-02 20:51:51 +08:00

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

siriussilen

2017-03-02 21:18:18 +08:00

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

siriussilen

2017-03-02 21:19:59 +08:00

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

cdsama

2017-03-02 21:21:19 +08:00

不如量子猴排序法好

jsq2627

2017-03-02 21:39:55 +08:00 via iPhone

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

syv2

2017-03-02 21:57:37 +08:00 via iPad

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

think2011

2017-03-02 22:01:56 +08:00

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

ZRS

2017-03-02 22:31:40 +08:00

感觉和珠排序有点像

wangjie

2017-03-02 22:33:50 +08:00

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

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

wizardoz

2017-03-02 22:41:43 +08:00

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

tianice

2017-03-02 22:46:20 +08:00

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

cuzfinal

2017-03-02 23:46:57 +08:00 via Android

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

coldear

2017-03-03 01:29:58 +08:00

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

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 秒，那多个线程同时满足唤醒条件。调度器可没说保证时间短的就先唤醒。完全有可能按任何顺序唤醒所有满足条件的线程。