?? allsorttimecompare.cpp
字號:
// 各種排序算法的實驗比較
//計算不同初始狀態與排序規模下的各種排序算法的運行時間
#include "time.h"
#include "iostream"
#include "stdlib.h"
#include "string.h"
#include "Compare.h"
#include "Node.h"
#include "StraightInsertSorter.h"
#include "ImprovedInsertSorter.h"
#include "BinaryInsertSorter.h"
#include "BubbleSorter.h"
#include "ImprovedBubbleSorter.h"
#include "StraightSelectSorter.h"
#include "ShellSorter.h"
#include "HeapSorter.h"
#include "QuickSorter.h"
#include "ImprovedQuickSorter.h"
#include "TwoWayMergeSorter.h"
#include "ImprovedTwoWayMergeSorter.h"
#include "BucketSorter.h"
#include "RadixSorter.h"
#include "LinkRadixSorter.h"
using namespace std;
char a[3][10]={"隨機","正序","逆序"};
// 設定隨即函數的種子
inline void Randomize()
{ srand(1); }
//返回一個0到n-1之間的隨機數
inline int Random(int n)
{ return rand() % (n); }
// Timing variables and functions
clock_t tstart = 0; // Time at beginning of timed section
// Initialize the program timer
void Settime()
{ tstart = clock(); }
// Return the elapsed time since the last call to Settime
double Gettime()
{ return (double)((double)clock() - (double)tstart)/
(double)CLOCKS_PER_SEC; }
inline void swap(int * array, int x, int y) //交換位置x和y的元素
{
int temp=array[x];
array[x]=array[y];
array[y]=temp;
}
void main()
{
int numofsort; //輸入規模：10, 100 ,1000 ,10000 ,100000 ,1000000
int wayofsort; //排序算法的序號
int flag; //初始數組順序：正序、逆序、隨機順序,其中正序和逆序分別為已排序及逆排序
while(1)
{
Randomize();
cout<<endl;
cout<<" 直接插入排序 1 優化的插入排序 2"<<endl;
cout<<" 二分法插入排序 3 起泡排序 4"<<endl;
cout<<" 優化的起泡排序 5 直接選擇排序 6"<<endl;
cout<<" Shell 排序/2 7 Shell 排序/3 8"<<endl;
cout<<" 快速排序 9 優化的快速排序 10"<<endl;
cout<<" 兩路歸并排序 11 優化的兩路歸并排序 12"<<endl;
cout<<" 堆排序 13 基數排序/2 14"<<endl;
cout<<" 基數排序/4 15 基數排序/8 16"<<endl;
cout<<" 基數排序(隊列實現)/2 17 基數排序(隊列實現)/4 18"<<endl;
cout<<" 基數排序(隊列實現)/8 19 計算所有排序時間 20"<<endl;
cout<<endl;
cout<<"請輸入排序算法的序號(0-退出):";
cin>>wayofsort;
if(wayofsort==0) exit(1);
cout<<"請輸入數組規模:";
cin>>numofsort;
if(numofsort>1000000)
{
cout<<"sorry,數據規模太大!";
exit(1);
}
cout<<"請輸入初始狀態(隨機0 正序1 逆序2):";
cin>>flag;
int allflag=0;
wayofsort--;
if(wayofsort==19)
{
wayofsort=0;
allflag=1;
}
begin:
wayofsort++;
int *sortarray =new int[1000000];
int *temparray =new int[1000000];
//產生隨機數組,長度為1000000
Randomize();
for(int i=0;i<1000000;i++)
sortarray[i]=Random(32003);
//產生正序、逆序數組
if(flag==1||flag==2)
{
//實例化快速排序類
ImprovedQuickSorter<int,Compare> sorter;
sorter.Sort(sortarray,0,1000000-1);
if(flag==2)
{
for(int i=0;i<1000000/2;i++)
swap(sortarray,i,999999-i);
}
}
//開始排序
switch(wayofsort)
{
case 1:
{ //直接插入排序
//實例化直接插入排序類
StraightInsertSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"直接插入排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 2:
{ //改進的插入排序
//實例化優化的插入排序類
ImprovedInsertSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"改進的插入排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 3:
{ //二分法插入排序
//實例化二分法插入排序類
BinaryInsertSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"二分法插入排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 4:
{ //起泡排序
//實例化起泡排序類
BubbleSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"起泡排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 5:
{ //改進的起泡排序
//實例化優化的起泡排序類
ImprovedBubbleSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"改進的起泡排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 6:
{ //直接選擇排序
//實例化直接選擇排序類
StraightSelectSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"直接選擇排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 7:
{//Shell 排序/2
//實例化Shell排序類
ShellSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"Shell 排序/2"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 8:
{//Shell 排序/3
//實例化Shell排序類
ShellSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.delta3Sort(sortarray+numofsort*i,numofsort);
cout<<"Shell 排序/3"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 9:
{ //快速排序
//實例化快速排序類
QuickSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray,0+numofsort*i,numofsort-1+numofsort*i);
cout<<"快速排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 10:
{ //優化的快速排序
//實例化優化的快速排序類
ImprovedQuickSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray,0+numofsort*i,numofsort-1+numofsort*i);
cout<<"優化的快速排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 11:
{ //兩路歸并排序
//實例化兩路歸并排序類
TwoWayMergeSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray,temparray,0+numofsort*i,numofsort-1+numofsort*i);
cout<<"兩路歸并排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 12:
{ //優化的兩路歸并排序
//實例化優化的兩路歸并排序類
ImprovedTwoWayMergeSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray,temparray,0+numofsort*i,numofsort-1+numofsort*i);
cout<<"優化的兩路歸并排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 13:
{ //堆排序
//實例化堆排序類
HeapSorter<int,Compare> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort);
cout<<"堆排序"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 14:
{ //基數排序/2
//實例化基數排序類
RadixSorter<int> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort,16,2);
cout<<"基數排序/2"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 15:
{ //基數排序/4
//實例化基數排序類
RadixSorter<int> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
sorter.Sort(sortarray+numofsort*i,numofsort,8,4);
cout<<"基數排序/4"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 16:
{ //基數排序/8
//實例化基數排序類
RadixSorter<int> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
{
sorter.Sort(sortarray+numofsort*i,numofsort,5,8);
}
cout<<"基數排序/8"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
if(allflag==1)
goto begin;
break;
}
case 17:
{ //基數排序(隊列實現)/2
Node* sortarray1=new Node[1000000];
for(int ii=0;ii<1000000;ii++)
sortarray1[ii].key=sortarray[ii];
//實例化基于靜態鏈的基數排序類
LinkRadixSorter<Node> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
{
sorter.Sort(sortarray1+numofsort*i,numofsort,16,2);
}
cout<<"基數排序(隊列實現)/2"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
delete[] sortarray1;
if(allflag==1)
goto begin;
break;
}
case 18:
{ //基數排序(隊列實現)/4
Node* sortarray1=new Node[1000000];
for(int ii=0;ii<1000000;ii++)
sortarray1[ii].key=sortarray[ii];
//實例化基于靜態鏈的基數排序類
LinkRadixSorter<Node> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
{
sorter.Sort(sortarray1+numofsort*i,numofsort,8,4);
}
cout<<"基數排序(隊列實現)/4"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
delete[] sortarray1;
if(allflag==1)
goto begin;
break;
}
case 19:
{ //基數排序(隊列實現)/8
Node* sortarray1=new Node[1000000];
for(int ii=0;ii<1000000;ii++)
sortarray1[ii].key=sortarray[ii];
//實例化基于靜態鏈的基數排序類
LinkRadixSorter<Node> sorter;
Settime();
for(int i=0;i<1000000/numofsort;i++)
{
sorter.Sort(sortarray1+numofsort*i,numofsort,5,8);
}
cout<<"基數排序(隊列實現)/8"<<endl
<<"排序規模:"<<numofsort<<endl<<"初始狀態："<<a[flag]<<endl
<<Gettime()/1000000*numofsort<<"seconds"<<endl;
delete[] sortarray;
delete[] sortarray1;
if(allflag==1)
goto begin;
break;
}
}
}//end while
}
?? 快捷鍵說明
復制代碼
Ctrl + C
搜索代碼
Ctrl + F
全屏模式
F11
切換主題
Ctrl + Shift + D
顯示快捷鍵
?
增大字號
Ctrl + =
減小字號
Ctrl + -