八大排序方法汇总（选择排序，插入排序-简单插入排序、shell排序，交换排序-冒泡排序、快速排序、堆排序，归并排序，计数排序）

  1 #include <iostream>
  2 #include <cassert>
  3 #include <ctime>
  4 #include <bitset>
  5 using namespace std;
  6 
  7 typedef int DataType;
  8 const int MaxSize = 1000000;
  9 const int SortCutOff = 50;
 10 
 11 //产生在[lowBound,upperBound - 1]区间的随机数
 12 int RandomIntGenerate(int lowBound, int upperBound)
 13 {    
 14     return (lowBound + (RAND_MAX * rand() + rand()) % (upperBound - lowBound + 1) );
 15 }
 16 
 17 
 18 //数组显示
 19 void DisplayArray(DataType array[],int len)
 20 {
 21     assert(NULL != array && len > 0);
 22 
 23     for (int i = 0;i < len;++i)
 24     {
 25         cout<<array[i]<<"	";
 26     }
 27     cout<<endl;
 28 }
 29 
 30 //简单选择排序
 31 void SelectSort(DataType *unStorted,size_t n)
 32 {
 33     assert(NULL != unStorted && n > 0);
 34 
 35     size_t i;
 36     size_t j;
 37     size_t minIndex = 0;
 38 
 39     for (i= 0;i < n - 1;++i)
 40     {
 41         minIndex = i;
 42         for (j = i + 1;j < n;++j)
 43         {
 44             minIndex = unStorted[minIndex] < unStorted[j] ? minIndex : j;
 45         }
 46 
 47         swap(unStorted[i],unStorted[minIndex]);  //没有判断i与minIndex是否相等
 48     }
 49 }
 50 
 51 //简单插入排序
 52 void InsertSort(DataType *unStorted,size_t n)
 53 {
 54     assert(NULL != unStorted && n > 0);
 55 
 56     size_t i;
 57     int j;   //不能定义为size_t,因为for循环的结束条件需要将j减为-1作为结束条件
 58     DataType dataToInsert = 0;
 59 
 60     for (i= 0;i < n - 1;++i)
 61     {
 62         dataToInsert = unStorted[i + 1];
 63         for (j = i;j >= 0;--j)
 64         {
 65             if (unStorted[j] > dataToInsert)
 66             {
 67                 unStorted[j + 1] = unStorted[j];
 68             }
 69             else
 70             {
 71                 break;
 72             }
 73         }
 74         unStorted[j + 1] = dataToInsert;   //注意此处为j + 1，而非j
 75     }
 76 }
 77 
 78 //插入排序-shell排序
 79 //简单插入排序在输入为基本有序的情况下，性能最好，
 80 //shell排序每次大步长下的排序，相当于通过分组对数组预处理，使其基本有序
 81 void ShellSort(DataType *unStorted,size_t n)
 82 {
 83     assert(NULL != unStorted && n > 0);
 84 
 85     size_t step = n / 2;
 86     size_t k;
 87     size_t i;
 88     int j;   //不能定义为size_t,因为for循环的结束条件需要将j减为-1作为结束条件
 89     DataType dataToInsert = 0;
 90 
 91     while (step >= 1)  //n为1时，step为0，不进入while循环就返回；
 92     {
 93         for (k = 0;k < step;++k )
 94         {
 95             for (i= 0;i < n - step;i += step)
 96             {
 97                 dataToInsert = unStorted[i + step];
 98                 for (j = i;j >= 0;j -= step)
 99                 {
100                     if (unStorted[j] > dataToInsert)
101                     {
102                         unStorted[j + step] = unStorted[j];
103                     }
104                     else
105                     {
106                         break;
107                     }
108                 }
109                 unStorted[j + step] = dataToInsert;   //注意此处为j + 1，而非j
110             }
111         }
112         step /= 2; 
113     }
114 }
115 
116 //交换排序-冒泡排序
117 void BubbleSort(DataType *unStorted,size_t n)
118 {
119     assert(NULL != unStorted && n > 0);
120 
121     size_t i;
122     size_t j;    
123 
124     for (i = n - 1;i >= 1;--i)
125     {
126         for (j = 0;j < i;++j)
127         {
128             if (unStorted[j] > unStorted[j + 1])
129             {
130                 swap(unStorted[j],unStorted[j + 1]);
131             }
132         }
133     }
134 }
135 
136 //快速排序的划分函数
137 size_t Partion(DataType *unStorted,size_t begin,size_t end)
138 {
139     assert(begin <= end); //begin end都是定义为size_t的，因此不需要检查
140     
141     size_t i = begin;
142     size_t j = end;
143     //size_t pivot = i;
144     size_t pivot = RandomIntGenerate(begin,end);  //枢轴为随机的，使得快速排序的划分尽可能对称
145     swap(unStorted[i],unStorted[pivot]);
146 
147     while (i < j)
148     {
149         while (j > i && unStorted[j] > unStorted[i])
150         {
151             --j;
152         }
153         
154         if (j > i)
155         {
156             swap(unStorted[i],unStorted[j]);
157             pivot = j;
158             ++i;
159         }
160 
161         while (i < j && unStorted[i] < unStorted[j])
162         {
163             ++i;
164         }
165 
166         if (j > i)
167         {
168             swap(unStorted[i],unStorted[j]);
169             pivot = i;
170             --j;
171         }
172     }
173     //return i;
174     //return j;
175     return pivot;
176 }
177 
178 //交换排序-快速排序
179 void QuickSort(DataType *unStorted,size_t begin,size_t end)
180 {
181     assert(NULL != unStorted);
182 
183     //assert(begin >= 0 && end >= 0);  //begin end都是定义为size_t的，因此不需要检查
184 
185     if (begin >= end)
186     {
187         return;
188     }
189 
190     int mid = Partion(unStorted,begin,end);    
191 
192     if (begin < mid)
193     {
194         QuickSort(unStorted,begin,mid - 1);
195     }
196 
197     //QuickSort(unStorted,begin,mid - 1);  //若mid为0，size_t类型的mid减1会出问题，因此用begin < mid判断
198     QuickSort(unStorted,mid + 1,end);
199 }
200 
201 //归并两个数组
202 void Merge(DataType *unStorted,size_t begin,size_t mid,size_t end)
203 {
204     assert(NULL != unStorted);
205     assert(begin <= mid && mid <=end);
206 
207     DataType *resArray = new DataType[end - begin + 1];
208     DataType *res = resArray;
209 
210     size_t lowIndex = begin;
211     size_t highIndex = mid + 1;
212 
213     while (lowIndex <= mid && highIndex <= end)
214     {
215         if (unStorted[lowIndex] <= unStorted[highIndex])
216         {
217             *res++ = unStorted[lowIndex++];
218         }
219         else
220         {
221             *res++ = unStorted[highIndex++];
222         }
223     }
224 
225     while (lowIndex <= mid)
226     {
227         *res++ = unStorted[lowIndex++];
228     }
229 
230     while (highIndex <= end)
231     {
232         *res++ = unStorted[highIndex++];
233     }
234 
235     res = resArray;
236 
237     for (size_t index = begin;index <= end;++index)
238     {
239         unStorted[index] = *res++;
240     }
241 
242     delete [] resArray;
243 }
244 
245 //归并排序的非递归实现，自底向上归并
246 void MergeSortNonRecursive(DataType *unStorted,size_t n)
247 {
248     assert(NULL != unStorted);
249 
250     size_t begin = 0;
251     size_t mid = 0;
252     size_t end = 0;
253 
254     size_t step = 1;
255 
256     while (step < n)
257     {
258         begin = 0;
259         mid = begin + step - 1;
260         end = begin+ 2 * step - 1;
261 
262         while (mid < n)
263         {
264             end = end > (n - 1) ? (n - 1) : end;  //防止end越界
265 
266             Merge(unStorted,begin,mid,end);
267 
268             begin = end + 1;    //不是begin = begin + step + 1;
269             mid = begin + step - 1;
270             end = begin+ 2 * step - 1;
271         }
272         step *= 2;
273     }
274 }
275 
276 //归并排序的非递归实现，自顶向下归并，分治法
277 void MergeSort(DataType *unStorted,size_t begin,size_t end)
278 {
279     assert(NULL != unStorted);
280 
281     if (begin >= end)
282     {
283         return;
284     }
285 
286     size_t mid = begin + (end - begin) / 2;
287     MergeSort(unStorted,begin,mid);
288     MergeSort(unStorted,mid + 1,end);  //若mid为size_t类型最大值，mid + 1就会越界，此时end已经越界
289     Merge(unStorted,begin,mid,end);
290 }
291 
292 //堆调整
293 //参数n为数组中最大小标，如数组有n+1个元素，最大下标为n
294 //posToAdjust为需要调整的位置的下标
295 void HeapAdjust(DataType *unStorted,size_t n,size_t posToAdjust)
296 {
297     assert(NULL != unStorted);  //在调用的函数中已经有，可以删去
298 
299     size_t lchildIndex = 2 * posToAdjust + 1;
300     size_t rchildIndex = 2 * posToAdjust + 2;
301 
302     size_t maxPosition = posToAdjust;
303 
304     //while (lchildIndex <= n || rchildIndex <= n)
305     while (lchildIndex <= n)  //此处只要lchildIndex <= n ，即可进入循环
306     {
307         if (lchildIndex <= n && unStorted[lchildIndex] > unStorted[maxPosition])
308         {
309             maxPosition = lchildIndex;
310         }
311         //else if (rchildIndex <= n && unStorted[rchildIndex] > unStorted[maxPosition])
312         if (rchildIndex <= n && unStorted[rchildIndex] > unStorted[maxPosition])  //不是else if 
313         {
314             maxPosition = rchildIndex;
315         }
316 
317         if (maxPosition != posToAdjust)
318         {
319             swap(unStorted[posToAdjust],unStorted[maxPosition]);
320             
321             posToAdjust = maxPosition;      //更新posToAdjust，可以用递归，即HeapAdjust(unStorted,n,maxPosition);
322             lchildIndex = 2 * maxPosition + 1;
323             rchildIndex = 2 * maxPosition + 2;
324         }
325         else
326         {
327             break;
328         }
329     }
330 }
331 
332 //堆排序
333 //参数n为数组中最大小标，如数组有n+1个元素，最大下标为n
334 void HeapSort(DataType *unStorted,size_t n)
335 {
336     assert(NULL != unStorted);
337 
338     int index;
339 
340     for (index = (n - 1) / 2;index >= 0;--index)  //index需要减到0，因此不能定义为size_t
341     {
342         HeapAdjust(unStorted,n,index);
343     }
344 
345     for (index = n;index >= 1;--index)
346     {
347         swap(unStorted[0],unStorted[index]);
348         HeapAdjust(unStorted,index - 1,0);  //不是HeapAdjust(unStorted,index,0);
349     }
350 }
351 
352 //计数排序，基本实现
353 //此处的基数排序的使用场合：
354 //输入为正数；
355 //    输入不重复；
356 //输入的最大数与输入的个数基本相等时空间利用率最高，也就是输入为0~n内的n个不重复的正数
357 void CountSortBasic_1(DataType *unStorted,size_t n)
358 {
359     assert(NULL != unStorted);
360 
361     size_t *hash = new size_t [n + 1];
362     size_t cnt = 0;
363     int index =  0;
364 
365     for (index = 0;index <= n;++index)
366     {
367         hash[index] = 0;
368     }
369 
370     for (index = 0;index < n;++index)  //index < n而非index <= n，因为此处访问的是unStorted[index]，最大下标为n-1
371     {
372         ++hash[ unStorted[index] ];
373     }
374 
375     for (index = 0;index <= n;++index)
376     {
377         if (hash[ index ] != 0)   //判断index是否出现
378         {
379             unStorted[cnt++ ] = index;  
380         }
381     }
382 
383     delete [] hash;
384 }
385 
386 //计数排序，位图实现
387 void CountSort(DataType *unStorted,size_t n)
388 {
389     assert(NULL != unStorted);
390 
391     bitset<MaxSize> hash;
392     
393     size_t cnt = 0;
394     int index =  0;
395 
396     hash.reset();
397 
398     for (index = 0;index < n;++index)  //index < n而非index <= n，因为此处访问的是unStorted[index]，最大下标为n-1
399     {
400         hash.set(unStorted[index]);
401     }
402 
403     for (index = 0;index <= n;++index)
404     {
405         if ( hash.test(index) )
406         {
407             unStorted[cnt++ ] = index;  
408         }
409     }
410 }
411 
412 //测试“脚手架”
413 void TestSortDriver()
414 {    
415     /*DataType *unsortedArray = new DataType[MaxSize];
416     size_t lengthOfUnsortedArray;*/
417     size_t programToTest;
418     
419     int MinRandomInt;
420     int MaxRandomInt;
421     size_t i;
422     int timeStart = 0;
423     double timeCostAverage = 0;
424 
425     //用于计数排序时的输入
426     DataType  unsortedArray[10]= {2,0,9,8,4,5,3,7,1,6};
427     size_t lengthOfUnsortedArray = 10;
428     
429 
430     cout<<"please enter the length Of UnsortedArray,MinRandomInt and MaxRandomInt :"<<endl;
431     cin>>lengthOfUnsortedArray>>MinRandomInt>>MaxRandomInt;
432     cout<<"please enter the identifier of the program to test (end with ctrl+z): "<<endl;
433     while (cin>>programToTest)
434     {
435         for (i = 0;i < lengthOfUnsortedArray;++i)  //准备待排序数组
436         {
437             unsortedArray[i] = RandomIntGenerate(MinRandomInt,MaxRandomInt);
438         }
439 
440         cout<<"the unsorted array is :"<<endl;
441         DisplayArray(unsortedArray,lengthOfUnsortedArray);
442 
443         timeStart = clock();
444         switch (programToTest)
445         {
446             case 11: 
447                 cout<<"Test SelectSort..."<<endl;
448                 SelectSort(unsortedArray,lengthOfUnsortedArray);
449                 break;
450 
451             case 21: 
452                 cout<<"Test InsertSort..."<<endl;
453                 InsertSort(unsortedArray,lengthOfUnsortedArray);
454                 break;
455 
456             case 22: 
457                 cout<<"Test ShellSort..."<<endl;
458                 ShellSort(unsortedArray,lengthOfUnsortedArray);
459                 break;
460 
461             case 31: 
462                 cout<<"Test BubbleSort..."<<endl;
463                 BubbleSort(unsortedArray,lengthOfUnsortedArray);
464                 break;
465 
466             case 32: 
467                 cout<<"Test QuickSort..."<<endl;
468                 QuickSort(unsortedArray,0,lengthOfUnsortedArray - 1);
469                 break;
470 
471             case 33: 
472                 cout<<"Test HeapSort..."<<endl;
473                 HeapSort(unsortedArray,lengthOfUnsortedArray - 1);
474                 break;
475 
476             case 41: 
477                 cout<<"Test MergeSortNonRecursive..."<<endl;
478                 MergeSortNonRecursive(unsortedArray,lengthOfUnsortedArray);
479                 break;
480 
481             case 42: 
482                 cout<<"Test MergeSort..."<<endl;
483                 MergeSort(unsortedArray,0,lengthOfUnsortedArray - 1);
484                 break;
485 
486 
487             case 51: 
488                 cout<<"Test CountSort..."<<endl;
489                 CountSort(unsortedArray,lengthOfUnsortedArray);
490                 break;
491                 
492             default:
493                 break;
494         }
495 
496         timeCostAverage = 1e9 * ( clock() - timeStart ) / ( CLOCKS_PER_SEC * lengthOfUnsortedArray );
497         cout<<"the average time cost per data is : "<<timeCostAverage<<" ns"<<endl;
498 
499         for (i = 0;i < lengthOfUnsortedArray - 1;++i)
500         {
501             if (unsortedArray[i] > unsortedArray[i + 1])
502             {
503                 cout<<"sort bug i = "<<i<<endl;
504             }
505         }
506 
507         cout<<"the sorted array is :"<<endl;
508         DisplayArray(unsortedArray,lengthOfUnsortedArray);
509 
510         cout<<endl;
511         cout<<"please enter the identifier of the program to test (end with ctrl+z): "<<endl;
512     }
513 
514     //delete [] unsortedArray;
515 }
516 
517 int main()
518 {
519     TestSortDriver();
520 
521     return 0;
522 }