搞笑排序之睡眠排序

桃扇骨 2023-02-20 04:52 2阅读 0赞

一个程序的运行时间受多种因素影响，因此它的返回结果不一定正确

> 构造n个线程，它们和这n个数一一对应。初始化后，线程们开始睡眠，等到对应的数那么多个时间单位后各自醒来，然后输出它对应的数。这样最小的数对应的线程最早醒来，这个数最早被输出。等所有线程都醒来，排序就结束了

# java实现 #

package com.oceanstar;
    
    
    public class TreeNode {
        
        public static void main(String[] args) {
        
            int[] arr = {
        10,40,70,30,80,90,20,60,50,49,48,-2};
            //创建指定长度的线程数组
            SortThread[] sortThreads = new SortThread[arr.length];
            //指定每个线程数组的值
            for (int i = 0; i < sortThreads.length; i++) {
        
                sortThreads[i] = new SortThread(arr[i]);
            }
            //开启每个线程
            for (int i = 0; i < sortThreads.length; i++) {
        
                sortThreads[i].start();
            }
        }
    }
    
    class SortThread extends Thread{
        
        int s = 0;
        public SortThread(int s){
        
            this.s = s;
        }
        public void run(){
        
            try {
        
                sleep(s*10+10);  //睡眠指定的时间
            } catch (InterruptedException e) {
        
    
                e.printStackTrace();
            }
            //输出该数
            System.out.printf("%d\t",s);
        }
    }

# golang实现 #

## 版本一 ##

package main
    
    import (
    	"fmt"
    	"time"
    )
    
    var flag bool
    var count int
    var c chan bool
    
    func tosleep(data int)  {
        
    	time.Sleep(time.Duration(data) * time.Microsecond * 1000) //如果各线程睡觉时间太短而没法准确按照时间长度排序, 前面乘以1000可以解决问题
    	fmt.Print(data , "\t")
    	c <- true
    }
    
    func listen(size int)  {
        
    	for flag  {
        
    		select {
        
    		case <- c:
    			count++
    			if count >= size {
        
    				flag = false
    				break
    			}
    		}
    	}
    }
    func main() {
        
    	arr := []int{
        16, 8, 1, 24, 30, 2}
    	flag = true
    	c = make(chan bool, len(arr)) // 管道：用来传输元素
    	for i := 0; i < len(arr) ; i++ {
        
    		go tosleep(arr[i])
    	}
    	go listen(len(arr))
    	for flag {
        
    		time.Sleep(1*time.Second)
    	}
    }

## 版本二 ##

package main
    
    import (
    	"fmt"
    	"time"
    )
    
    func num_sleep(sec int, c chan int) {
        
    	time.Sleep(100 * time.Millisecond * time.Duration(sec))
    	c <- sec
    }
    func main() {
        
    	arr := []int{
        16, 8, 1, 24, 30, 2}
    	c := make(chan int, len(arr)) // 管道：用来传输元素
    	for i := 0; i < len(arr) ; i++ {
        
    		go num_sleep(arr[i], c)
    	}
    	var res []int
    	for i := 0; i < len(arr) ; i++ {
        
    		res = append(res, <-c)
    	}
    	close(c)
    	fmt.Println(res)
    }

代码很粗略，很多bug。比如

(1) 搞不定负数。

(2)比如输入数据很相近时会有误差

(3)输入数据很多时，这些线程不能看作是同时启动等等…

对于(1)，可以用一个在恒正的函数把输入映射成时间；

(2)，可以乘个系数，放大数据间的差，但是依然搞不定重复的数据；

(3)，试着让算法在多个物理核上真正的并行起来