|
001 #include<iostream>
002 #include<ctime>
003 using namespace std;
004
005 //MergeSort
006 void Merge(int a[ ], int p, int q, int r)
007 {
008 //对两个有序的数列进行归并
009 int i,k;
010 int begin1,end1,begin2,end2;
011 int *temp= new int[r-p+1];
012 begin1= p;
013 end1 = q;
014 begin2 = q+1;
015 end2 = r;
016 k = 0;
017 //数列a从begin1到end1，及从begin2到end2都是有序的，接下来把这两部分合成一个
018 //新的有序的数列
019 while((begin1 <= end1)&&( begin2 <= end2)){
020 if(a[begin1] <=a[begin2]){
021 temp[k] = a[begin1];
022 begin1++;
023 } else {
024 temp[k] = a[begin2];
025 begin2++;
026 }
027 k++;
028 }
029 while(begin1<=end1){
030 temp[k++] = a[begin1++];
031 }
032 while(begin2<=end2){
033 temp[k++] = a[begin2++];
034 }
035 for (i = 0; i < (r - p+1); i++){
036 a[p+i] = temp[i];
037 }
038 delete temp;
039 }
040
041 void MergeSort(int a[], int first, int last)
042 {
043 int mid = 0;
044 if(first<last){
045 mid = (first+last)/2;
046 MergeSort(a, first, mid);
047 MergeSort(a, mid+1,last);
048 Merge(a,first,mid,last);
049 }
050 }
051
052 //QuickSort
053 void QuickSort(int a[],int first,int last)
054 {
055 int pivot,last_small;
056 pivot=a[first];
057 last_small=first;
058 //从pivot之后的第一个元素开始扫描，一旦发现比pivot小的元素就挪到前边
059 //循环结束后，从a[1]到a[last_small]都是比pivot小的元素
060 //从a[last_small+1]到a[last]都是不比pivot小的元素
061 for(int i=first+1;i<=last;i++){
062 if(a[i]<pivot){
063 last_small++;
064 swap(a[last_small],a[i]);
065 }
066 }
067 //这个swap的作用是使得从a[0]到a[last_small-1]都是比pivot小的元素
068 //从a[last_small+1]到a[last]都是不比pivot小的元素
069 swap(a[first],a[last_small]);
070 if(first<last){
071 QuickSort(a,first,last_small-1);
072 QuickSort(a,last_small+1,last);
073 }
074 }
075
076 int main()
077 {
078 int *p,*q,t=2;;
079 int choice;
080 clock_t start,end;
081 const int num=1000;
082 p=new int[num];
083
084 srand(int(time(NULL)));
085 for(int i=0;i<num;i++){
086 p[i]=rand()%num;
087 cout<<p[i]<<"\t";
088 }
089
090 q=new int[num];
091 for(int i=0;i<num;i++){
092 q[i]=p[i];
093 }
094
095 cout<<endl;
096 cout<<"Input 1 to use mergesort,input 2 to use quicksort:"<<endl;
097 while(t--){
098 cin>>choice;
099 switch(choice){
100 case 1:
101 start=clock();
102 MergeSort(p,0,num-1);
103 end=clock();
104 for(int i=0;i<num;i++){
105 cout<<p[i]<<"\t";
106 }
107 cout<<"Time of sort is "<<double(end-start)/CLOCKS_PER_SEC<<endl;
108 break;
109 case 2:
110 start=clock();
111 QuickSort(q,0,num-1);
112 end=clock();
113 for(int i=0;i<num;i++){
114 cout<<q[i]<<"\t";
115 }
116 cout<<"Time of sort is "<<double(end-start)/CLOCKS_PER_SEC<<endl;
117 break;
118 }
119 cout<<endl;
120 }
121 return 0;
122 }
|
