算法：代码量很少，但很牛逼很经典的算法（洗牌算法、睡眠排序）

喜欢ヅ旅行 2023-07-12 11:56 16阅读 0赞

**洗牌算法**

这个代码很简单，只有两行代码，但是却可以实现这个功能：对于给定的 n 个元素，生成的那个排列，每一个元素都能等概率地出现在每一个位置。

换句话说，每一个位置都能等概率地放置每个元素。

代码如下：  
for(int i = n - 1; i >= 0 ; i – )  
swap(arr\[i\], arr\[rand(0, i)\]) // rand(0, i) 生成 \[0, i\] 之间的随机整数  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]

**睡眠排序**

public class SleepSort {   
        public static void main(String[] args) {   
            int[] ints = { 1,4,7,3,8,9,2,6,5};  
            SortThread[] sortThreads = new SortThread[ints.length];  
            for (int i = 0; i < sortThreads.length; i++) {   
                sortThreads[i] = new SortThread(ints[i]);  
            }  
            for (int i = 0; i < sortThreads.length; i++) {   
                sortThreads[i].start();  
            }  
        }  
    }  
    class SortThread extends Thread{   
        int ms = 0;  
        public SortThread(int ms){   
            this.ms = ms;  
        }  
        public void run(){   
            try {   
                sleep(ms*10+10);  
            } catch (InterruptedException e) {   
                // TODO Auto-generated catch block 
                e.printStackTrace();  
            }  
            System.out.println(ms);  
        }  
    }

它原理是构造 n 个线程，它们和这 n 个数一一对应。

初始化后，线程们开始睡眠，等到对应的数那么多个时间单位后各自醒来，然后输出它对应的数。

这样最小的数对应的线程最早醒来，这个数最早被输出。

等所有线程都醒来，排序就结束了。

不要问时间复杂度，时间复杂度在这个排序上已经毫无意义！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200308164958786.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200308165021950.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/2020030816510072.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200308165115267.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20200308165135251.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200308165159257.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20200308165227256.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 7]: https://img-blog.csdnimg.cn/20200308165243811.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ_size_16_color_FFFFFF_t_70 8]: https://img-blog.csdnimg.cn/202003081653179.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2Jhb2JpbmdqaQ==,size_16,color_FFFFFF,t_70