睡眠排序是由当代网友们想出来的排序算法,传闻中发明此算法的程序员已被老板开除。
排序思路是:遍历数组,为每个数字开启一个线程。这个数字有多大,这个线程就睡眠多少秒。待线程睡醒后,输出此数字。利用「小的数字所在的线程会先于大的数字所在的线程醒来」这个特性完成排序。
举个例子,比如公司要对员工按年龄排序,那么睡眠排序的思路就是:为每个员工分配一个房间,自己有多少岁就在房间里睡多少个小时。员工睡醒后就走出房间,老板按照员工出房间的顺序完成排序。
代码如下:
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();
}
}
由于此算法可能由于数字过大而迟迟不能算出结果,所以又被称之为「天地同寿排序法」。
整个过程只需要遍历一次数组,所以时间复杂度为
... 吗?在 stack overflow 上对此有过讨论,讨论的结果是它的时间复杂度应该是 ,这个表达式很奇怪,大多数排序算法的时间复杂度都只与数据量有关,而睡眠排序却是与数据本身有关。
这一点类似于计数排序,计数排序的空间复杂度就和数据本身有关。所以我们可以说睡眠排序的时间复杂度是 k
表示数据范围,另外,想要达到 ,还需要将所有数据都减去最小值)。 基于数据量, 基于数据本身。
但这里的
并不是真的那么快,它和数据的规模是两个维度的东西。或许讨论睡眠排序的时间复杂度是没有意义的,读者不妨在留言区说出你的看法。由于开启线程需要一些内存开销,所以空间复杂度为
。需要注意的是,线程的调度是由操作系统决定的,开发者无法控制操作系统何时调用哪一个线程。而且线程的调度也需要一定时间,所以睡眠排序算法不一定能得出正确的结果。
联系客服