08/02/29 01:11:21
>>482
全文字列を展開してソートした場合
#include <iostream>
#include <string>
#include <set>
#include <time.h>
using namespace std;
class gou{
public: string str; int num;
gou(string a, int b){str=a; num=b;}
bool operator<(const gou& a)const{return str<a.str;}};
main(){
int sz=20000,n;
string a(sz,'\0');
for(n=0;n<sz;n++)a[n]=rand()&255;
multiset<gou> s;
int cl=clock();
for(n=0;n<sz;n++){ s.insert(gou(a,n)); a=a.substr(1)+a[0];}
cl=clock()-cl; cout<<"20kのブロックーソート "<<(cl+0.0)/1000<<"sec \n";
}