各種ソートアルゴリズムの効率比較
4847 ワード
(1)本明細書には、発泡アルゴリズム、速排アルゴリズム、挿入ソートアルゴリズムなどが含まれる.乱数によって彼らの前の効率を比較する.
(2)自分で手動で実現した簡単なアルゴリズムの泡立ちと速排はシステムが持参したアルゴリズムと比較し、システムが持参したのは容器向けであるため、全体的に自分が簡単に実現したよりも効率が高いが、基本的には1桁である.
(3)初めてこのように縦方向の比较的に自分で手动的に书いたコード、やはり少し兴奋して、足りないところ、各位に指摘してもらいます.
(4)私も幼稚ですよ...
(2)自分で手動で実現した簡単なアルゴリズムの泡立ちと速排はシステムが持参したアルゴリズムと比較し、システムが持参したのは容器向けであるため、全体的に自分が簡単に実現したよりも効率が高いが、基本的には1桁である.
(3)初めてこのように縦方向の比较的に自分で手动的に书いたコード、やはり少し兴奋して、足りないところ、各位に指摘してもらいます.
(4)私も幼稚ですよ...
/*
//use stl
#include <iostream>
#include <algorithm>
#include <functional>
using namespace std;
//use c qsort
#include <cstdlib>
//clock
#include <ctime>
struct mytype{
int key;
int data;
};
struct mygen{
//typedef
mytype operator() (void) const {
mytype v;
v.key=rand();
return v;
}
};
struct stl_cmp:public binary_function<mytype,mytype,bool>{
bool operator() (const mytype& e1,const mytype& e2) const { return e1.key<e2.
key; }
};
static int qsort_cmp(const void* e1,const void* e2)
{
return (*(mytype*)e1).key-(*(mytype*)e2).key;
}
mytype a[10000000];
int main(int argc, char* argv[])
{
//stl sort
clock_t t;
generate(a, a+sizeof(a)/sizeof(a[0]), mygen());
t=clock();
sort(a,a+sizeof(a)/sizeof(a[0]),stl_cmp());
t=clock()-t;
cout<<"stl sort cost "<<t*1.0/CLK_TCK<<" seconds"<<endl;
//c qsort
generate(a, a+sizeof(a)/sizeof(a[0]), mygen());
t=clock();
qsort((void*)a,sizeof(a)/sizeof(a[0]),sizeof(a[0]),qsort_cmp);
t=clock()-t;
//cout<<"c qsort cost "<<t*1.0/CLK_TCK<<" seconds"<<endl;
cout<<"c qsort cost "<<(double)t/CLOCKS_PER_SEC<<" seconds"<<endl;
return 0;
} // c qsort() c++ sort() , 。
*/
/*
clock() , 。 TC2.0 18.2 ,
VC++6.0 1000 。
typedef long clock_t;
#define CLK_TCK 18.2
VC++6.0 CLOCKS_PER_SEC 。 1000。
#define CLOCKS_PER_SEC 1000
VC6.0 CLK_TCK 18.2, 1000。
*/
#include <iostream>
#include <ctime>
#include <cstdlib> //rand()
#include <algorithm> //sort()
using namespace std;
const int N = 100000;
struct data{
int key;
int num;
};
struct data a[N],b[N],c[N],d[N];
//bool quick_cmp(const void *a, const void *b) //bool
int quick_cmp(const void *a, const void *b)
{
//if( (*(data*)a).key > (*(data*)b).key)
// return true;
// return false;
return (*(data*)a).key - (*(data*)b).key;
}// sort , sort() 。 qsort() cmp 。
bool stl_cmp(const data &a, const data &b)
{
if( a.key > b.key)
return true;
return false;
}// 。
void BubSort(data a[],int n)
{
int flag,i,j;
int temp;
for (i=0;i<n;i++)//
{
flag = 0;
for (j=n-1;j>i;j--)
{
if (a[j].key<a[j-1].key)
{
temp = a[j].key;
a[j].key = a[j-1].key;
a[j-1].key = temp;
flag = 1;
}
}
if (flag == 0)
break;
}
}
int quicksort(data b[], int left, int right)//
{
if(left < right)
{
int key = b[left].key;
int low = left;
int high = right;
while(low < high)
{
while(low < high && b[high].key >= key)
{
high--;
}
b[low].key = b[high].key;// key ( low = high ),
// 。
while(low < high && b[low].key <= key)
{
low++;
}
b[high].key = b[low].key;// key ( low = high ),
// ……( : key , ; , )。
}
b[low].key = key;
quicksort(b,left,low-1);
quicksort(b,high+1,right);
}
return 0;
}
int main()
{
int i;
clock_t t_start,t_end;
for (i=0;i<N;i++)
{
a[i].key = rand();
b[i].key = a[i].key;
c[i].key = a[i].key;
d[i].key = a[i].key;
//cout << a[i].key<<" ";
}
t_start = clock();
BubSort(a,N);
t_end = clock();
cout << " " << N << " :" << (double)(t_end - t_start)/CLOCKS_PER_SEC << " " << endl;
//for ( i=0;i<N;i++)
// cout << a[i].key << " ";
cout << endl << endl;
t_start = clock();
//sort(c,c+sizeof(c)/sizeof(c[0]),cmp);
sort(c,c+N,stl_cmp);
t_end = clock();
cout << " " << N << " stl::sort() :" << (double)(t_end - t_start)/CLOCKS_PER_SEC << " " << endl;
t_start = clock();
quicksort(b,0,N-1);// N-1, 。
t_end = clock();
cout << " " << N << " :" << (double)(t_end - t_start)/CLOCKS_PER_SEC << " " << endl;
//for ( i=0;i<N;i++)
// cout << b[i].key << " ";
t_start = clock();
qsort(d,N,sizeof(d[0]),quick_cmp);
t_end = clock();
cout << " " << N << " c qsort() :" << (double)(t_end - t_start)/CLOCKS_PER_SEC << " " << endl;
cout << endl << "successfully"<<endl;
return 0;
}