C排序算法总结及性能大致分析.doc

这里讲的排序默认为内排序。参考书籍： 数据结构(C语言版) 秦玉平 马靖善 主编 冯佳昕 周连秋 副主编清华大学出版社按照排序过程中依据的原则不同划分为：（1） 插入排序 包括直接插入排序，折半插入排序，2_路插入排序，shell排序（2） 交换排序 包括简单交换排序，冒泡排序，快速排序（3） 选择排序 包括简单选择排序，*树形选择排序，*堆排序（4） 归并排序 （5） 计数排序 包括*计数排序，基数排序*上面打星号的代码没有添加*下面代码修改自/%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/5ad1f372177b21158701b093.html主要修改了快速排序的错误，添加了折半插入排序和2_路插入排序，而且按照以上(1)(5)重新改写了程序的结构。代码如下：排序头文件：sort.h#ifndef _SORT_H_#define _SORT_H_/*/* 排序头文件 */*/*/* 头文件包含 */#include insertSort.h#include exchangeSort.h#include selectSort.h#include mergeSort.h#include countSort.h/*/#endif（1）插入排序：insertSort.h#ifndef _INSERTSORT_H_#define _INSERTSORT_H_/*/*常用头文件包含*/#include using namespace std;/*/*/*插入排序的思想插入排序属于插入方法的排序算法，它的想法是从第一个元素开始，创建有序序列，把未排序序列依次插入到有序序列中，以此类推*/*/*函数实现，按从小到大排序*/template void insertSort(vector& v)/*直接插入排序*/for (unsigned int i = 1; i = 0 & vj tmp) vj+1 = 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; else high = mid - 1; int j = i - 1; while (j = 0 & vj tmp) vj+1 = vj; j-; vj+1 = tmp;template void binInsertSort(vector& v)/*2_路查找排序*/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; else high = mid - 1; for (j = final; j = low; j-) vecTmpj+1 = vecTmpj; vecTmplow = tmp; final+; else if (first = 0) first = siz - 1; vecTmpsiz-1 = tmp; else low = first; high = siz - 1; while (low vecTmpmid) low = mid + 1; else high = 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;/*/* 希尔排序 */*希尔排序的思想希尔排序属于插入方法的排序算法，可以说是插入排序算法的改进版本，它的想法是把数据分组，在分组内进行插入排序，以此类推，分组的大小跟数据量有关系，D. E. Knuth建议数据量很大时按3*n+1分组，例如100的数据时，可以取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 int i = group; i =0 & vj tmp) vj+count = vj; j -= count; vj+count = tmp; /*/*/#endif（2）交换排序：exchangeSort.h#ifndef _EXCHANGESORT_H_#define _EXCHANGESORT_H_/*/*常用头文件包含*/#include /*要用template void swap(Type& _Left,Type& _Right);*/#include #include using namespace std;/*/*/*交换排序的思想交换排序属于比较法的排序算法，它的想法是扫描整个数据，从第0个元素开始，跟以后的元素逐个比较，按照排序规则(从小到大或者从大到小)交换顺序，比较完第a后再去比较第a+1个元素，以此类推*/*函数实现，按从小到大排序*/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); /*/*冒泡排序的思想冒泡排序属于比较法的排序算法，它的想法是比较相邻的两个数据，按照排序规则(从小到大或者从大到小)交换顺序，再去比较下一组相邻元素，以此类推*/*/*函数实现，按从小到大排序*/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; /*/*/*快速排序的思想快速排序的想法是尽可能的减少每次排序的数据量以提高效率，那么对于任意从数据中取出的数据，可以按照大小把比它小的放在它的左边，比它大的放在它的右边，那么这个数的位置就确定了，再在它的左右两边分别按此排序，这就是快速排序。*/*函数实现，按从小到大排序*/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 vhigh) swap(vpivot,vhigh); if (high left) quickSort(v,left,high-1); if (low right) quickSort(v,low,right); /*/#endif（3）选择排序：selectSort.h#ifndef _SELECTSORT_H_#define _SELECTSORT_H_/*/*常用头文件包含*/#include /*要用template void swap(Type& _Left,Type& _Right);*/#include using namespace std;/*/*/*选择排序的思想选择排序属于选择法的排序算法，它的想法是按照排序规则(从小到大或者从大到小)查找最小(大)的元素，并与第一个元素交换，再在剩下的元素中重复此过程以此类推*/*/*/*函数实现，按从小到大排序*/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（4）归并排序：mergeSort.h#ifndef _MERGESORT_H_#define _MERGESORT_H_/*/*常用头文件包含*/#include /*要用template void swap(Type& _Left,Type& _Right);*/#include using namespace std;/*/*/*归并排序的思想归并排序的思想跟快排序类似，即先不断地把数据分割至每组只有一个数据，然后在按大小归并成一组有序数。*/*函数实现，按从小到大排序*/template void mergeSort(vector& v,unsigned int left, unsigned int right)unsigned int half;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按始末位置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（5）计数排序：countSort.h#ifndef _COUNTSORT_H_#define _COUNTSORT_H_/*/*常用头文件包含*/#include #include using namespace std;/*/*/*基数排序的思想基数排序是根据数字的性质来进行的排序算法，它首先分离出个位数，并把原数据按照个位数大小依次排序，得到一个排序结果，再将这个排序结果按照十位数的大小在进行排序，以此类推，知道最高位排序即完成。基数排序必须是正整数。*/*函数实现，按从小到大排序*/unsigned int findMax(vector v);unsigned int findk(unsigned 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; for (int i = 0; i 10; i+) for (int k = 0; k noCounti; k+) vindex+ = vTmpik; unsigned int findMax(vector v)/函数查找最大数的位数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)/函数查找正整数的第k位上的数字 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;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); vector 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 += 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; cout *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()-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 mergeSort: 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+) averTimej += averjk; averTimej /= TESTTIME; out averTimej endl;out.close();return 0;计时器代码以及随机数产生代码请分别参阅：/%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/a0421781846ea8de9123d9fa.html/%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/d3f21efca0061f4cd6887d28.html程序运行结果：这是第1次测试！insertSort:8063biInsertSort:8109binInsertSort:4828shellSort:94exchageSort:18468bubbleSort:18672quickSort:63selectSort:12593mergeSort:641radixSort:63这是第2次测试！insertSort:8031biInsertSort:8110binInsertSort:4859shellSort:94exchageSort:18469bubbleSort:18703quickSort:62selectSort:12531mergeSort:625radixSort:63这是第3次测试！insertSort:8062biInsertSort:8141binInsertSort:2719shellSort:94exchageSort:18546bubbleSort:18813quickSort:78selectSort:12625mergeSort:641radixSort:47这是第4次测试！insertSort:8047biInsertSort:8109binInsertSort:5328shellSort:94exchageSort:18531bubbleSort:18735quickSort:63selectSort:12562mergeSort:641radixSort:62这是第5次测试！insertSort:8062biInsertSort:8125binInsertSort:4625shellSort:94exchageSort:18641bubbleSort:18781quickSort:78selectSort:12594mergeSort:640radixSort:47这是第6次测试！insertSort:8093biInsertSort:8172binInsertSort:3078shellSort:93exchageSort:18563bubbleSort:18829quickSort:78selectSort:13468mergeSort:688radixSort:47这是第7次测试！insertSort:8797biInsertSort:8671binInsertSort:2813shellSort:93exchageSort:19094bubbleSort:19578quickSort:78selectSort:13156mergeSort:656radixSort:63这是第8次测试！insertSort:8313biInsertSort:8422binInsertSort:4125shellSort:109exchageSort:19125bubbleSort:19328quickSort:63selectSort:13188mergeSort:672radixSort:62这是第9次测试！insertSort:8266biInsertSort:8391binInsertSort:3937shellSort:94exchageSort:19141bubbleSort:18703quickSort:78selectSort:12562mergeSort:657radixSort:46这是第10次测试！insertSort:8312biInsertSort:8360binInsertSort:3500shellSort:94exchageSort:19187bubbleSort:19484quickSort:62selectSort:13266mergeSort:703radixSort:62这是第11次测试！insertSort:8313biInsertSort:8500binInsertSort:3593shellSort:94exchageSort:19015bubbleSort:19078quickSort:79selectSort:13047mergeSort:656radixSort:47这是第12次测试！insertSort:8422biInsertSort:8375binInsertSort:2813shellSort:109exchageSort:18906bubbleSort:19094quickSort:63selectSort:12656mergeSort:641radixSort:47这是第13次测试！insertSort:8016biInsertSort:8109binInsertSort:4360shellSort:78exchageSort:18266bubbleSort:18547quickSort:63selectSort:12750mergeSort:640radixSort:47这是第14次测试！insertSort:8000biInsertSort:8109binInsertSort:2953shellSort:94exchageSort:18438bubbleSort:18562quickSort:63selectSort:12547mergeSort:641radixSort:47这是第15次测试！insertSort:7906biInsertSort:8078binInsertSort:3547shellSort:94exchageSort:18391bubbleSort:18656quickSort:78selectSort:12687mergeSort:656radixSort:47这是第16次测试！insertSort:7953biInsertSort:8094binInsertSort:5000shellSort:94exchageSort:19015bubbleSort:18954quickSort:63selectSort:13063mergeSort:656radixSort:63这是第17次测试！insertSort:8266biInsertSort:8344binInsertSort:3453shellSort:93exchageSort:18844bubbleSort:18938quickSort:62selectSort:12828mergeSort:640radixSort:47这是第18次测试！insertSort:8156biInsertSort:8344binInsertSort:4500shellSort:109exchageSort:19000bubbleSort:19110quickSort:78selectSort:12859mergeSort:625radixSort:63这是第19次测试！insertSort:8203biInsertSort:8437binInsertSort:3188shellSort:94exchageSort:19046bubbleSort:19391quickSort:78selectSort:12781mergeSort:625radixSort:47这是第20次测试！insertSort:7984biInsertSort:8125binInsertSort:3391shellSort:94exchageSort:18765bubbleSort:18922quickSo