用户工具

站点工具


alogrithm:bogo

Bogo排序算法

Bogo算法定义

下面是维基百科中Bogo算法定义:

在计算机科学中,Bogo排序(bogo-sort)是个既不实用又原始的排序算法,其原理等同将一堆卡片抛起,落在桌上后检查卡片是否已整齐排列好,若非就再抛一次。其名字源自Quantum bogodynamics,又称bozo sort、blort sort或猴子排序。

其实Bogo算法就是随机算法,给出一个序列,随机抽取序列中的元素,组成新的序列,如果序列为有序,则排序成功。

Bogo算法的Python实现

Bogo算法的平均时间复杂度是 O(n × n!),在最坏情况所需时间是无限。它并非一个稳定的算法。

from random import shuffle
from itertools import izip, tee
 
def in_order(my_list):
    """Check if my_list is ordered"""
    it1, it2 = tee(my_list)
    it2.next()
    return all(a<=b for a,b in izip(it1, it2))
 
def bogo_sort(my_list):
    """Bogo-sorts my_list in place."""
    while not in_order(my_list):
        shuffle(my_list)
alogrithm/bogo.txt · 最后更改: 2011/04/07 09:15 (外部编辑)