排序算法复习

排序算法复习
作者:vpoet
mails:vpoet_sir@163.com
注:转载请注明出处
  1 #include <iostream>
  2 #include <windows.h>
  3 using namespace std;
  4 
  5 void Bubble_Sort(int UnSort[],int length);
  6 void Select_Sort(int UnSort[],int length);
  7 void Insert_Sort(int UnSort[],int length);
  8 void Merge_Sort(int UnSort[],int length);
  9 void Quick_Sort(int UnSort[],int length);
 10 
 11 
 12 int main()
 13 {
 14     int UnSort[10]={5,4,7,12,31,3,8,9,10,2};
 15     cout<<"*****************************Vpoet************************************"<<endl;
 16     cout<<"The Unsort Array is: ";
 17     for(int i=0;i<10;i++)
 18     {
 19         cout<<UnSort[i]<<"  ";
 20     }
 21     cout<<endl;
 22     cout<<"**********************************************************************"<<endl;
 23     cout<<"			*********1.Bubble*********			"<<endl;
 24     cout<<"			*********2.Select*********			"<<endl;
 25     cout<<"			*********3.Insert*********			"<<endl;
 26     cout<<"			*********4.Merge *********			"<<endl;
 27     cout<<"			*********5.Quick *********			"<<endl;
 28     cout<<"			*********0.Exit*********			"<<endl;
 29     cout<<"**********************************************************************"<<endl;
 30     int ChooseIndex;
 31     cout<<"Please choose the sort Algo:";
 32     cin>>ChooseIndex;
 33     
 34     switch(ChooseIndex)
 35     {
 36     case 1:
 37         Bubble_Sort(UnSort,10);
 38         break;
 39     case 2:
 40         Select_Sort(UnSort,10);
 41         break;
 42     case 3:
 43         Insert_Sort(UnSort,10);
 44         break;
 45     case 4:
 46         Merge_Sort(UnSort,10);
 47         break;
 48     case 5:
 49         LARGE_INTEGER BegainTime ;     
 50         LARGE_INTEGER EndTime ;     
 51         LARGE_INTEGER Frequency ;     
 52         QueryPerformanceFrequency(&Frequency);     
 53         QueryPerformanceCounter(&BegainTime) ;   
 54         Quick_Sort(UnSort,10);
 55         QueryPerformanceCounter(&EndTime);
 56         cout<<"**********************************************************************"<<endl;
 57         cout<<"You choosed Quick sort!"<<endl;
 58         cout<<"The Sort Array is:  ";
 59         for(i=0;i<10;i++)
 60         {
 61             cout<<UnSort[i]<<"  ";
 62         }
 63         cout<<endl;
 64         cout << "Run Time："<<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl;     
 65         cout<<"**********************************************************************"<<endl;
 66         break;
 67     case 0:
 68         cout<<"You Choose To exit,GoodBye!"<<endl;
 69         break;
 70 
 71     }
 72     return 1;
 73 }
 74 
 75 
 76 void Bubble_Sort(int UnSort[],int length)
 77 {
 78     LARGE_INTEGER BegainTime ;     
 79     LARGE_INTEGER EndTime ;     
 80     LARGE_INTEGER Frequency ;     
 81     QueryPerformanceFrequency(&Frequency);     
 82     QueryPerformanceCounter(&BegainTime) ;     
 83     for(int i=0;i<9;i++)
 84     {
 85         for(int j=i+1;j<10;j++)
 86         {
 87             if(UnSort[i]>UnSort[j])
 88             {
 89                 int temp=UnSort[i];
 90                 UnSort[i]=UnSort[j];
 91                 UnSort[j]=temp;
 92             }
 93         }
 94     }
 95     QueryPerformanceCounter(&EndTime);    
 96     cout<<"**********************************************************************"<<endl;
 97     cout<<"You choosed Buuble sort!"<<endl;
 98     cout<<"The Sort Array is:  ";
 99     for(i=0;i<10;i++)
100     {
101         cout<<UnSort[i]<<"  ";
102     }
103     cout<<endl;
104     cout <<"Run Time:"<<(double)(EndTime.QuadPart-BegainTime.QuadPart)/Frequency.QuadPart<<endl;     
105     cout<<"**********************************************************************"<<endl;
106     
107 }
108 
109 void Select_Sort(int UnSort[],int length)
110 {
111     LARGE_INTEGER BegainTime ;     
112     LARGE_INTEGER EndTime ;     
113     LARGE_INTEGER Frequency ;     
114     QueryPerformanceFrequency(&Frequency);     
115     QueryPerformanceCounter(&BegainTime) ;     
116     int Min;
117     for(int i=0;i<10;i++)
118     {
119         Min=UnSort[i];
120         int index=i;
121         for(int j=i+1;j<10;j++)
122         {
123             if(Min>UnSort[j])
124             {
125                 Min=UnSort[j];
126                 index=j;
127             }
128         }
129         int temp=UnSort[i];
130         UnSort[i]=UnSort[index];
131         UnSort[index]=temp;
132     }
133     QueryPerformanceCounter(&EndTime);    
134     cout<<"**********************************************************************"<<endl;
135     cout<<"You choosed Select sort!"<<endl;
136     cout<<"The Sort Array is:  ";
137     for(i=0;i<10;i++)
138     {
139         cout<<UnSort[i]<<"  ";
140     }
141     cout<<endl;
142     cout << "Run Time："<<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl;     
143     cout<<"**********************************************************************"<<endl;
144 }
145 
146 void Insert_Sort(int UnSort[],int length)
147 {
148     LARGE_INTEGER BegainTime ;     
149     LARGE_INTEGER EndTime ;     
150     LARGE_INTEGER Frequency ;     
151     QueryPerformanceFrequency(&Frequency);     
152     QueryPerformanceCounter(&BegainTime) ;     
153     for(int i=1;i<10;i++)
154     {
155         int j=i;
156         int temp=UnSort[i];
157         while(j>0&&temp<UnSort[j-1])
158         {
159             UnSort[j]=UnSort[j-1];
160             j--;
161         }
162         UnSort[j]=temp;
163     }
164     QueryPerformanceCounter(&EndTime);    
165     cout<<"**********************************************************************"<<endl;
166     cout<<"You choosed Select sort!"<<endl;
167     cout<<"The Sort Array is:  ";
168     for(i=0;i<10;i++)
169     {
170         cout<<UnSort[i]<<"  ";
171     }
172     cout<<endl;
173     cout << "Run Time："<<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl;     
174     cout<<"**********************************************************************"<<endl;
175 }
176 
177 void mergesortEnd(int Unsort[],int first,int mid,int last,int temp[])
178 {
179     int i = first, j = mid + 1;
180     int m = mid, n = last;
181     int k = 0;
182     
183     while (i <= m && j <= n)
184     {
185         if (Unsort[i] <= Unsort[j])
186             temp[k++] = Unsort[i++];
187         else
188             temp[k++] = Unsort[j++];
189     }
190     
191     while (i <= m)
192         temp[k++] = Unsort[i++];
193     
194     while (j <= n)
195         temp[k++] = Unsort[j++];
196     
197     for (i = 0; i < k; ++i)
198         Unsort[first + i] = temp[i];    
199 }
200 
201 
202 void mergesortfun(int UnSort[],int first,int last,int temp[])
203 {
204     if (first < last)
205     {
206        int mid = (first + last) / 2;
207        mergesortfun(UnSort, first, mid, temp);     //左边有序
208        mergesortfun(UnSort, mid + 1, last, temp);  //右边有序
209        mergesortEnd(UnSort, first, mid, last, temp); //再将两个有序数列合并
210     }
211 }
212 
213 void Merge_Sort(int UnSort[],int length)
214 {
215     int *p = new int[length];
216     if (p == NULL)
217         return ;
218     
219     LARGE_INTEGER BegainTime ;     
220     LARGE_INTEGER EndTime ;     
221     LARGE_INTEGER Frequency ;     
222     QueryPerformanceFrequency(&Frequency);     
223     QueryPerformanceCounter(&BegainTime) ;     
224     mergesortfun(UnSort, 0, length - 1, p);
225     QueryPerformanceCounter(&EndTime);
226     delete[] p;
227     
228     cout<<"**********************************************************************"<<endl;
229     cout<<"You choosed Merge sort!"<<endl;
230     cout<<"The Sort Array is:  ";
231     for(int i=0;i<10;i++)
232     {
233         cout<<UnSort[i]<<"  ";
234     }
235     cout<<endl;
236     cout << "Run Time："<<(double)( EndTime.QuadPart - BegainTime.QuadPart )/ Frequency.QuadPart <<endl;     
237     cout<<"**********************************************************************"<<endl;
238 }
239 
240 void Quick_Sort(int UnSort[],int length)
241 {
242     int i=0;
243     int j=length-1;
244     int key=UnSort[0];
245 
246     if(length>1)
247     {
248         while(i!=j)
249         {
250             for(;j>i;j--)
251             {
252                 if(UnSort[j]<key)
253                 {
254                     UnSort[i]=UnSort[j];
255                     break;
256                 }
257             }
258 
259             for(;i<j;i++)
260             {
261                 if(UnSort[i]>key)
262                 {
263                     UnSort[j]=UnSort[i];
264                     break;
265                 }
266             }
267 
268             UnSort[i]=key;
269         }
270 
271         Quick_Sort(UnSort,i);
272         Quick_Sort(UnSort+i+1,length-i-1);
273     }
274 }