沙雕排序算法之猴子排序、睡眠排序
你好，我是测试蔡坨坨。
当谈到算法时，通常人们会追求最优解，而最优解的评判标准主要考虑时间复杂度和空间复杂度，因为较低的复杂度通常代表着更优秀的算法。然而，有一些有趣的例外，即那些非传统的算法，如猴子排序（Monkey Sort）和睡眠排序（Sleep Sort），都是一些令人忍俊不禁的例子，尽管它们并不实用，但它们都引发了人们的兴趣和好奇心。
本篇将详细探讨这两种算法。
猴子排序算法
在一本1909年出版谈概率的书籍中，埃米尔·博雷尔提出了无限猴子定理，其中介绍了“打字的猴子”的概念。
故事情节
很久以前，有一个猴子叫做查尔斯，他生活在一个巨大的图书馆里。这个图书馆里有数以亿计的书籍和打字机，包含了所有可能的字母、数字和标点符号。查尔斯对打字机产生了浓厚的兴趣。
有一天，查尔斯突然站在了一台打字机前。虽然他并不知道如何打字，但他开始随机地按下键盘上的键。他的动作毫无规律，就像是瞎猜一样。
人们会好奇地想知道，如果查尔斯一直随机地按键，是否有一天他能够打出莎士比亚的某一部作品，比如《哈姆雷特》呢？或者打出一本完整的百科全书？
这个故事用来探讨概率和无序事件的概念。理论上，查尔斯确实有可能在某一刻随机地按键，打出一部文学作品或其他文字。然而，由于随机性极高，要实现这一点所需要的时间几乎是不可想象的。这个思考实验强调了概率事件的稀有性和随机性，以及在实际情况下，某些事件可能需要极长的时间才能发生。
真猴子实验
为了验证这一理论的真实性，2003年，英国一所大学的师生从学校里拿了两千欧元的科研经费，给动物园的猴子买了一台电脑和一个键盘。然而结果并不尽人意，在一个月的相处时间里，猴子除了胡乱敲键盘外，剩下的时间便是在电脑上进行大小便，最终导致电脑无法正常运行，实验宣告失败。
程序模拟猴子敲键盘
后来有人尝试用计算机程序来模拟猴子敲击键盘，最终在花费了 421625*10^23 年后，终于打出了莎士比亚的前十九个字母VALENTINE.Cease to。
猴子排序算法
基于上述理论，便可以得到猴子排序算法，也被称为猴子补丁排序（BogoSort）。对于要排序的数组，每一次给它进行一个随机的排序，那么总有一次，它能够变成一个有序的数组，如果运气好，可能一次就搞定（一次成功的幸运猴，时间复杂度就是O(N)，Perfect！），如果运气不好，可能一直都不会成功（永不成功猴，时间复杂度就是INF）。
Python代码实现
# 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、自己写一个方法；方法2、使用Collections.shuffle()
由于Collections.shuffle(List<?> list)需接收一个List参数，因此可以使用guava（瓜瓦），Google提供的api Ints.asList(int... backingArray)将int数组转成list。
<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>23.0</version>
</dependency>
判断数组是否按顺序排序
具体代码：
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代码实现
# 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代码实现
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到100之间）
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);
}
}
运行结果：
这两种算法在实际应用中并不常见，但它们以其独特的方式引发了人们的兴趣。猴子排序算法可能是一种“乱序”数据的有趣方式，而睡眠排序算法则是一种富有创意的尝试，尽管并不实际可行。这些算法的目的通常不是为了优化时间或空间复杂度，而是为了娱乐或启发思考。
因此，虽然大多数情况下我们关注最优化算法，但也有一些算法，如猴子排序和睡眠排序，它们不追求传统的效率标准，而是为了不同的目的而存在，让人们在计算领域保持创意和幽默的一面。
你还了解其他有趣的算法吗？欢迎分享并进行探讨。
以上，完。