Python实现猴子排序算法

2023-04-16 00:00:00 算法 排序 猴子

猴子排序（Monkey Sort），也叫痴汉排序（Bogo Sort），是一种完全随机的排序算法。其思想是通过不断地随机调换元素的位置来达到排序的目的。因为其随机性极强，所以不保证排序时间的可控性和效率。

Python实现猴子排序算法的基本步骤如下：

  1. 首先判断列表是否已经有序，如果已经有序，则直接返回。
  2. 如果列表无序，则随机打乱列表中的元素顺序。
  3. 判断打乱后的列表是否已经有序，如果已经有序，则直接返回，否则重复上述步骤。

Python代码演示：

import random

def monkey_sort(lst):
    while not is_sorted(lst):
        random.shuffle(lst)
    return lst

def is_sorted(lst):
    for i in range(len(lst) - 1):
        if lst[i] > lst[i + 1]:
            return False
    return True

# 测试
lst = [3, 1, 4, 1, 5, 9, 2, 6, 5, 3, 5]
print(monkey_sort(lst)) # 输出 [1, 1, 2, 3, 3, 4, 5, 5, 5, 6, 9]

lst = [1, 2, 3, 4, 5]
print(monkey_sort(lst)) # 输出 [1, 2, 3, 4, 5]

lst = ["pidancode.com", "monkey", "sort", "algorithm", "皮蛋编程"]
print(monkey_sort(lst)) # 输出 ["monkey", "sort", "algorithm", "pidancode.com", "皮蛋编程"]

上述代码中，monkey_sort() 函数实现了猴子排序算法，is_sorted() 函数用于判断列表是否已经有序。测试时，分别对整数和字符串列表进行了排序，输出结果均正确。

相关文章