非常无聊——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啊。。。

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

 #include <cmath>

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 struct num

 {

     int data;

     num* next;

 }nu[];

 void plu(num *f,num *b)

 {

     f->next=b;

 }

 num* t[];

 num* e[];

 void add(int pos,num* l)

 {

     if (e[pos])

     {

         e[pos]->next=l;

         e[pos]=l;

     }

     else

     {

         t[pos]=l;

         e[pos]=l;

     }

 }

 int predo()

 {

     int n,ret=;

     scanf("%d",&n);

     for (int i=;i<=n;++i)

     {

         int j;

         scanf("%d",&j);

         nu[i].data=j;

         nu[i].next=nu+i+;

         if (i==n) nu[i].next=NULL;

         ret=max(ret,j);

     }

     return ret;

 }

 num* root=nu+;

 void JSsort(int n)

 {

     for (num* now=root;now;)

     {

         num* nex=now->next;

         now->next=NULL;

         int tt=now->data%n;

         add(tt,now);

         now=nex;

     }

     num* last=NULL;

     for (int i=;i<n;++i)

     {

         if (t[i])

         {

             if (!last)

             {

                 root=t[i];

             }

             else

             {

                 last->next=t[i];

             }

             for (num *now=t[i];now;now=now->next)

                 last=now;

         }

         t[i]=e[i]=NULL;

     }

     for (num* now=root;now;)

     {

         num* nex=now->next;

         now->next=NULL;

         int tt=now->data/n;

         add(tt,now);

         now=nex;

     }

     last=NULL;

     for (int i=;i<n;++i)

     {

         if (t[i])

         {

             if (!last)

             {

                 root=t[i];

             }

             else

             {

                 last->next=t[i];

             }

             for (num *now=t[i];now;now=now->next)

                 last=now;

         }

     }

     return;

 }

 void print()

 {

     for (num* now=root;now;now=now->next)

     {

         printf("%d ",now->data);

     }

     printf("\n");

     return;

 }

 int main()

 {

     freopen ("sort.in","r",stdin);

     freopen ("sort.out","w",stdout);

     int k=predo();

     JSsort(sqrt(k)+);

     print();

     return ;

 }

巴特西

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

最新文章

热门文章