浅谈C++之冒泡排序、希尔排序、快速排序、插入排序、堆排序、基数排序性能对比分析(好戏在后面有图有真相)

1、 最近一段时间去武汉参加了N多笔试，在几次试题中都出现了排序。偏偏出现了我没怎么看的插入排序，弄得我好是纠结。趁回学校的机会把这几个不是很复杂的排序重新复习了一下，借此比较了一下他们的效率。让我有点以外的是在数据量达到1W10W之间，希尔排序竟然比快速排序效率还要高。贴上完整代码！冒泡排序 1 /冒泡排序 2 / 3 void BubleSort(int a,int n) 4 5 int temp; 6 bool flag=false; 7 for (int i=0;in;i+) 8 9 flag=true;10 for (int j=0;jaj+1)13 14 temp=aj;15 aj=aj+1;16 aj+1=temp;17 flag=false;18 19 20 if(flag) break;21 22 冒泡排序的时间复杂度为O(n),在数据比较小的情况下各个算法效率差不多。希尔排序：以前竟然没有发现，希尔排序如此短小精悍的代码。其效率很多时候并不输给快速排序其时间复杂度为O(nlogn)。 1 void ShellSort(int array,int length) 2 3

2、4 5 int d = length/2; /设置希尔排序的增量 6 int i ; 7 int j; 8 int temp; 9 while(d=1) 10 11 for(i=d;i=0 & arrayjtemp) 16 17 arrayj+d=arrayj; 18 j=j-d; 19 20 arrayj+d = temp; 21 22 /Display(array,10); 23 d= d/2; /缩小增量 24 25 快速排序： 1 /快速排序 2 / 3 void Swap(int &a,int &b) 4 5 int temp; 6 temp=a; 7 a=b; 8 b=temp; 9 10 11 int Partition(int a,int p,int r)12 13 int i=p;14 int j=r+1;15 int x=ap;16 while (true)17 18 while(a+ix&ix);20 if (i=j)break;21 Swap(aj,ai);22 23 24 ap=aj;25 aj=x;26 return j;27 28 29 void Quic

3、kSort(int a,int p,int r)30 31 if (p=0)&(key0)20 21 InsertionSort(a,n-1);22 Insert(a,n);23 24 else return;25 算法效率和冒泡排序相差无几，时间复杂度为O(n)。这里要注意的问题是由于不断地递归，栈的不断开辟如果数据太大可能会导致栈溢出而不能得到结果。堆排序： 1 /堆排序 2 / 3 int Parent(int i) 4 5 return i/2; 6 7 int Left(int i) 8 9 return 2*i;10 11 int Right(int i)12 13 return 2*i+1;14 15 16 /把以第i个节点给子树的根的子树调整为堆17 void MaxHeap(int *a,int i,int length)18 19 int L=Left(i);20 int R=Right(i);21 int temp;22 int largest; /记录子树最大值的下表，值可能为根节点下标、左子树下表、右子树下标23 if (Lai-1) /length是递归返回

4、的条件24 25 largest=L;26 27 else largest=i;28 if (Ralargest-1) /length是递归返回的条件29 largest=R;30 if (largest!=i)31 32 temp=ai-1;33 ai-1=alargest-1;34 alargest-1=temp;35 MaxHeap(a,largest,length);36 37 38 39 void BuildMaxHeap(int *a,int length)40 41 42 for (int i=length/2;i=1;i-)43 MaxHeap(a,i,length);44 45 46 void HeapSort(int *a,int length)47 48 BuildMaxHeap(a,length);49 for (int i=length;i0;i-)50 51 int temp;52 temp=ai-1;53 ai-1=a0;54 a0=temp;55 length-=1;56 MaxHeap(a,1,length);57 58 通过使用大根堆来排序，排序过程

5、中主要的动作就是堆的调整。每次把堆的根节点存入到堆的后面，然后把最后一个节点交换到根节点的位置，然后又调整为新的堆。这样不断重复这个步骤就能把把一个数组排列的有序，时间复杂度为O(nlogn)。最后一种是比较特别的基数排序（属于分配式排序，前几种属于比较性排序）又称“桶子法”：基本思想是通过键值的部分信息分配到某些桶中，藉此达到排序的作用，基数排序属于稳定的排序，其时间复杂度为O(nlog(r)m),r为所采取的的基数，m为堆的个数，在某些情况下基数排序法的效率比其他比较性排序效率要高。 1 /基数排序 2 / 3 int GetMaxTimes(int *a,int n) 4 5 int max=a0; 6 int count=0; 7 for (int i=1;imax)10 max=ai;11 12 while(max)13 14 max=max/10;15 count+;16 17 return count;18 19 20 void InitialArray(int *a,int n)21 22 for (int i=0;in;i+)23 ai=0;24 25 26 / void InitialArray1(int a,int m,int n)27 / 28

《浅谈C++之冒泡排序、希尔排序、快速排序、插入排序、堆排序、基数排序性能对比分析(好戏在后面有图有真相)》由会员cn****1分享，可在线阅读，更多相关《浅谈C++之冒泡排序、希尔排序、快速排序、插入排序、堆排序、基数排序性能对比分析(好戏在后面有图有真相)》请在金锄头文库上搜索。