排序算法全解析

睡眠排序是由当代网友们想出来的排序算法，传闻中发明此算法的程序员已被老板开除。

排序思路是：遍历数组，为每个数字开启一个线程。这个数字有多大，这个线程就睡眠多少秒。待线程睡醒后，输出此数字。利用「小的数字所在的线程会先于大的数字所在的线程醒来」这个特性完成排序。

举个例子，比如公司要对员工按年龄排序，那么睡眠排序的思路就是：为每个员工分配一个房间，自己有多少岁就在房间里睡多少个小时。员工睡醒后就走出房间，老板按照员工出房间的顺序完成排序。

代码如下：

• Java

public static void sleepSort(int[] arr) {
    for (final int number : arr) {
        new Thread(new Runnable() {
            @Override
            public void run() {
                try {
                    Thread.sleep(number * 1000L);
                    System.out.println(number);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();
    }
}

由于此算法可能由于数字过大而迟迟不能算出结果，所以又被称之为「天地同寿排序法」。

时间复杂度 & 空间复杂度

整个过程只需要遍历一次数组，所以时间复杂度为 $O(n)$O(n) ... 吗？

在 stack overflow 上对此有过讨论，讨论的结果是它的时间复杂度应该是 $O(max(input)+n)$O(max(input)+n)，这个表达式很奇怪，大多数排序算法的时间复杂度都只与数据量有关，而睡眠排序却是与数据本身有关。

这一点类似于计数排序，计数排序的空间复杂度就和数据本身有关。所以我们可以说睡眠排序的时间复杂度是 $O(n)$O(n) 或 $O(k)$O(k)（k 表示数据范围，另外，想要达到 $O(k)$O(k)，还需要将所有数据都减去最小值）。$O(n)$O(n) 基于数据量，$O(k)$O(k) 基于数据本身。

但这里的 $O(k)$O(k) 并不是真的那么快，它和数据的规模是两个维度的东西。或许讨论睡眠排序的时间复杂度是没有意义的，读者不妨在留言区说出你的看法。

由于开启线程需要一些内存开销，所以空间复杂度为 $O(n)$O(n)。

需要注意的是，线程的调度是由操作系统决定的，开发者无法控制操作系统何时调用哪一个线程。而且线程的调度也需要一定时间，所以睡眠排序算法不一定能得出正确的结果。