脑洞大开的算法

Table of Contents

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

1. sleep 排序

有一个无序的数组，每个元素为一个数字，将其排序。

思路：数组大小创建相同数量的线程，每个线程都 sleep，时长就是对应的数，因此数字越大，线程阻塞的时间就越长。

实现代码如下： 

from time import sleep
import threading


def sleep_print(n):
    sleep(n)
    print(n)


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

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

Common Lisp 实现如下： 

(defun sleeprint(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 () (sleeprint 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