牛小飞《数据结构》7.3归并排序和快速排序

归并排序和交换类排序,起泡排序,快速排序7.7,归并排序7.6,小结和作业,交换类排序,归并排序,归并排序的过程基于下列基本思想进行：将两个或两个以上的有序子序列“归并”为一个有序序列。,归并排序,归并排序中的基本操作是合并两个已排序的表。其中的合并算法是取两个输入数组A和B，一个输出数组C，以及3个计数器Actr,Bctr,Cctr。,1,13,24,26,2,15,27,38,1,2,13,15,24,26,27,38,归并排序,在内部排序中，通常采用的是2-路归并排序。即：将两个位置相邻的记录有序子序列,有序子序列Rl.m,归并为一个记录的有序序列。,有序序列Tl.n,这个操作对顺序表而言，是轻而易举的。,有序子序列Rm+1.n,归并两个有序序列算法,publicstaticvoidMerge(AnyTypea,AnyTypetmpArray,intleftPos,intrightPos,intrightEnd)/将有序序列aleftPos.rightPos-1和arightPos.rightEnd归并为有序序列/tmpArrayleftPos.rightEndintleftEnd=rightPos-1;/第一个有序序列的最后元素位置inttmpPos=leftPos;/归并后序列的下标intnumElements=rightEnd-leftPos+1;/共有的数据元素个数while(leftPosvoidMerge(AnyTypea,AnyTypetmpArray,intleftPos,intrightPos,intrightEnd)while(leftPos=leftEnd)/将剩余的aleftPos.leftEnd复制到/tmpArray中tmpArraytmpPos+=aleftPos+;while(rightPosvoidBubbleSort(AnyTypea)for(inti=a.length-1;i0;i-)for(intj=0;j0)SwapReferences(a,j,j+1);,起泡排序,1.每一趟起泡排序都是将待排序序列中最大的关键字移动到最后一个记录的位置上。,2.起泡排序的结束条件为，最后一趟没有进行“交换记录”。,3.一般情况下，每经过一趟“起泡”，“i减一”，但并不是每趟都如此。,起泡排序,例如:,2,5,5,3,1,5,7,9,8,9,i=7,i=6,1,3,i=2,起泡排序改进算法,publicstaticvoidBubbleSort(AnyTypea)inti=a.length-1;/比较i个数中的最大值，结果放入ai-1中while(i0)intlastExchangeIndex=0;for(intj=0;ji;j+)if(aj+1.compareTo(aj)AnyTypemedian3(AnyTypea,intleft,intright)intcenter=(left+right)/2;if(pareTo(aleft)0)SwapReferences(a,left,center);if(pareTo(aleft)CUTOFF)/当数组元素的个数大于CUTOFF时，采用快速排序，否则采用插入排序。AnyTypepivot=median3(a,left,right);/选择枢轴/一次快速划分排序QuickSort(a,left,i-1);QuickSort(a,i+1,right);elseInsertionSort(a,left,right);/插入排序,/一次快速划分排序inti=left,j=right-1;for(;)while(a+pareTo(pivot)0)/找到第一个大于pivot的元素if(ij)SwapReferences(a,i,j);elsebreak;SwapReferences(a,i,right-1);/一次快速排序结束。以i为界，i+1right的数据一定都大于pivot,left-i-1的数据一定都小于pivot,快速排序算法,快速排序-性能分析,假设一次划分所得枢轴位置i=k，则对n个记录进行快速排序所需时间：,其中Tpass(n)为对n个记录进行一次划分所需时间，和记录数n成正比，可用cn表示。,T(n)=Tpass(n)+T(k-1)+T(n-k),若待排序列中记录的关键字是随机分布的，则k取1至n中任意一值的可能性相同。,快速排序-性能分析,结论:在所有同数量级O(nlogn)的排序方法中快速