C++排序算法總結(jié)及性能大致分析

1、這里講的排序默認(rèn)為內(nèi)排序。參考書籍：數(shù)據(jù)結(jié)構(gòu)（C語言版）秦玉平 馬靖善 主編馮佳昕 周連秋 副主編 清華大學(xué)出版社 按照排序過程中依據(jù)的原則不同劃分為：(1)插入排序包括直接插入排序，折半插入排序，2路插入排序，shell排 序( 2) 交換排序 包括簡單交換排序，冒泡排序，快速排序( 3) 選擇排序 包括簡單選擇排序， *樹形選擇排序， *堆排序( 4) 歸并排序( 5) 計數(shù)排序 包括*計數(shù)排序，基數(shù)排序*上面打星號的代碼沒有添加*下面代碼修改自 HYPERLINK /%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/5adlf372177b21 /%D0%E3%B2%

2、C5%CC%AB%CA%D8/blog/item/5adlf372177b21 158701b093.html主要修改了快速排序的錯誤，添加了折半插入排序和2路插入排序，而且按照 以上(1)(5)重新改寫了程序的結(jié)構(gòu)。代碼如下：排序頭文件： sort.h#ifndef _SORT_H_#define _SORT_H_/* */* 排序頭文件 */ /* */*/* 頭文件包含 */#include insertSort.h#include exchangeSort.h#include selectSort.h#include mergeSort.h#include countSort.h/*/

3、#endif插入排序：insertSort.h#ifndef _INSERTSORT_H_#define _INSERTSORT_H_/* */*常用頭文件包含*/#include using namespace std;/* */* */*插入排序的思想 插入排序?qū)儆诓迦敕椒ǖ呐判蛩惴?，它的想法是從第一個元素開始，創(chuàng)建 有序序列，把未排序序列依次插入到有序序列中，以此類推*/* */*函數(shù)實現(xiàn)，按從小到大排序*/template void insertSort(vector& v)/*直接插入排序*/for (unsigned int i = 1; i = 0 & vj tmp)vj+1 =

4、 vj;j-;vj+1 = tmp;template void biInsertSort(vector& v) /*折半插入排序*/for (unsigned int i = 1; i v.size(); i+) T tmp = vi;int low = 0;int high = i - 1;while (low vmid)low = mid + 1;elsehigh = mid - 1;int j = i - 1;while (j = 0 & vj tmp)vj+1 = vj;j-;vj+1 = tmp;template void binInsertSort(vector& v) /*2_路

5、查找排序*/ vector vecTmp(v);int first,final,low,high,mid,k,j; unsigned int i,siz;siz = v.size();first = final = 0;for (i = 1; i = vecTmp0)low = 0;high = final;while (low vecTmpmid)low = mid + 1;elsehigh = mid - 1;for (j = final; j = low; j-)vecTmpj+1 = vecTmpj;vecTmplow = tmp;final+;elseif (first = 0)fi

6、rst = siz - 1; vecTmpsiz-1 = tmp;elselow = first;high = siz - 1;while (low vecTmpmid)low = mid + 1;elsehigh = mid - 1;for (j = first; j = high; j+)vecTmpj-1 = vecTmpj;vecTmphigh = tmp;first-;for (i = 0,j = first; j siz; i+,j+)vi = vecTmpj;for (k = 0; k = final; k+)vi+ = vecTmpk;/* */* 希爾排序 */*希爾排序的思

7、想 希爾排序?qū)儆诓迦敕椒ǖ呐判蛩惴?，可以說是插入排序算法的改進(jìn)版本， 它的想法是把數(shù)據(jù)分組，在分組內(nèi)進(jìn)行插入排序，以此類推，分組的大小跟數(shù)據(jù)量有關(guān)系，D. E. Knuth建議數(shù)據(jù)量很大時按3*n+l分組，例如100 的數(shù)據(jù)時，可以取 1， 4， 13， 40。*/template void shellSort(vector& v)for (unsigned int count = (unsigned int)v.size()/2; count 0; count /=2)for(unsigned int group = 0; group count; group+)for (unsigned

8、int i = group; i =0 & vj tmp)vj+count = vj;j -= count;vj+count = tmp;/* */* */#endif交換排序:exchangeSort.h#ifndef _EXCHANGESORT_H_#define _EXCHANGESORT_H_/* */*常用頭文件包含*/#include /*要用 template void swap(Type& _Left,Type& _Right);*/#include #include using namespace std;/* */* */*交換排序的思想 交換排序?qū)儆诒容^法的排序算法，它的

9、想法是掃描整個數(shù)據(jù)，從第 0 個元素 開始，跟以后的元素逐個比較，按照排序規(guī)則(從小到大或者從大到小)交換 順序，比較完第a后再去比較第a+1個元素，以此類推*/*函數(shù)實現(xiàn)，按從小到大排序*/template void exchageSort(vector& v)for (unsigned int i = 0; i v.size()-1; i+)for (unsigned int j = i + 1; j vj)swap(vi,vj);/* */*冒泡排序的思想 冒泡排序?qū)儆诒容^法的排序算法，它的想法是比較相鄰的兩個數(shù)據(jù)，按照排序 規(guī)則(從小到大或者從大到小)交換順序，再去比較下一組相鄰元素，

10、以此類推 */* */*函數(shù)實現(xiàn)，按從小到大排序*/template void bubbleSort(vector& v)bool flag = true;for (unsigned int i = 0; (i v.size()-1) & (flag); i+)flag = false;for (unsigned int j = 0; j vj+1)swap(vj,vj+1);flag = true;/* */ /* */*快速排序的思想快速排序的想法是盡可能的減少每次排序的數(shù)據(jù)量以提高效率，那么對于任意從數(shù)據(jù)中取出的數(shù)據(jù)，可以按照大小把比它小的放在它的左邊，比它 大的放在它的右邊，那么這個數(shù)

11、的位置就確定了，再在它的左右兩邊分別 按此排序，這就是快速排序。*/*函數(shù)實現(xiàn)，按從小到大排序*/template void quickSort(vector& v,unsigned int left, unsigned int right)if (left right)unsigned int pivot = left;unsigned int low = left + 1;unsigned int high = right;while (low high)while(low high & vlow = vpivot)low+;while(low = vpivot)high-;if (low

12、 vhigh)swap(vpivot,vhigh);if (high left)quickSort(v,left,high-1);if (low right)quickSort(v,low,right);/* */#endif選擇排序：selectSort.h#ifndef _SELECTSORT_H_#define _SELECTSORT_H_/* */*常用頭文件包含*/#include /*要用 template void swap(Type& _Left,Type& _Right);*/ #include using namespace std;/* */* */*選擇排序的思想 選擇

13、排序?qū)儆谶x擇法的排序算法，它的想法是按照排序規(guī)則(從小到大或者 從大到小)查找最小(大)的元素，并與第一個元素交換，再在剩下的元素中 重復(fù)此過程以此類推*/* */* */*函數(shù)實現(xiàn)，按從小到大排序*/template void selectSort(vector& v)for (unsigned int i = 0; i v.size()-1; i+)unsigned int min = i;for (unsigned int j = i + 1; j vj)min = j;swap(vi,vmin);/ /#endif歸并排序:mergeSort.h#ifndef _MERGESORT_H

14、_#define _MERGESORT_H_/* */*常用頭文件包含*/#include /*要用 template void swap(Type& _Left,Type& _Right);*/ #include using namespace std;/* */* */*歸并排序的思想 歸并排序的思想跟快排序類似，即先不斷地把數(shù)據(jù)分割至每組只有一個數(shù)據(jù)， 然后在按大小歸并成一組有序數(shù)。*/*函數(shù)實現(xiàn)，按從小到大排序*/template void mergeSort(vector& v,unsigned int left, unsigned int right)unsigned int ha

15、lf;if (left right)half = (left + right) / 2;mergeSort(v,left,half); mergeSort(v,half + 1,right);merge(v,left,v,left,half,v,half+1,right); template void merge(vector&v, unsigned int left,vector A, unsigned int leftA, unsigned int rightA, vector B, unsigned int leftB, unsigned int rightB) /歸并，把向量 A 按始

16、末位置 leftA，rightA，/向量 B 按始末位置 leftB，rightB ,/ 排序歸并到 v 中 unsigned int indexA = leftA; unsigned int indexB = leftB;while (indexA = rightA & indexB BindexB) vleft+ = BindexB+;else vleft+ = AindexA+; while (indexA = rightA)vleft+ = AindexA+;while (indexB = rightB)vleft+ = BindexB+;/*/ #endif計數(shù)排序:countSor

17、t.h #ifndef _COUNTSORT_H_#define _COUNTSORT_H_/* */*常用頭文件包含*/#include #include using namespace std;/* */* */*基數(shù)排序的思想 基數(shù)排序是根據(jù)數(shù)字的性質(zhì)來進(jìn)行的排序算法，它首先分離出個位數(shù)，并把 原數(shù)據(jù)按照個位數(shù)大小依次排序，得到一個排序結(jié)果，再將這個排序結(jié)果按 照十位數(shù)的大小在進(jìn)行排序，以此類推，知道最高位排序即完成。 基數(shù)排序必須是正整數(shù)。*/*函數(shù)實現(xiàn)，按從小到大排序*/unsigned int findMax(vector v);unsigned int findk(unsigne

18、d int num,unsigned int kth);void radixSort(vector& v)unsigned int no;unsigned int count = findMax(v);vectorvector vTmp (10,vector(v.size();for (unsigned int i = 1; i = count; i+)int noCount10 = 0;for (unsigned int j = 0; j v.size(); j+)no = findk(vj,i);vTmpnonoCountno = vj;noCountno+;int index = 0;f

19、or (int i = 0; i 10; i+)for (int k = 0; k noCounti; k+)vindex+ = vTmpik;unsigned int findMax(vector v)/函數(shù)查找最大數(shù)的位數(shù)unsigned int maxx = v0;for (unsigned int i = 1; i v.size(); i+)if (maxx vi)maxx = vi;return (unsigned int)log10(float)maxx) + 1;unsigned int findk(unsigned int num,unsigned int kth)/函數(shù)查找正

20、整數(shù)的第 k 位上的數(shù)字 kth = 1,2,3,.個位，十位，百位int m = 1;for (unsigned int i = 1; i = kth; i+)m *= 10;return (num * 10 / m) % 10;/* */#endif 測試代碼：test.h#include sort.h#include timer.h#include randomNumber.h#include #include using namespace std;const int SIZ = 10000;const int MAX = 10*SIZ;const int TESTTIME = 20;

21、int main()vectorvector aver(10,vector(TESTTIME); vector averTime(10);ofstream out(c:averageTime.txt);for (int i = 0; i TESTTIME; i+)cout 這是第 i+1 次測試！ endl; out 這是第 i+1 次測試！ endl; timer t0,t1,t2,t3,t4,t5,t6,t7,t8,t9; vector v;randomNumber rnd;for (int j = 0; j SIZ; j+)v.push_back(rnd.random(MAX);vect

22、or v0(v); vector v1(v); vector v2(v); vector v3(v); vector v4(v); vector v5(v); vector v6(v); vector v7(v); vector v8(v); vector v9(v);t0.start(); insertSort(v0);t0.stop();aver0i += t0.timeElapse();out insertSort: aver0i endl; cout *insertSort over* endl;t1.start();biInsertSort(v1);t1.stop();aver1i

23、+= t1.timeElapse();out biInsertSort: aver1i endl; cout *biInsertSort over* endl;t2.start();binInsertSort(v2);t2.stop();aver2i += t2.timeElapse();out binInsertSort: aver2i endl; cout *binInsertSort over* endl;t3.start(); shellSort(v3);t3.stop();aver3i += t3.timeElapse();out shellSort: aver3i endl; co

24、ut *shellSort over* endl;t4.start();exchageSort(v4);t4.stop();aver4i += t4.timeElapse();out exchageSort: aver4i endl; cout *exchageSort over* endl;t5.start();bubbleSort(v5);t5.stop();aver5i += t5.timeElapse();out bubbleSort: aver5i endl; cout *bubbleSort over* endl;t6.start(); quickSort(v6,0,v6.size

25、()-1);t6.stop();aver6i += t6.timeElapse();out quickSort: aver6i endl; cout *quickSort over* endl;t7.start(); selectSort(v7);t7.stop();aver7i += t7.timeElapse();out selectSort: aver7i endl; cout *selectSort over* endl;t8.start(); mergeSort(v8,0,v8.size()-1);t8.stop();aver8i += t8.timeElapse();out mer

26、geSort: aver8i endl; cout *mergeSort over* endl;t9.start(); radixSort(v9);t9.stop();aver9i += t9.timeElapse();out radixSort: aver9i endl; cout *radixSort over* endl;for (int j = 0; j 10; j+)for (int k = 0; k TESTTIME; k+)out averjk ;out endl;for (int j = 0; j 10; j+)for (int k = 0; k TESTTIME; k+)av

27、erTimej += averjk; averTimej /= TESTTIME;out averTimej endl;out.close();return 0;計時器代碼以及隨機(jī)數(shù)產(chǎn)生代碼請分別參閱： HYPERLINK /%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/a0421781846ea8 /%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/a0421781846ea8 de9123d9fa.h tml HYPERLINK /%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/d3f21efca0061f /%D0%E3%

28、B2%C5%CC%AB%CA%D8/blog/item/d3f21efca0061f 4cd6887d28.html程序運(yùn)行結(jié)果：這是第 1 次測試！insertSort:8063biInsertSort:8109binInsertSort:4828shellSort:94exchageSort:18468bubbleSort:18672quickSort:63selectSort:12593mergeSort:641radixSort:63這是第2次測試！insertSort:8031biInsertSort:8110binInsertSort:4859shellSort:94exchage

29、Sort:18469bubbleSort:18703quickSort:62selectSort:12531mergeSort:625radixSort:63這是第3次測試！insertSort:8062biInsertSort:8141binInsertSort:2719shellSort:94exchageSort:18546bubbleSort:18813quickSort:78 selectSort:12625 mergeSort:641 radixSort:47 這是第 4 次測試！ insertSort:8047 biInsertSort:8109 binInsertSort:53

30、28 shellSort:94 exchageSort:18531 bubbleSort:18735 quickSort:63 selectSort:12562 mergeSort:641 radixSort:62 這是第 5 次測試！ insertSort:8062 biInsertSort:8125 binInsertSort:4625 shellSort:94 exchageSort:18641 bubbleSort:18781 quickSort:78 selectSort:12594 mergeSort:640 radixSort:47 這是第 6 次測試！ insertSort:8

31、093 biInsertSort:8172 binInsertSort:3078 shellSort:93 exchageSort:18563 bubbleSort:18829 quickSort:78 selectSort:13468 mergeSort:688 radixSort:47 這是第 7 次測試！ insertSort:8797 biInsertSort:8671 binInsertSort:2813 shellSort:93 exchageSort:19094 bubbleSort:19578 quickSort:78 selectSort:13156 mergeSort:65

32、6 radixSort:63 這是第8 次測試！ insertSort:8313 biInsertSort:8422 binInsertSort:4125 shellSort:109 exchageSort:19125 bubbleSort:19328 quickSort:63 selectSort:13188 mergeSort:672 radixSort:62 這是第9 次測試！ insertSort:8266 biInsertSort:8391 binInsertSort:3937 shellSort:94 exchageSort:19141 bubbleSort:18703 quick

33、Sort:78 selectSort:12562 mergeSort:657 radixSort:46 這是第10 次測試！ insertSort:8312 biInsertSort:8360 binInsertSort:3500 shellSort:94 exchageSort:19187 bubbleSort:19484 quickSort:62 selectSort:13266 mergeSort:703 radixSort:62 這是第11 次測試！ insertSort:8313 biInsertSort:8500 binInsertSort:3593 shellSort:94 ex

34、chageSort:19015 bubbleSort:19078 quickSort:79 selectSort:13047 mergeSort:656 radixSort:47 這是第12 次測試！ insertSort:8422 biInsertSort:8375 binInsertSort:2813 shellSort:109 exchageSort:18906 bubbleSort:19094 quickSort:63 selectSort:12656 mergeSort:641 radixSort:47 這是第13 次測試！ insertSort:8016 biInsertSort:

35、8109 binInsertSort:4360 shellSort:78 exchageSort:18266 bubbleSort:18547 quickSort:63 selectSort:12750 mergeSort:640 radixSort:47 這是第14 次測試！ insertSort:8000 biInsertSort:8109 binInsertSort:2953 shellSort:94 exchageSort:18438 bubbleSort:18562 quickSort:63 selectSort:12547 mergeSort:641 radixSort:47 這是

36、第15 次測試！ insertSort:7906 biInsertSort:8078 binInsertSort:3547 shellSort:94 exchageSort:18391 bubbleSort:18656 quickSort:78 selectSort:12687 mergeSort:656 radixSort:47 這是第16 次測試！ insertSort:7953 biInsertSort:8094 binInsertSort:5000 shellSort:94 exchageSort:19015 bubbleSort:18954 quickSort:63 selectSo

37、rt:13063 mergeSort:656 radixSort:63 這是第17 次測試！ insertSort:8266 biInsertSort:8344 binInsertSort:3453 shellSort:93 exchageSort:18844 bubbleSort:18938 quickSort:62 selectSort:12828 mergeSort:640 radixSort:47 這是第18 次測試！ insertSort:8156 biInsertSort:8344 binInsertSort:4500 shellSort:109 exchageSort:19000

38、 bubbleSort:19110 quickSort:78 selectSort:12859 mergeSort:625 radixSort:63 這是第19 次測試！ insertSort:8203 biInsertSort:8437 binInsertSort:3188 shellSort:94 exchageSort:19046 bubbleSort:19391quickSort:78selectSort:12781mergeSort:625radixSort:47這是第20 次測試！insertSort:7984biInsertSort:8125binInsertSort:3391shellSort:94exchageSort:18765bubbleSort:18922quickSort:78selectSort:13031mergeSort:641radixSort:628063 8031 8062 8047 8062 8093 8797 8313 8266 8312 8313 8422