脑洞大开的算法

Table of Contents

最后更新时间：2017-03-03

1. sleep 排序

对一个由数字组成的无序的数组做排序。

创建和数组元素一样多的线程，每个线程都 sleep，时长就是对应的数，数字越大，线程阻塞的时间就越长。

实现代码如下： 

from time import sleep
import threading


def sleep_sort(n):
    sleep(n)
    print(n)                    # 屏幕打印出的顺序就是已排序好的


target = [1, 3, 8, 4, 9, 10, 3, 20, 5]

for i in target:
    thread = threading.Thread(target=sleep_sort, args=(i,))
    thread.start()

Common Lisp 版本： 

(defun sleep-sort(n)
    (sleep (/ n 10))
    (format t "~a~%" n))

(loop for i in '(1 3 8 4 9 10 3 20 5) do
      (sb-thread:make-thread (lambda () (sleep-sort i))))

(loop while (not (null (cdr (sb-thread:list-all-threads)))))

其他语言的实现参考：https://rosettacode.org/wiki/Sorting_algorithms/Sleep_sort

2. bogo（猴子）排序

让一只猴子在打字机上乱敲按键，按键时间达到无穷时，也能打出一部莎士比亚全集。——无限猴子定理

这是种效率极低的排序算法，随机打乱集合中数字的顺序，只要你有足够的耐心等待，迟早会排列正确的。 

from random import shuffle


def bogo_sort(array):
    pos_list = range(1, len(array))

    while not all(array[p] > array[p - 1] for p in pos_list):
        shuffle(array)

    return array


if __name__ == '__main__':
    print(bogo_sort([10, 4, 1, 5, 9, 8, 3, 6]))

其他语言实现参考：https://zh.wikipedia.org/wiki/Bogo%E6%8E%92%E5%BA%8F