学步园

bogo是排序算法中的异类，它的原理非常简单，检查序列是否已经有序，如果有序就完成排序，否则打乱需要序列的顺序并重新执行判断，下面给出这个算法的实现。

/* 打乱数组的顺序 */<br /> void suffle(int *arr, int size)<br /> {<br /> int i, r, t;<br /> for (i = 0; i < size - 1; i++)<br /> {<br /> r = rand() % (size - i);<br /> t = arr[i];<br /> arr[i] = arr[r + i];<br /> arr[r + i] = t;<br /> }<br /> }<br /> /* 排序过程 */<br /> void bogoSort(int *arr, int size)<br /> {<br /> int i;<br /> int flag;<br /> srand((unsigned int)time(NULL));<br /> while(1)<br /> {<br /> flag = 0;<br /> for (i = 0; i < size - 1; i++)<br /> {<br /> if (arr[i] > arr[i + 1])<br /> {<br /> flag = 1;<br /> break;<br /> }<br /> }<br /> if (!flag) return;<br /> suffle(arr, size);<br /> }<br /> } 

还有一种类似的算法叫Bozo排序，排序的原理依然很简单，检查是否是有序的，如果有序就完成排序否则随机将序列中两个数交换。

/* 随机交换序列中的两个数 */<br /> void randomSwap(int *arr, int size)<br /> {<br /> int r1 = rand() % size;<br /> int r2 = (r1 + 1 + rand() % (size - 1)) % size;<br /> int t = arr[r1];<br /> arr[r1] = arr[r2];<br /> arr[r2] = t;<br /> }<br /> /* 排序过程 */<br /> void bozoSort(int *arr, int size)<br /> {<br /> int i;<br /> int flag;<br /> srand((unsigned int)time(NULL));<br /> while(1)<br /> {<br /> flag = 0;<br /> for (i = 0; i < size - 1; i++)<br /> {<br /> if (arr[i] > arr[i + 1])<br /> {<br /> flag = 1;<br /> break;<br /> }<br /> }<br /> if (!flag) return;<br /> randomSwap(arr, size);<br /> }<br /> } 

这两种排序方法运气好的话比较size - 1次就可以完成，运气不好的话永远都不会出结果。