bogo_sort (名副其实最慢的的排序)
Chipset发表于 2012-01-10 05:10:00
一直追求的目标是写出高效低内存消耗的程序，时间久了觉得换个方向了，呵呵。就拿排序试试吧。
bogo sort又称stupid sort或slow sort，我觉得应该是最慢的排序算法了吧，至少理论上比蜗牛排序(本主页有介绍)慢。
该排序算法的思想是对于一个给定的序列，随机的生成各种可能的序列，直到遇到某个序列有序为止。时间复杂度最好情况下是O(n)，最坏情况下是无穷大，一般情况是O(n*n!)，可见相当的恐怖。看代码就明白了。
bogo sort又称stupid sort或slow sort，我觉得应该是最慢的排序算法了吧，至少理论上比蜗牛排序(本主页有介绍)慢。
该排序算法的思想是对于一个给定的序列，随机的生成各种可能的序列，直到遇到某个序列有序为止。时间复杂度最好情况下是O(n)，最坏情况下是无穷大，一般情况是O(n*n!)，可见相当的恐怖。看代码就明白了。
1 // bogo_sort.hpp
2 #ifndef BOGO_SORT_HPP_
3 #define BOGO_SORT_HPP_
4
5 template <typename ForwardIterator, typename Compare>
6 bool is_sorted(ForwardIterator first, ForwardIterator last, Compare cmp)
7 {
8 if (first == last)
9 return true;
10 ForwardIterator next = first;
11 for(++next; next != last; first = next, ++next)
12 if(cmp(*next, *first))
13 return false;
14 return true;
15 }
16
17 template <typename T>
18 inline void swap(T& x, T& y)
19 {
20 const T tmp(x);
21 x = y;
22 y = tmp;
23 }
24
25 template <typename RandomIterator, typename RandomGen>
26 void shuffle(RandomIterator first, RandomIterator last, RandomGen gen)
27 {
28 unsigned long d = last - first;
29 if(d < 2)
30 return;
31 for(RandomIterator it = first; first != last; ++first)
32 swap(*(it + gen()%d), *first);
33 }
34
35 #include "random.hpp"
36
37 template <typename RandomIterator, typename Compare>
38 void bogo_sort(RandomIterator first, RandomIterator last, Compare cmp)
39 {
40 while(!is_sorted(first, last, cmp))
41 shuffle(first, last, random());
42 }
43
44 #endif
45
46 // random.hpp
47 #ifndef RANDOM_HPP_
48 #define RANDOM_HPP_
49 #include <ctime>
50
51 class random
52 {
53 private:
54 typedef unsigned long UInt32; // 如果你的编译器不认识uint32_t，就用unsigned long代替
55 UInt32 a;
56 UInt32 b;
57 UInt32 c;
58 UInt32 d;
59
60 UInt32 randomize()
61 {
62 UInt32 e = a - ((b << 27) | (b >> 5));
63 a = b ^ ((c << 17) | (c >> 15));
64 b = c + d;
65 c = d + e;
66 d = e + a;
67 return d;
68 }
69
70 void init()
71 {
72 for(UInt32 i = 0; i < 20; ++i)
73 randomize();
74 }
75
76 public:
77 explicit random(UInt32 s = std::time(0)) : a(4058668781ul), b(s), c(s), d(s)
78 {
79 init();
80 }
81
82 void reset(UInt32 s = 0)
83 {
84 if(0 == s)
85 s = std::time(0);
86 a = 4058668781ul;
87 b = c = d = s;
88 init();
89 }
90
91 UInt32 rand()
92 {
93 //returns a random integer in the range [0, 4294967296)
94 return randomize();
95 }
96
97 double real()
98 {
99 //returns a random real number in the range [0.0, 1.0)
100 return randomize() / 4294967296.0;
101 }
102
103 UInt32 operator()() { return rand(); }
104 };
105
106 #endif // RANDOM_HPP_
2 #ifndef BOGO_SORT_HPP_
3 #define BOGO_SORT_HPP_
4
5 template <typename ForwardIterator, typename Compare>
6 bool is_sorted(ForwardIterator first, ForwardIterator last, Compare cmp)
7 {
8 if (first == last)
9 return true;
10 ForwardIterator next = first;
11 for(++next; next != last; first = next, ++next)
12 if(cmp(*next, *first))
13 return false;
14 return true;
15 }
16
17 template <typename T>
18 inline void swap(T& x, T& y)
19 {
20 const T tmp(x);
21 x = y;
22 y = tmp;
23 }
24
25 template <typename RandomIterator, typename RandomGen>
26 void shuffle(RandomIterator first, RandomIterator last, RandomGen gen)
27 {
28 unsigned long d = last - first;
29 if(d < 2)
30 return;
31 for(RandomIterator it = first; first != last; ++first)
32 swap(*(it + gen()%d), *first);
33 }
34
35 #include "random.hpp"
36
37 template <typename RandomIterator, typename Compare>
38 void bogo_sort(RandomIterator first, RandomIterator last, Compare cmp)
39 {
40 while(!is_sorted(first, last, cmp))
41 shuffle(first, last, random());
42 }
43
44 #endif
45
46 // random.hpp
47 #ifndef RANDOM_HPP_
48 #define RANDOM_HPP_
49 #include <ctime>
50
51 class random
52 {
53 private:
54 typedef unsigned long UInt32; // 如果你的编译器不认识uint32_t，就用unsigned long代替
55 UInt32 a;
56 UInt32 b;
57 UInt32 c;
58 UInt32 d;
59
60 UInt32 randomize()
61 {
62 UInt32 e = a - ((b << 27) | (b >> 5));
63 a = b ^ ((c << 17) | (c >> 15));
64 b = c + d;
65 c = d + e;
66 d = e + a;
67 return d;
68 }
69
70 void init()
71 {
72 for(UInt32 i = 0; i < 20; ++i)
73 randomize();
74 }
75
76 public:
77 explicit random(UInt32 s = std::time(0)) : a(4058668781ul), b(s), c(s), d(s)
78 {
79 init();
80 }
81
82 void reset(UInt32 s = 0)
83 {
84 if(0 == s)
85 s = std::time(0);
86 a = 4058668781ul;
87 b = c = d = s;
88 init();
89 }
90
91 UInt32 rand()
92 {
93 //returns a random integer in the range [0, 4294967296)
94 return randomize();
95 }
96
97 double real()
98 {
99 //returns a random real number in the range [0.0, 1.0)
100 return randomize() / 4294967296.0;
101 }
102
103 UInt32 operator()() { return rand(); }
104 };
105
106 #endif // RANDOM_HPP_
1 // main.cpp
2 #include "bogo_sort.hpp"
3 #include <iostream>
4
5 template <typename T>
6 struct greater
7 {
8 bool operator ()(const T& x, const T& y) const { return y < x; }
9 };
10
11 int main()
12 {
13 const int LEN = 4;
14 int arr[LEN] = { 2, 5, 1, 4 };
15 while(!is_sorted(arr, arr + LEN, greater<int>())) // 就来个从大到小的顺序吧
16 shuffle(arr, arr + LEN, random());
17 for(int i = 0; i < LEN; ++i) // 序列这么短，输出看看就行
18 std::cout << arr[i] << ' ';
19
20 return 0;
21 }
22
2 #include "bogo_sort.hpp"
3 #include <iostream>
4
5 template <typename T>
6 struct greater
7 {
8 bool operator ()(const T& x, const T& y) const { return y < x; }
9 };
10
11 int main()
12 {
13 const int LEN = 4;
14 int arr[LEN] = { 2, 5, 1, 4 };
15 while(!is_sorted(arr, arr + LEN, greater<int>())) // 就来个从大到小的顺序吧
16 shuffle(arr, arr + LEN, random());
17 for(int i = 0; i < LEN; ++i) // 序列这么短，输出看看就行
18 std::cout << arr[i] << ' ';
19
20 return 0;
21 }
22