首页 > 代码库 > 非常无聊——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 }