排序算法在不同数组状态下时间复杂度的比较

#include <windows.h> #include <stdio.h> #include <iostream> #include <time.h> #include <iomanip> #include "Quick.h" #include "Merge.h" #include "Heap.h" #include "Insertion.h" #include "Selection.h" //#include "Sort.h" using namespace std; #define MAXINT 32767 //最大的int，不能超过这个数 int sortarray[1000000]; //产生随机数组,长度为1000000 int temparray[1000000]; //保存随机数组,保证各种排序算法的数组对象相同 char a[3][10]={"随机","正序","逆序"}; int temp; inline void Randomize() { srand(time(0)); } clock_t tstart = 0; clock_t tend = 0; void Settime() { tstart = clock(); } double Gettime() { tend = clock(); return double(tend - tstart)/CLOCKS_PER_SEC; } void main() { int NUM; //输入规模 int flag; //初始数组顺序：随机顺序、正序、逆序 double time[5] = {0,0,0,0,0}; //用来记录每个算法的平均时间 while(1) { system("cls"); cout << "\n\t┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl; cout << "\t┃ 排序算法的数值比较 ┃"<<endl; cout << "\t┃ 快速排序 ┃"<<endl; cout << "\t┃ 插入排序 ┃"<<endl; cout << "\t┃ 选择排序 ┃"<<endl; cout << "\t┃ 归并排序 ┃"<<endl; cout << "\t┃ 堆排序 ┃"<<endl; cout << "\t┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; cout<<"请输入数组初始状态(随机0 正序1 逆序2):"; cin>>flag; cout << endl; cout << "\t-----------------------------------------\n" << endl; for(NUM=10000;NUM<=100000;NUM +=10000) { cout <<"\t排序规模:"<<NUM<<endl<<"\t初始状态："<<a[flag]<<endl; //开始排序 for(int i=0; i<5; ++i) { Randomize(); for(int j=1; j<=NUM; ++j) sortarray[j] = rand()%MAXINT; //如果是正序或逆序，则先把随机数组排好序 if(flag==1||flag==2) { //快速排序实现正序初始状态 QuickSort(sortarray,NUM); //逆序 if(flag==2) { for(int i=1;i<=NUM/2;i++) { temp=sortarray[i]; sortarray[i]=sortarray[NUM+1-i]; sortarray[NUM+1-i]=temp; }//for(int i=1;i<=num/2;i++) } //if(flag==2) }//if(flag==1||flag==2) for(int j1=1; j1<=NUM; ++j1) temparray[j1] = sortarray[j1]; Settime(); QuickSort(temparray,NUM); time[0] += (double)Gettime(); for(int j2=1; j2<=NUM; ++j2) temparray[j2] = sortarray[j2]; Settime(); InsertionSort(temparray,NUM); time[1] += (double)Gettime(); for(int j3=1; j3<=NUM; ++j3) temparray[j3] = sortarray[j3]; Settime(); SelectSort(temparray,NUM); time[2] += (double)Gettime(); for(int j4=1; j4<=NUM; ++j4) temparray[j4] = sortarray[j4]; Settime(); MergeSort(temparray,NUM); time[3] += (double)Gettime(); for(int j5=1; j5<=NUM; ++j5) temparray[j5] = sortarray[j5]; Settime(); HeapSort(temparray,NUM); time[4] += (double)Gettime(); }//for (i) cout << endl; cout<<"\t排序算法："<< " " << " 平均时间 " <<endl; cout<<"\t快速排序" << " " << time[0]/5<<" seconds"<<endl; cout<<"\t插入排序" << " " << time[1]/5 <<" seconds"<<endl; cout<<"\t选择排序" << " " << time[2]/5<<" seconds"<<endl; cout<<"\t归并排序" << " " << time[3]/5<<" seconds"<<endl; cout<<"\t堆排序 " << " " << time[4]/5 <<" seconds"<<endl; cout << "\n\t-----------------------------------------\n" << endl; }//for(NUM=10000;NUM<=100000;NUM +=10000) system("pause"); //delete[] sortarray; //delete[] temparray; }//while }//main