Sleep Sort 的 Golang 实现

多线程排序的蛋疼算法

前言

在网上乱逛的时候看到了这个 sleep-sort 的算法，感觉很有趣。刚好在学 golang, 就用这个来实践一下并发操作吧。

这个算法原本是来自 4chan 的一个帖子，不过好像原帖早就被冲水了？只能说 4chan 老哥欢乐多。

原本是给的一个 shell 脚本

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

正文

先上源代码

package main

import (
	"fmt"
	"log"
	"os"
	"path/filepath"
	"strconv"
	"time"
)

func main() {
	if len(os.Args) < 2 || os.Args[1] == "-h" || os.Args[1] == "--help" {
		fmt.Printf("使用方法： %s [需要排序的数组 空格隔开]\n", filepath.Base(os.Args[0]))
		fmt.Printf("如： %s 2 2 1 3 4\n", filepath.Base(os.Args[0]))
		os.Exit(1)
	}
	answer := make(chan int, len(os.Args)-1)
	defer close(answer)
	for _, num := range os.Args[1:] {
		if sleeptime, err := strconv.Atoi(num); err != nil {
			log.Fatal(err)
		} else {
			go func() {
				time.Sleep(time.Duration(sleeptime) * time.Millisecond * 120)
				answer <- sleeptime
			}()
		}
	}
DONE:
	for {
		switch len(answer) {
		case len(os.Args) - 1:
			for i := 0; i < len(os.Args)-1; i++ {
				output := <-answer
				fmt.Print(output, " ")
			}
			break DONE
		}
	}
}

我这边倒没有专门写一个排序的包，不过单独摘出来其实也很简单的。改成输入的参数是一个 int 类型的函数就好了。

我这个主要是通过命令行的方式来调用，所以也顺便练习了一下 os.Args 的使用。

算法的实现其实很简单，就是对要排序的每个数字开一个 goroutine 然后等待对应的时长。在时间到了之后就把结果放到 answer 这个通道里面。

然后主函数中就是等所有的数字处理好之后就可以开始一个一个输出了。因为不知道要等待的时长，所以就是用了一个无限循环的函数来检测answer的长度。

参考

Sleep sort with goroutines