V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
a1310747
V2EX  ›  程序员

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

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

    估计有大部分人不知道把,原理是构造 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  
    mintist
        101
    mintist  
       2017-03-03 22:28:43 +08:00
    逻辑上果然够简单, O(∩_∩)O 哈哈~
    arzusyume
        102
    arzusyume  
       2017-03-04 11:31:24 +08:00
    我想到之前一个笑话...要求输出一天后的时间...

    sleep(86400);
    echo time();
    JiaZombie
        103
    JiaZombie  
       2017-03-04 12:57:52 +08:00
    @arzusyume 这让我想到之前一个笑话...
    把程序运行时间乘以 0.8 后再输出,程序效率就提高了
    log4geek
        104
    log4geek  
       2017-03-04 13:20:01 +08:00
    好有才!!
    halfer53
        105
    halfer53  
       2017-03-04 13:44:42 +08:00
    系统对 alarm 的排序是 O(n),遍历一遍是 O ( n ), 所以还是 O ( n )
    huiyue
        106
    huiyue  
       2017-03-04 14:36:49 +08:00
    这个可以是一个段子,虽然思路新颖。
    injy
        107
    injy  
       2018-12-12 23:29:44 +08:00
    那是不是我也可以这样?
    $arr = Array(9,7,2,6,15,8,9,9,9,9,9);
    for ($i=1; $i < 15; $i++) {
    foreach ($arr as $k => $v) {
    $x = $v + $i;
    if ($x>15) {
    $newArr[]=$v;
    unset($arr[$k]);
    }
    }

    }
    print_r($newArr);
    1  2  
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   1414 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 667ms · UTC 23:47 · PVG 07:47 · LAX 16:47 · JFK 19:47
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.