欢迎您来到芯片的主页!

Welcome to Chipset's homepage!

蜗牛排序--我见过的最慢的排序

鄙人目光短浅,以为见到的这个时间复杂度为O(n!)的排序是最慢的。如果不是,请举出更慢的例子:)

原理是枚举所有排列组合,直到找到一个合适的有序序列,取名蜗牛排序。

使用模板来实现。

 1 template <typename T>
 2 struct greater
 3 {
 4   bool operator()(const T& x, const T& y) const { return y < x; }
 5 };
 6 
 7 template <typename T>
 8 struct less
 9 {
10   bool operator()(const T& x, const T& y) const { return x < y; }
11 };
12 
13 template <typename T>
14 inline void swap(T& x, T& y)
15 {
16     const T tmp(x);
17     x = y;
18     y = tmp;
19 }
20 
21 // reverse a sequence in the range [first, last)
22 template <typename BidirectionalIter>
23 void reverse(BidirectionalIter first, BidirectionalIter last)
24 {
25   while(true)
26     if(first == last || first == --last)
27       return;
28     else
29       swap(*first++*last);
30 }
31 // find the next possible permutation
32 template <typename BidirectionalIter, typename Compare>
33 bool next_permutation(BidirectionalIter first, BidirectionalIter last,
34                                  Compare cmp)
35 {
36   if(first == last)
37     return false;
38   BidirectionalIter i = first;
39   ++i;
40   if(i == last)
41     return false;
42   i = last;
43   --i;
44 
45   for(;;)
46   {
47     BidirectionalIter ii = i;
48     --i;
49     if(cmp(*i, *ii))
50     {
51       BidirectionalIter j = last;
52       while(!cmp(*i, *--j));
53       swap(*i, *j);
54       reverse(ii, last);
55       return true;
56     }
57     if(i == first)
58     {
59       reverse(first, last);
60       return false;
61     }
62   }
63 }
64 
65 template <typename BidirectionalIterator, typename Compare>
66 void snail_sort(BidirectionalIterator first, BidirectionalIterator last, Compare cmp)
67 {
68   while(next_permutation(first, last, cmp));
69 }
70 
71 #include <iostream>
72 
73 int main()
74 {
75     const int SZ = 12;
76     int arr[SZ] = { 539746502138 };
77     snail_sort(arr, arr + SZ, greater<int>());
78     for(int i =0 ; i < SZ; ++i)
79         std::cout << arr[i] << ' ';
80 }

posted on 2011-08-16 12:35 Chipset 阅读(600) 评论(4)  编辑 收藏 引用 所属分类: 算法和数据结构消遣

Feedback

# re: 蜗牛排序--我见过的最慢的排序[未登录] 2011-08-23 15:17 CLJ

有更慢的。
Bogo排序 又称 猴子排序。听过没。时间复杂度,在现代计算机上,很随机,可以是无穷。但确实可以在某一个时刻排好。  回复  更多评论   

# re: 蜗牛排序--我见过的最慢的排序[未登录] 2011-08-23 16:24 Chipset

@CLJ
孤陋寡闻啦,呵呵,第一次听说过猴子排序。  回复  更多评论   

# re: 蜗牛排序--我见过的最慢的排序[未登录] 2012-01-07 11:53 .

大大你错了,还真有比蜗牛排序还要慢的,理论上不知道是否会收敛的猴子排序算法.  回复  更多评论   

# re: 蜗牛排序--我见过的最慢的排序 2012-01-10 10:21 Chipset

@.
猴子排序理论上最坏情况下时间复杂度为无穷大,最好情况为O(n),一般情况为O(n*n!)。可见确实比我的蜗牛排序慢。

猴子排序伪代码如下:
while (没有排好序)
打乱当前序列的顺序;  回复  更多评论   


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