欢迎您来到芯片的主页!

Welcome to Chipset's homepage!

bogo_sort (名副其实最慢的的排序)

一直追求的目标是写出高效低内存消耗的程序,时间久了觉得换个方向了,呵呵。就拿排序试试吧。
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_

 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] = { 2514 };
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 

posted on 2012-01-10 13:10 Chipset 阅读(2299) 评论(2)  编辑 收藏 引用 所属分类: 算法和数据结构消遣

Feedback

# re: bogo_sort (名副其实最慢的的排序)[未登录] 2012-01-11 20:09 kkk

为啥要研究这个。。。  回复  更多评论   

# re: bogo_sort (名副其实最慢的的排序) 2012-12-17 20:30 Mobile Development company

This is a typical sorting program which has a better effeciency than other sorting algorithms like bubble sort  回复  更多评论   


只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理