14种排序

  1 #include<iostream>
  2 #include<time.h>
  3 using namespace std;
  4 /*
  5 简单插入排序:
  6 最差时间复杂度:O(n^2)
  7 平均时间复杂度:O(n^2)
  8 */
  9 void Insertion_Sort(int *a,int n)
 10 {
 11     int i,j;
 12     for(i=2;i<=n;i++)
 13         if(a[i]<a[i-1])
 14         {
 15             a[0]=a[i];
 16             for(j=i-1;a[j]>a[0];j--)
 17                 a[j+1]=a[j];
 18             a[j+1]=a[0];
 19         }
 20 }
 21 /*
 22 折半插入排序:
 23 最差时间复杂度:O(n^2)
 24 平均时间复杂度:O(n^2)
 25 */
 26 void Bin_Sort(int *a,int n)
 27 {
 28     int i,j,low,mid,high;
 29     for(i=2;i<=n;i++)
 30         if(a[i]<a[i-1])
 31         {
 32             a[0]=a[i];
 33             low=1;
 34             high=i-1;
 35             while(low<=high)
 36             {
 37                 mid=(low+high)/2;
 38                 if(a[mid]>a[0])
 39                     high=mid-1;
 40                 else 
 41                     low=mid+1;
 42             }
 43             for(j=i-1;j>high;j--)
 44                 a[j+1]=a[j];
 45             a[high+1]=a[0];
 46         }
 47 }
 48 /*选择排序:
 49 最差时间复杂度:O(n^2)
 50 平均时间复杂度:O(n^2)
 51 */
 52 void Selection_Sort(int *a,int n)
 53 {
 54     int i,j,k;
 55     for(i=1;i<n;i++)
 56     {
 57         k=i;
 58         for(j=i+1;j<=n;j++)
 59             if(a[k]>a[j])
 60                 k=j;
 61         if(k!=i)    
 62             swap(a[k],a[i]);
 63     }
 64 }
 65 /*快速排序
 66 最差时间复杂度:O(n^2)
 67 平均时间复杂度:O(nlogn)
 68 */
 69 void Quick_Sort(int *a,int low,int high)
 70 {
 71     int i=low,j=high;
 72     a[0]=a[low];
 73     while(low<high)
 74     {
 75         while(low<high && a[high]>=a[0])
 76             high--;
 77             swap(a[low],a[high]);
 78         while(low<high && a[low]<=a[0])
 79             low++;
 80             swap(a[low],a[high]);
 81     }
 82     a[low]=a[0];
 83     if(i!=low)
 84         Quick_Sort(a,i,low-1);
 85     if(j!=high)
 86         Quick_Sort(a,high+1,j);
 87 }
 88 /*冒泡排序
 89 最差时间复杂度:O(n^2)
 90 平均时间复杂度:O(n^2)
 91 */
 92 void Bubble_Sort(int *a,int n)
 93 {
 94     int i;
 95     bool change=true;
 96     while(change)
 97     {
 98         change=false;
 99         for(i=1;i<n;i++)
100             if(a[i]>a[i+1])
101             {
102                 change=true;
103                 swap(a[i],a[i+1]);
104             }
105     }
106 }
107 /*鸡尾酒排序(双向冒泡排序):
108 最差时间复杂度:O(n^2))
109 平均时间复杂度:O(n^2)
110 */
111 void Cocktail_Sort(int *a,int n)
112 {
113     int i;
114     int left=1,right=n;
115     bool change=true;
116     while(change)
117     {
118         change=false;
119         for(i=left;i<right;i++)
120             if(a[i]>a[i+1])
121             {
122                 change=true;
123                 swap(a[i],a[i+1]);
124             }
125             right--;
126         for(i=right;i>left;i--)
127             if(a[i]<a[i-1])
128             {
129                 change=true;
130                 swap(a[i],a[i-1]);
131             }
132             left++;
133     }
134 }
135 /*堆排序
136 最差时间复杂度:O(nlogn)
137 平均时间复杂度:O(nlogn)
138 */
139 void Heap_Adjust(int *a,int low,int high)
140 {
141     int i;
142     a[0]=a[low];
143     for(i=2*low;i<=high;i*=2)
144         {
145             if(i<high && a[i]<a[i+1])
146                 i++;
147             if(a[0]>=a[i])
148                 break;
149             else 
150             {
151                 a[low]=a[i];
152                 low=i;
153             }
154         a[low]=a[0];
155         }
156 }
157 void Heap_Sort(int *a,int n)
158 {
159     int i;
160     for(i=n/2;i>=1;i--)
161         Heap_Adjust(a,i,n);
162     for(i=n;i>=2;i--)
163     {
164         swap(a[1],a[i]);
165          Heap_Adjust(a,1,i-1);
166     }
167 }
168 /*
169 希尔排序
170 最差时间复杂度:O(n^2)
171 平均时间复杂度:O(n^1.3)
172 */
173 void Shell_Sort(int *a,int n)
174 {
175     int i,j;
176     int gap=n/2;
177     while(gap)
178     {
179         for(i=gap+1;i<=n;i++)
180             if(a[i]<a[i-gap])
181             {
182                 a[0]=a[i];
183                 for(j=i-gap;j>0 && a[j]>a[0];j-=gap)
184                     a[j+gap]=a[j];
185                 a[j+gap]=a[0];
186             }
187             gap/=2;
188     }
189 }
190 /*
191 计数排序:
192 最差时间复杂度:O(n+k)
193 平均时间复杂度:O(n+k)
194 */
195 void Counting_Sort(int *a,int n)
196 {
197     int i;
198     int max=a[1];
199     for(i=2;i<=n;i++)
200         {
201             if(max<a[i])
202             max=a[i];
203         }
204     int *mark=new int[max+1];
205     memset(mark,0,sizeof(int)*(max+1));
206     for(i=1;i<=n;i++)
207         mark[a[i]]++;
208     for(i=1;i<=max;i++)
209         mark[i]+=mark[i-1];
210     int *p=new int[n+1];
211     memset(p,0,sizeof(int)*(n+1));
212     for(i=1;i<=n;i++)
213         {
214             p[mark[a[i]]]=a[i];
215             mark[a[i]]--;
216         }
217     for(i=1;i<=n;i++)
218         a[i]=p[i];
219 }
220 /*
221 鸽巢排序:
222 最差时间复杂度:O(n+N)
223 平均时间复杂度:O(n+N)
224 */
225 void Pigeonhole_Sort(int *a,int n)
226 {
227     int i,j,k=1;
228     int max=a[1];
229     for(i=2;i<=n;i++)
230         {
231             if(max<a[i])
232             max=a[i];
233         }
234     int *mark=new int[max+1];
235     memset(mark,0,sizeof(int)*(max+1));
236     for(i=1;i<=n;i++)
237         mark[a[i]]++;
238     for(i=1;i<=max;i++)
239     for(j=1;j<=mark[i];j++)
240         a[k++]=i;
241 }
242 /*
243 归并排序:
244 最差时间复杂度:O(nlogn)
245 平均时间复杂度:O(nlogn)
246 */
247 void Merge(int *a,int low,int mid,int high)
248 {
249     int p,i=low,j=mid+1,k=low;
250     int *temp=new int[high+1];
251     memset(temp,0,sizeof(int)*(high+1));
252     for(;i<=mid && j<=high;k++)
253         if(a[i]<a[j])
254             temp[k]=a[i++];
255         else 
256             temp[k]=a[j++];
257     if(i<=mid)
258         for(p=0;p<=mid-i;p++)
259             temp[k+p]=a[i+p];
260     if(j<=high)
261         for(p=0;p<=high-j;p++)
262             temp[k+p]=a[j+p];
263     for(p=low;p<=high;p++)
264         a[p]=temp[p];
265 }
266 void MSort(int *a,int low,int high)
267 {
268     if(low<high)
269     {
270         int mid=(low+high)/2;
271         MSort(a,low,mid);
272         MSort(a,mid+1,high);
273         Merge(a,low,mid,high);
274     }
275 }
276 /*
277 梳排序:
278 最差时间复杂度:O(nlogn)
279 平均时间复杂度:O(nlogn)
280 */
281 void Comb_Sort(int *a,int n)
282 {
283     int i;
284     int gap=n;
285     while(gap/=1.3)
286     {
287         for(i=gap+1;i<=n;i++)
288             if(a[i]<a[i-gap])
289                 swap(a[i],a[i-gap]);
290     }
291 }
292 /*
293 奇偶排序(砖排序):
294 最差时间复杂度:O(n^2)
295 平均时间复杂度:O(n^2)
296 */
297 void Odd_Even(int *a,int n)
298 {
299     int i;
300     bool change=true;
301     while(change)
302     {
303         change=false;
304     for(i=1;i<n;i+=2)
305         if(a[i]>a[i+1])
306             {
307                 change=true;
308                 swap(a[i],a[i+1]);
309             }
310     for(i=2;i<n;i+=2)
311         if(a[i]>a[i+1])
312         {
313             change=true;
314             swap(a[i],a[i+1]);
315         }
316     }
317 }
318 /*
319 地精排序(侏儒排序):
320 最差时间复杂度:O(n^2)
321 平均时间复杂度:O(n^2)
322 */
323 void Gnome_Sort(int *a,int n)
324 {
325     int i=0;
326     while(i<n)
327     {
328         if(i<=0 || (i>=1 && a[i]<=a[i+1]))
329             i++;
330         else 
331         {
332             swap(a[i],a[i+1]);
333             i--;
334         }
335     }
336 }
337 void Out(int *a,int n)
338 {
339     int i;
340     for(i=1;i<=n;i++)
341         cout<<a[i]<<" ";
342     cout<<endl;
343 }
344 int main()
345 {
346     srand((unsigned)time(NULL));
347     int *p=new int[16];
348     memset(p,0,sizeof(int)*16);
349     for(int i=1;i<=15;i++)
350     {
351         p[i]=rand()%100;
352     }
353     Out(p,15);
354     //Insertion_Sort(p,15);
355     //Bin_Sort(p,15);
356     //Selection_Sort(p,15);
357     //Quick_Sort(p,1,15);
358     //Bubble_Sort(p,15);
359     //Cocktail_Sort(p,15);
360     //Heap_Sort(p,15);
361     //Shell_Sort(p,15);
362     //Counting_Sort(p,15);
363     //Pigeonhole_Sort(p,15);
364     //Comb_Sort(p,15);
365     //Odd_Even(p,15);
366     //MSort(p,1,15);
367     Gnome_Sort(p,15);
368     Out(p,15);
369 }
原文链接：http://www.oschina.net/code/snippet_564140_12720