在计算机科学中，Bogo排序（bogo-sort）是个非常低效率的排序算法，通常用在教学或测试。其原理等同将一堆卡片抛起，落在桌上后检查卡片是否已整齐排列好，若非就再抛一次。其名字源自Quantum bogodynamics，又称bozo sort、blort sort或猴子排序（参见无限猴子定理）。
以下是伪代码：
function bogosort(arr) while arr is not ordered arr := 隨機排列(arr)
首页 >
Bogo排序
✍ dations ◷ 2025-06-07 02:19:08 #Bogo排序
其平均时间复杂度是 O(n × n!)，在最坏情况所需时间是无限。它并非一个稳定的算法。
#include <stdio.h>#include <stdlib.h>#include <time.h> void swap(void *a, void *b) { unsigned char *p = a; unsigned char *q = b; unsigned char tmp; tmp = *p; *p = *q; *q = tmp; }/*洗牌函數*/void shuffle(void *x, int size_elem, int total_elem) { int i = total_elem - 1; for(i ; i >= 0; --i) { int r = rand() % (i+1); swap(x + r*size_elem, x + i*size_elem); } }int main(int argc, char *argv) { /*為了洗牌而需要隨機化函數，此處的函數具有偽隨機性*/ srand((unsigned)time(NULL)); int l = {5,2,1,3,4}; int n; n = sizeof(l)/sizeof(l); /*先設陣列未排序=0,已排序=1*/ int isSort = 0; int i; while(!isSort) { /*進行洗牌動作*/ /*等同於從搖獎機或籤筒裡依序抽出n個數*/ shuffle(l, sizeof(l), n); isSort = 1; /*檢查從搖獎機或籤筒裡所抽出來的數是否比前一個數還大*/ for(i = 0; i < n-1; i++) { if (l > l) {/*若較大的陣列編號的值比較小時則重新洗牌*/ isSort = 0; break; } } }}from random import shufflefrom itertools import izip, teedef 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)
，期望的位置交换次数渐近
。 期望的位置交换次数增长地比期望比较次数快，是因为只需要比较几对元素就能发现元素是无序的，但是随机地打乱顺序所需要的交换次数却与数据长度成比例。在最差的情况下，交换和比较次数都是无限的，这就像随机投掷硬币可能连续任意次正面向上。
。