史上最秀！时间复杂度 O(1) 的排序算法！

发表于 | 分类于

看完标题，我是不是可以明日去UC编辑部报道了，哈哈哈哈。

算法原理

最近排序算法中也出现了一个网红，它不仅很红，而且时间复杂度是O(1)，我这种算法爱(da)好(shui)狂(bi)怎么可以错过这么优秀的算法。那么，是什么排序算法这么优秀？它的名字就叫做睡眠排序。顾名思义，就是利用程序的 sleep，什么也不用干，等着数字自己蹦出来。

上代码！

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
// go 版，更能展现出该算法的简洁与优秀
package main

import (
	"fmt"
	"time"
)

func main() {
	var arr = [...]int{300, 60, 1, 9, 4, 2, 7, 5}
	var sorted = make(chan int)

	for i := 0; i < len(arr); i++ {
		go func(i int) {
			if arr[i] > 0 {
				time.Sleep(time.Duration(arr[i]) * time.Millisecond)
			}
			sorted <- arr[i]
		}(i)
	}

	for i := 0; i < len(arr); i++ {
		fmt.Print(<-sorted, " ")
	}
}

注意

  • 这个算法有一些局限，目前只能对数字进行排序。
  • 有一些同学认为这是一个时间复杂度为 O(n) 的算法，这个是错误的，算法所用的时间是 max(arr), 是一个常数时间，怎么能是 O(n) 呢？
  • 熟悉 go 的同学可能注意到了， Nanosecond 比 Millisecond 更短，为什么不用 Nanosecond 呢？经过我实际测试，Nanosecond 在对相差不大的数进行排序的时候，会出现输出顺序的错误，可能 Nanosecond 太小了吧。
  • 上述代码，你可以转载、使用，但是如果造成任何损失，本人不承担任何责任。
  • 不许笑，认真脸！<(‵^′)>