也谈慢速排序~

每天都在思考如何更好的增加程序的效率，但是今天我们讨论下如何让程序效率变的低下，或者说是极度低下~本慢速排序算法的思想是对于一个给定的序列，随机的生成各种可能的序列，直到遇到某个序列有序为止。时间复杂度最好情况下是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_

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

Xushine

484