lancelei

(严肃向)奇葩算法之——睡眠排序
这次要给大家介绍的是一个严肃向(欢乐向)的算法,睡眠排序。说实话小妖是非常佩服这个天才啦。现在就简单的介绍下这个算...
扫描右侧二维码阅读全文
24
2018/10

(严肃向)奇葩算法之——睡眠排序

这次要给大家介绍的是一个严肃向(欢乐向)的算法,睡眠排序。说实话小妖是非常佩服这个天才啦。现在就简单的介绍下这个算法吧。

这个算法的时间复杂度为O(n),其使用价值不是很高,但是能找到这么一个方法,小妖是非常非常佩服的。

花了点时间,研究了一下,写了个demo出来,我们先来看看代码吧。

public class SleepSort {  
    public static void main(String[] args) {  
        int[] a = {4,7,1,3,9,5,6,2};  //需要排序的数组
        SleepThread[] SleepThreads = new SleepThread[a.length];  //根据待排数组a[]的长度建一个线程数组
        for (int i = 0; i < sortThreads.length; i++) { //把待排数组转移到线程数组中
            SleepThreads[i] = new SleepThread(a[i]);  
        }  
        for (int i = 0; i < SleepThreads.length; i++) {  
            SleepThreads[i].start();  
        }  
    }  
}  
class SortThread extends Thread{  
    int time = 0;  
    public SortThread(int time){  
        this.time = time;  
    }  
    public void run(){  
        try {  
            sleep(time*10+10);  
        } catch (InterruptedException e) {  
            // TODO Auto-generated catch block   
            e.printStackTrace();  
        }  
        System.out.println(time);  
    }  
}  

这个算法的思想就是CPU的线程和调度来实现的,缺陷有很多,不能存在负数值,当两个数据值接近的话,会有误差。具体实现就是,让每一个数占用一个线程,并且让这个线程睡眠,睡眠的时间是数的值的10倍+10。为啥不睡眠和它数值一样大呢,那是因为数值太小时,误差太大,睡眠的时间不比输出的时间少(毕竟现在计算机运算速度那么快,1线程还在输出的时候,没准2线程就已经醒过来输出了),这时就会输出不正确的结果。

没准几年以后,就可以真正的让排序算法在多物理线程上并行起来提高效率了呢,完结撒花。

Last modification:October 24th, 2018 at 05:31 pm
If you think my article is useful to you, please feel free to appreciate

Leave a Comment