算法实现/排序/随机排序
随机排序（也称为随机排序、散弹排序或猴子排序）是一种特别无效的排序算法。它唯一的作用是用于教育目的，将其与其他更现实的算法进行对比。如果随机排序被用来对一副牌进行排序，它将包括检查这副牌是否按顺序排列，如果不是，就会把这副牌扔到空中，随机捡起卡片，然后重复这个过程，直到这副牌排序完成。它的名字来源于单词bogus。
以下是用伪代码描述的算法。
while not inOrder(deck) do
shuffle(deck);
#include <iostream>
#include <ctime>
#include <cstdlib>
#include <vector>
#include <algorithm>
#include <iterator>
using namespace std;
static const int NUM = 7;
bool IsInOrder(const vector<int>& x) {
return adjacent_find(x.begin(), x.end(), greater<int>()) == x.end();
}
int main() {
int counter = 0;
srand(time(0));
vector<int> bogo;
// Initiate the vector with NUM random numbers
generate_n(back_inserter(bogo), NUM, rand);
// Bogosort
while(!IsInOrder(bogo)) {
random_shuffle(bogo.begin(), bogo.end());
copy(bogo.begin(), bogo.end(), ostream_iterator<int>(cout, " "));
cout << "\n\n";
counter++;
}
cout << "Sorting took " << counter << " tries." << endl;
}
import java.util.*;
public void bogoSort(List<Integer> deck) {
while(!isInOrder(deck)) {
Collections.shuffle(deck);
}
}
public boolean isInOrder(List<Integer> deck) {
for (int i = 0; i < deck.size() - 1; i++) {
if (deck.get(i) > deck.get(i+1)) return false;
}
return true;
}
function is_sorted(t)
local last_v = t[1]
local current_v
for i = 2, #t do
current_v = t[i]
if last_v > current_v then
return false
end
last_v = current_v
end
return true -- if the length of the table is 1, it will return as if it is sorted
end
function bogosort(t)
while not is_sorted(t) do
local nt = {t[1]}
for i = 2, #t do
table.insert(nt, math.random(1, #nt), t[i])
end
t = nt
end
return t
end
use List::Util qw{shuffle};
sub inorder (&@) {
my $sub = shift;
while (scalar(@_) > 1) {
return unless ( $sub->(shift, $_[0]) )
}
return 1;
}
my @list = (1, 2, 3, 4, 5, 6);
@list = do { shuffle @list } until inorder { $_[0] <= $_[1] } @list;
或者，对于一副牌
use List::Util qw{shuffle};
sub inorder (&@) {
my $sub = shift;
while (scalar(@_) > 1) {
return unless ( $sub->(shift, $_[0]) )
}
return 1;
}
my @list = qw{2 3 4 5 6 7 8 9 A J K Q};
@list = do { shuffle @list } until inorder { $_[0] le $_[1] } @list;
my @list = 1, 2, 3, 4, 5, 6;
@list .= pick(*) until [<=] @list;
或者，对于一副牌
my @deck = <2 3 4 5 6 7 8 9 A J K Q>;
@deck .= pick(*) until [le] @deck;
from random import *
from time import *
seed()
valeurs = []
for i in range(0, 10):
valeurs.append(randint(0, 100))
def inorder(valeurs):
i = 0
j = len(valeurs)
while i + 1 < j:
if valeurs[i] > valeurs[i + 1]:
return(False)
i += 1
return(True)
def bogo(valeurs):
while not inorder(valeurs):
shuffle(valeurs)
return valeurs
start = time()
print("Before: ", valeurs)
valeurs = bogo(valeurs)
print("After: ", valeurs)
print("%.2f seconds" % (time() - start))
class Array
def bogosort!
shuffle! until sorted?
end
def sorted?
each_cons(2).all? { |a,b| a <= b }
end
end
(define (bogosort to-sort)
(cond
((list? to-sort) (vector->list (bogosort (list->vector to-sort))))
((sorted? to-sort) to-sort)
(else (bogosort (shuffle to-sort)))))
(define (sorted? to-sort)
(define (check-index-and-next n)
(or (>= n (- (vector-length to-sort) 1))
(and (<= (vector-ref to-sort n) (vector-ref to-sort (+ 1 n)))
(check-index-and-next (+ n 1)))))
(check-index-and-next 0))
(define (shuffle deck)
(define (set-index-to-random n)
(if (< n 1)
deck
(begin
(let ((rand (random (+ 1 n)))
(val-at-n (vector-ref deck n)))
(vector-set! deck n (vector-ref deck rand))
(vector-set! deck rand val-at-n))
(set-index-to-random (- n 1)))))
(set-index-to-random (- (vector-length deck) 1)))
|deck|
deck := (1 to:10) asArray randomShuffle.
[ deck isSorted ] whileFalse:[
deck randomShuffle
]
在 C++ 中还有各种其他实现，包括一个STL风格的算法，它源于 ACCU General 邮件列表中的讨论。
- H. Gruber, M. Holzer 和 O. Ruepp: 排序的慢速方式：对反常的糟糕随机排序算法的分析，第四届算法乐趣国际会议，意大利卡斯蒂利亚切洛，2007 年，计算机科学讲义 4475，第 183-197 页。
- Jargon File 中的“bogo-sort”条目，“典型的反常的糟糕算法”
- http://c2.com/cgi/wiki?BogoSort
- 随机排序：一种在类 Unix 系统上运行的实现，类似于标准排序程序。
- 随机排序 和 jmmcg::bogosort：随机排序算法的简单而反常的 C++ 实现。