// 归并排序和快速排序算法实现#include <iostream>#include <cstdlib>#include <ctime>using namespace std;//// declaration// merge sorttemplate<class T>void MergeSort(T ar[], int num);template<class T>void MergeSort_In(T ar[], T ta[], int low, int high);template<class T>void Merge(T ar[], T ta[], int low, int mid, int high);// quick sorttemplate<class T>void QuickSort(T ar[], int num);template<class T>void QuickSort_In(T ar[], int left, int right);template<class T>int Partition(T ar[], int left, int right);// definition// merge sorttemplate<class T>void MergeSort(T ar[], int num){ T *ta=new T[num]; MergeSort_In(ar, ta, 0, num-1); delete ta;}//MergeSorttemplate<class T>void MergeSort_In(T ar[], T ta[], int low, int high){ if (low<high) { int mid=(low+high)/2; MergeSort_In(ar, ta, low, mid); MergeSort_In(ar, ta, mid+1, high); Merge(ar, ta, low, mid, high); }}//MergeSort_Intemplate<class T>void Merge(T ar[], T ta[], int low, int mid, int high){ int i=low, j=mid+1, k=low; while (i<=mid && j<=high) { if (ar[i]<=ar[j]) ta[k++]=ar[i++]; else ta[k++]=ar[j++]; } if (i>mid) { while (j<=high) ta[k++]=ar[j++]; } else { while (i<=mid) ta[k++]=ar[i++]; } // copy array back for (k=low; k<=high; ++k) ar[k]=ta[k];}// Merge
// quick sorttemplate<class T>void QuickSort(T ar[], int num){ QuickSort_In(ar, 0, num-1);}template<class T>void QuickSort_In(T ar[], int left, int right){ if (left<right) { int mid=Partition(ar, left, right); QuickSort_In(ar, left, mid-1); QuickSort_In(ar, mid+1, right); }}//QuickSorttemplate<class T>int Partition(T ar[], int left, int right){ int i=left, j=right+1; T key=ar[left]; while (true) { while (ar[++i]<key) ; while (ar[--j]>key) ; if (i>=j) break; swap(ar[i], ar[j]); } ar[left]=ar[j]; ar[j]=key; return j;}//Partition/// main programint main() {/* // test algorithm int test[9]={5, 32, 78, 155 ,68, 94, 26,57,48}; int test1[9]={5, 32, 78, 155 ,68, 94, 26,57,48}; cout<<"Before sort:"<<endl; for(int i=0; i<9; ++i) cout<<test[i]<<" "; cout<<endl; MergeSort(test, 9); cout<<"MergeSort:"<<endl; for(i=0; i<9; ++i) cout<<test[i]<<" "; cout<<endl; QuickSort(test1, 9); cout<<"QuickSort:"<<endl; for(i=0; i<9; ++i) cout<<test1[i]<<" "; cout<<endl;*/ int i, j; const int dim1=50; const int dim2=100000; int (*arr1)[dim2]=new int[dim1][dim2]; int (*arr2)[dim2]=new int[dim1][dim2]; // make random numbers srand((unsigned)time(NULL)); // set seed for (i=0; i<dim1; ++i) { for (j=0; j<dim2; ++j) { arr1[i][j]=rand(); // RAND_MAX=0x7FFF arr2[i][j]=arr1[i][j]; // keep two same arrays } } // time merge sort clock_t start=clock(); for (i=0; i<dim1; ++i) QuickSort(arr1[i], dim2); cout<<"Quick sort(50*100000): "<<(double)(clock()-start)/CLOCKS_PER_SEC<<" seconds"<<endl; // time merge sort start=clock(); for (i=0; i<dim1; ++i) MergeSort(arr2[i], dim2); cout<<"Merge sort(50*100000): "<<(double)(clock()-start)/CLOCKS_PER_SEC<<" seconds"<<endl; return 0;}
