首页 > 代码库 > 非常无聊——STD::sort VS 基数排序

非常无聊——STD::sort VS 基数排序

  众所周知,Std::sort()是一个非常快速的排序算法,它基于快排,但又有所修改。一般来说用它就挺快的了,代码一行,时间复杂度O(nlogn)(难道不是大叫一声“老子要排序!!”就排好了么。。。)。我们也知道,不基于比较的排序可以达到O(n),比如说基数排序。什么,它是O(n * log(10)( max(n) ) ) 的?NO!!我们可以用sqrt(max(n))来作为进制,这样就是(N*logMax(n))=O(2*n)的了。。看起来很不错, 代码量嘛。。。。呵呵

  所谓基数排序,就是做几次筒排,每一位一次,然后拉直,然后继续,时间复杂度O(n),我们来看一下效果吧

  Data1:10^7随机数据

  Data2:10^7不随机,从10^7到0

  Data3:第二个数据每一项除与2,10^7项

  Data4:第一个数据每一项除与2,10^7项

  效果:

  std::sort()

  1.7.07s

  2.5.51s

  3.7.00s

  4.5.31s

  基数排序

  1.5.31s

  2.7.26s

  3.4.89s

  4.7.06s

  觉得很奇怪,其实一四是对应的,二三是对应的。。。然后为什么会这样。。。不懂不懂。。。

  分析一下,可能是读入原因,或者std::sort()对一些特殊的有优化,但是很大可能是——Cena抽了。。。

  基数排序在排序上优化还是挺大的,但是,代码量和常数还有适用范围。。。呵呵

  本文纯粹太无聊作死只做,我不会说std::sort()在评测的时候连续4次75分,每次无输出的点还不一样。。。Cena啊,你何时出1.0啊。。。

  付:我写的基数排序极丑代码。。。

  

  1 #include <cmath>
  2 #include <iostream>
  3 #include <cstdio>
  4 #include <cstdlib>
  5 
  6 using namespace std;
  7 struct num
  8 {
  9     int data;
 10     num* next;
 11 }nu[100000000];
 12 
 13 void plu(num *f,num *b)
 14 {
 15     f->next=b;
 16 }
 17 
 18 num* t[100000];
 19 num* e[100000];
 20 void add(int pos,num* l)
 21 {
 22     if (e[pos])
 23     {
 24         e[pos]->next=l;
 25         e[pos]=l;
 26     }
 27     else
 28     {
 29         t[pos]=l;
 30         e[pos]=l;
 31     }
 32 }
 33 
 34 int predo()
 35 {
 36     int n,ret=0;
 37     scanf("%d",&n);
 38     for (int i=1;i<=n;++i)
 39     {
 40         int j;
 41         scanf("%d",&j);
 42         nu[i].data=http://www.mamicode.com/j;
 43         nu[i].next=nu+i+1;
 44         if (i==n) nu[i].next=NULL;
 45         ret=max(ret,j);
 46     }
 47     return ret;
 48 }
 49 num* root=nu+1;
 50 
 51 void JSsort(int n)
 52 {
 53     for (num* now=root;now;)
 54     {
 55         num* nex=now->next;
 56         now->next=NULL;
 57         int tt=now->data%n;
 58         add(tt,now);
 59         now=nex;
 60     }
 61     num* last=NULL;
 62     for (int i=0;i<n;++i)
 63     {
 64         if (t[i])
 65         {
 66             if (!last)
 67             {
 68                 root=t[i];
 69             }
 70             else
 71             {
 72                 last->next=t[i];
 73             }
 74             for (num *now=t[i];now;now=now->next)
 75                 last=now;
 76         }
 77         t[i]=e[i]=NULL;
 78     }
 79     for (num* now=root;now;)
 80     {
 81         num* nex=now->next;
 82         now->next=NULL;
 83         int tt=now->data/n;
 84         add(tt,now);
 85         now=nex;
 86     }
 87     last=NULL;
 88     for (int i=0;i<n;++i)
 89     {
 90         if (t[i])
 91         {
 92             if (!last)
 93             {
 94                 root=t[i];
 95             }
 96             else
 97             {
 98                 last->next=t[i];
 99             }
100             for (num *now=t[i];now;now=now->next)
101                 last=now;
102         }
103     }
104     return;
105 }
106 
107 void print()
108 {
109     for (num* now=root;now;now=now->next)
110     {
111         printf("%d ",now->data);
112     }
113     printf("\n");
114     return;
115 }
116 
117 int main()
118 {
119     freopen ("sort.in","r",stdin);
120     freopen ("sort.out","w",stdout);    
121     int k=predo();
122     JSsort(sqrt(k)+1);
123     print();
124     return 0;
125 }
View Code