Linear Sort
- function LinearSort(list): StartTime=Time() MergeSort(list) Sleep(1e6*length(list)-(Time()-StartTime)) return
- How to sort a list in linear time
The best case is O(n), and the worst case is that someone checks why.
- 函数 线性排序(列表):
- 开始时间 = 当前时间()
- 归并排序(列表)
- 睡眠(1e6 * 列表长度(列表) - (当前时间() - 开始时间))
- 返回
- 如何在线性时间内排序一个列表
- 最好情况是 O(n)，最坏的情况是有人检查为什么
译注:
程序的复杂度有最好/坏情况, 都是写成 O(一个关于 n 的表达式) 表示运行性能, 表达式越小越好
下文的 n 是列表长度. 该函数首先使用归并排序（时间复杂度为O(n log n)）对列表进行排序，然后根据列表长度 * 1e6 - 已用时长来计算剩下需要睡眠的时间，以使整个过程看起来像在 O(n) 时间内完成。有人检查会发现这个睡眠, 使算法”变坏”到 O(n log n)
还有个隐藏笑点：基于比较的排序复杂度最好就是 O(n log n)，不可能比这更好。
