C++排序算法对比（桶排序等）

#include <iostream> #include "sort.h" using namespace std; int main(void) { int n; LARGE_INTEGER t1,t2,feq; double time; double *arr = new double[10]; double *arr2 = new double[1000]; double *arr3 = new double[10000]; double *arr4 = new double[100000]; while (1) { Menu(); int sw; cin>>sw; switch(sw) { case 0: return 0 ; case 1: n = 10; //MergeSort cout<<"MergeSort:"<<endl; InitialArr(arr,n); cout<<"Before:"<<endl; PrintArr(arr,n); MergeSortArr(arr,n); cout<<"After:" <<endl; PrintArr(arr,n); cout<<endl; //InsertSort cout<<"InsertSort:"<<endl; InitialArr(arr,n); cout<<"Before:"<<endl; PrintArr(arr,n); InsertSort(arr,n); cout<<"After:" <<endl; PrintArr(arr,n); cout<<endl; //ShellSort cout<<"ShellSort:"<<endl; InitialArr(arr,n); cout<<"Before:"<<endl; PrintArr(arr,n); ShellSort(arr,n); cout<<"After:" <<endl; PrintArr(arr,n); cout<<endl; //QuickSort cout<<"QuickSort:"<<endl; InitialArr(arr,n); cout<<"Before:"<<endl; PrintArr(arr,n); QuickSortArr(arr,n); cout<<"After:" <<endl; PrintArr(arr,n); cout<<endl; //BubbleSort cout<<"BubbleSort:"<<endl; InitialArr(arr,n); cout<<"Before:"<<endl; PrintArr(arr,n); BubbleSort(arr,n); cout<<"After:" <<endl; PrintArr(arr,n); cout<<endl; //BucketSort cout<<"BucketSort:"<<endl; InitialArr(arr,n); cout<<"Before:"<<endl; PrintArr(arr,n); BucketSort(arr,n); cout<<"After:" <<endl; PrintArr(arr,n); cout<<endl; break; case 2: n = 1000; cout<<"The time of Sort of 1000 elements as follows: "<< endl; //MergeSort InitialArr(arr2,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); MergeSortArr(arr2,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"MergeSort:"<< setw(15) <<time <<"ms"<<endl; //InsertSort InitialArr(arr2,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); InsertSort(arr2,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"InsertSort:"<<setw(15) <<time <<"ms"<<endl; //ShellSort InitialArr(arr2,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); ShellSort(arr2,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"ShellSort:"<<setw(15) <<time <<"ms"<<endl; //QuickSort InitialArr(arr2,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); QuickSortArr(arr2,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"QuickSort:"<<setw(15) <<time <<"ms"<<endl; //BubbleSort InitialArr(arr2,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); BubbleSort(arr2,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"BubbleSort:"<<setw(15) <<time <<"ms"<<endl; //BucketSort InitialArr(arr2,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); BucketSort(arr2,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"BucketSort:"<<setw(15) <<time <<"ms"<<endl; break; case 3: n = 10000; cout<<"The time of Sort of 10000 elements as follows: "<< endl; //MergeSort InitialArr(arr3,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); MergeSortArr(arr3,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"MergeSort:"<<setw(15) <<time <<"ms"<<endl; //InserSort InitialArr(arr3,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); InsertSort(arr3,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"InsertSort:"<<setw(15) <<time <<"ms"<<endl; //ShellSort InitialArr(arr3,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); ShellSort(arr3,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"ShellSort:"<<setw(15) <<time <<"ms"<<endl; //QuickSort InitialArr(arr3,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); QuickSortArr(arr3,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"QuickSort:"<<setw(15) <<time <<"ms"<<endl; //BubbleSort InitialArr(arr3,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); BubbleSort(arr3,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"BubbleSort:"<<setw(15) <<time <<"ms"<<endl; //BucketSort InitialArr(arr3,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); BucketSort(arr3,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"BucketSort:"<<setw(15) <<time <<"ms"<<endl; break; case 4: n = 100000; cout<<"The time of Sort of 100000 elements as follows: "<< endl; //MergeSort InitialArr(arr4,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); MergeSortArr(arr4,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"MergeSort:"<<setw(15) <<time <<"ms"<<endl; //InserSort InitialArr(arr4,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); InsertSort(arr4,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"InsertSort:"<<setw(15) <<time <<"ms"<<endl; //ShellSort InitialArr(arr4,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); ShellSort(arr4,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"ShellSort:"<<setw(15) <<time <<"ms"<<endl; //QuickSort InitialArr(arr4,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); QuickSortArr(arr4,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"QuickSort:"<<setw(15) <<time <<"ms"<<endl; //BubbleSort InitialArr(arr4,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); BubbleSort(arr4,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"BubbleSort:"<<setw(15) <<time <<"ms"<<endl; //BucketSort InitialArr(arr4,n); QueryPerformanceFrequency(&feq); QueryPerformanceCounter(&t1); BucketSort(arr4,n); QueryPerformanceCounter(&t2); time=((double)t2.QuadPart-(double)t1.QuadPart)/((double)feq.QuadPart)*1000; cout<<setw(15)<<"BucketSort:"<<setw(15) <<time <<"ms"<<endl; break; default:cout<<"error,please input again:!\n"; break; } } }