沙雕排序算法之猴子排序、睡眠排序

转载请注明出处❤️

作者：测试蔡坨坨

原文链接：caituotuo.top/1b3dc548.html

你好，我是测试蔡坨坨。

当谈到算法时，通常人们会追求最优解，而最优解的评判标准主要考虑时间复杂度和空间复杂度，因为较低的复杂度通常代表着更优秀的算法。然而，有一些有趣的例外，即那些非传统的算法，如猴子排序（Monkey Sort）和睡眠排序（Sleep Sort），都是一些令人忍俊不禁的例子，尽管它们并不实用，但它们都引发了人们的兴趣和好奇心。

本篇将详细探讨这两种算法。

猴子排序算法

在一本1909年出版谈概率的书籍中，埃米尔·博雷尔提出了无限猴子定理，其中介绍了“打字的猴子”的概念。

故事情节

很久以前，有一个猴子叫做查尔斯，他生活在一个巨大的图书馆里。这个图书馆里有数以亿计的书籍和打字机，包含了所有可能的字母、数字和标点符号。查尔斯对打字机产生了浓厚的兴趣。

有一天，查尔斯突然站在了一台打字机前。虽然他并不知道如何打字，但他开始随机地按下键盘上的键。他的动作毫无规律，就像是瞎猜一样。

人们会好奇地想知道，如果查尔斯一直随机地按键，是否有一天他能够打出莎士比亚的某一部作品，比如《哈姆雷特》呢？或者打出一本完整的百科全书？

这个故事用来探讨概率和无序事件的概念。理论上，查尔斯确实有可能在某一刻随机地按键，打出一部文学作品或其他文字。然而，由于随机性极高，要实现这一点所需要的时间几乎是不可想象的。这个思考实验强调了概率事件的稀有性和随机性，以及在实际情况下，某些事件可能需要极长的时间才能发生。

真猴子实验

为了验证这一理论的真实性，2003年，英国一所大学的师生从学校里拿了两千欧元的科研经费，给动物园的猴子买了一台电脑和一个键盘。然而结果并不尽人意，在一个月的相处时间里，猴子除了胡乱敲键盘外，剩下的时间便是在电脑上进行大小便，最终导致电脑无法正常运行，实验宣告失败。

程序模拟猴子敲键盘

后来有人尝试用计算机程序来模拟猴子敲击键盘，最终在花费了 421625*10^23 年后，终于打出了莎士比亚的前十九个字母VALENTINE.Cease to。

猴子排序算法

基于上述理论，便可以得到猴子排序算法，也被称为猴子补丁排序（BogoSort）。对于要排序的数组，每一次给它进行一个随机的排序，那么总有一次，它能够变成一个有序的数组，如果运气好，可能一次就搞定（一次成功的幸运猴，时间复杂度就是O(N)，Perfect！），如果运气不好，可能一直都不会成功（永不成功猴，时间复杂度就是INF）。

Python代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
# author: 测试蔡坨坨
# datetime: 2023/9/2 0:28
# function: 猴子排序算法

import random
import time


def is_sorted(arr):
    # 检查数组是否已排序
    for i in range(1, len(arr)):
        if arr[i - 1] > arr[i]:
            return False
    return True


def monkey_sort(arr):
    attempts = 0
    start_time = time.time()

    while not is_sorted(arr):
        random.shuffle(arr)  # 随机打乱列表
        attempts += 1  # 尝试数+1
        print(f'第{attempts}次：' + str(arr))

    end_time = time.time()
    elapsed_time = end_time - start_time  # 耗时

    return arr, attempts, elapsed_time


if __name__ == "__main__":
    # 生成一个随机数组，作为排序的输入
    input_array = [random.randint(1, 1000) for _ in range(10)]

    sorted_array, attempts, elapsed_time = monkey_sort(input_array)

    print("原始数组:", input_array)
    print("排序后的数组:", sorted_array)
    print("排序尝试次数:", attempts)
    print("排序耗时（秒）:", elapsed_time)

我们尝试用猴子排序算法对10个1~1000范围内的数据做排序，看看最终要尝试多少次，花费多长时间？

接下来就是见证奇迹的时刻……

速度也不算太慢，也就尝试了7920246次，耗时448秒，不到8分钟。（笑哭

Java代码实现

基本思路：

  1. 将数组打乱：方法1、自己写一个方法；方法2、使用Collections.shuffle()

  2. 由于Collections.shuffle(List<?> list)需接收一个List参数，因此可以使用guava（瓜瓦），Google提供的api Ints.asList(int... backingArray)将int数组转成list。

    1
    2
    3
    4
    5
    6
    <!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
    <dependency>
        <groupId>com.google.guava</groupId>
        <artifactId>guava</artifactId>
        <version>23.0</version>
    </dependency>

  3. 判断数组是否按顺序排序

具体代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
package top.caituotuo.sortUtil;

import com.google.common.primitives.Ints;

import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Random;

/**
 * author: 测试蔡坨坨
 * datetime: 2023/9/2 1:04
 * function: Collections.shuffle()、Ints api应用
 */
public class MonkeySort {
    public static void main(String[] args) {
        // 生成一个包含10个随机整数的数组（范围在1到1000之间）
        int[] inputArray = new int[10];
        Random rand = new Random();
        for (int i = 0; i < inputArray.length; i++) {
            inputArray[i] = rand.nextInt(1000) + 1;
        }

        System.out.println("原始数组: " + Arrays.toString(inputArray));
        monkeySort(inputArray);
    }

    public static void monkeySort(int[] nums) {
        int attempts = 0;
        long startTime = System.currentTimeMillis();
        out:
        while (true) {
            List<Integer> tempList = Ints.asList(nums);
            Collections.shuffle(tempList);
            int[] result = Ints.toArray(tempList);

            for (int i = 1; i < result.length; i++) {
                if (result[i - 1] > result[i]) {
                    attempts++;
                    System.out.printf("第%s次: %s%n", attempts, Arrays.toString(result));
                    continue out;
                }
            }

            attempts++;
            System.out.printf("第%s次: %s%n", attempts, Arrays.toString(result));

            // 将排好序的结果复制回 nums 数组
            System.arraycopy(result, 0, nums, 0, result.length);
            break;
        }

        long endTime = System.currentTimeMillis();
        double elapsedTime = (endTime - startTime) / 1000.0;

        System.out.println("排序后的数组: " + Arrays.toString(nums));
        System.out.println("排序尝试次数: " + attempts);
        System.out.println("排序耗时（秒）: " + elapsedTime);
    }
}

测试结果：

睡眠排序算法

聊完猴子排序，我们再来看看睡眠排序。

睡眠排序算法是一个奇特而有趣的概念，其做法就是根据数字数组创建多个线程，并使每个线程休眠的时间与其对应的数字值成正比，数值越小的线程就会越早醒来，数值越大的线程就会越晚醒来，这样就完成了对数据的排序。

听起来是不是很有趣，但实际上，睡眠排序面临许多问题，包括线程创建和管理的开销，以及对于小数值和相同数值的处理。因此，它实际上并不是一个可行的排序算法，而是一种有趣的编程挑战和思考实验。

Python代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
# author: 测试蔡坨坨
# datetime: 2023/9/2 2:40
# function: 睡眠排序算法
import random
import threading
import time


def sleep_sort(nums):
    sorted_array = []

    def sleep_and_append(num):
        time.sleep(num)
        sorted_array.append(num)

    # 记录开始时间
    start_time = time.time()

    threads = []
    for num in nums:
        thread = threading.Thread(target=sleep_and_append, args=(num,))
        threads.append(thread)
        thread.start()

    for thread in threads:
        thread.join()

    print("排序后的数组:", sorted_array)
    # 计算时间差
    print("排序耗时（秒）:", time.time() - start_time)


if __name__ == "__main__":
    input_array = [random.randint(1, 10) for _ in range(5)]
    print("原始数组:", input_array)
    sleep_sort(input_array)

运行结果：

从运行结果可以看出，睡眠排序的耗时取决于数组中最大的那个数字，数字越大，耗时越久；当数组中存在负数时，运行就会报错，因为线程的睡眠时间不能为负数。

Java代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
package top.caituotuo.sortUtil;

/**
 * author: 测试蔡坨坨
 * datetime: 2023/9/2 2:53
 * function: 睡眠排序算法
 */

import java.util.Arrays;
import java.util.Random;

public class SleepSort {
    public static void sleepSortAndPrint(final int[] nums) {
        final int[] sortedArray = new int[nums.length];
        final int[] index = {0};

        long startTime = System.currentTimeMillis();

        for (int num : nums) {
            new Thread(() -> {
                try {
                    Thread.sleep(num); // 休眠时间为当前数字的值
                    sortedArray[index[0]++] = num;
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }).start();
        }

        // 等待所有线程完成
        while (index[0] < nums.length) {
            try {
                Thread.sleep(1);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }

        long endTime = System.currentTimeMillis();
        double elapsedTime = (endTime - startTime) / 1000.0;

        System.out.println("排序后的数组: " + Arrays.toString(sortedArray));
        System.out.println("排序耗时（秒）: " + elapsedTime);
    }

    public static void main(String[] args) {
        // 生成一个包含10个随机整数的数组（范围在1到1000之间）
        int[] inputArray = new int[10];
        Random rand = new Random();
        for (int i = 0; i < inputArray.length; i++) {
            inputArray[i] = rand.nextInt(100) + 1;
        }
        System.out.println("原始数组: " + Arrays.toString(inputArray));
        sleepSortAndPrint(inputArray);
    }
}

运行结果：

这两种算法在实际应用中并不常见，但它们以其独特的方式引发了人们的兴趣。猴子排序算法可能是一种“乱序”数据的有趣方式，而睡眠排序算法则是一种富有创意的尝试，尽管并不实际可行。这些算法的目的通常不是为了优化时间或空间复杂度，而是为了娱乐或启发思考。

因此，虽然大多数情况下我们关注最优化算法，但也有一些算法，如猴子排序和睡眠排序，它们不追求传统的效率标准，而是为了不同的目的而存在，让人们在计算领域保持创意和幽默的一面。

你还了解其他有趣的算法吗？欢迎分享并进行探讨。