牛小飞数据结构73归并排序和快速排序课件.pptx
归并排序,归并排序的过程基于下列基本思想进行： 将两个或两个以上的有序子序列 “归并” 为一个有序序列。,归并排序,归并排序中的基本操作是合并两个已排序的表。其中的合并算法是取两个输入数组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,归并两个有序序列算法,ublic static void Merge (AnyType a,AnyType tmpArray,int leftPos,int rightPos,int rightEnd) / 将有序序列 aleftPos.rightPos-1 和 arightPos.rightEnd归并为有序序列 /tmpArrayleftPos.rightEnd int leftEnd=rightPos-1; /第一个有序序列的最后元素位置 int tmpPos=leftPos; /归并后序列的下标 int numElements=rightEnd-leftPos+1;/共有的数据元素个数 while(leftPos=leftEnd ,归并两个有序序列算法,ublic static void Merge (AnyType a,AnyType tmpArray,int leftPos,int rightPos,int rightEnd) while(leftPos=leftEnd) / 将剩余的aleftPos.leftEnd复制到 /tmpArray中 tmpArraytmpPos+=aleftPos+; while(rightPos=rightEnd) /将剩余的arightPos.rightEnd复制到 / tmpArray中 tmpArraytmpPos+=arightPos+; /将排序后的有序序列复制到a中 for(int i=0;inumElements;i+,rightEnd-) arightEnd=tmpArrayrightEnd;,归并排序算法描述,如果n=1，只有一个元素需要排序；否则，递归地将前半部分数据和后半部分数据各自归并排序，得到排序后的两部分数据，然后使用合并算法将这两部分合并到一起。,该算法是经典的分治(divide-and-conquer)策略，它将问题分(divide)成一些小的问题然后递归求解，而治(conquer)阶段则将分的阶段结果修补在一起。,归并排序算法演示,52, 23, 80, 36, 68, 14 (s=0, t=5), 52, 23, 80 36, 68, 14, 52, 2380, 52, 23, 52, 23, 52, 80,36, 6814,3668,36, 68,14, 36, 68, 14, 23, 36, 52, 68, 80 ,23,归并排序算法,ublic static void MSort(AnyType a, AnyType b, int left, int right) / 归并排序 if(left=right) bleft=aleft; if (leftright) int center=(left+right)/2; MSort(a,b,left,center); MSort(a,b,center+1,right); Merge(a,b,left,center+1,right); ,归并排序算法,public static void MergeSort(AnyType a) AnyType tmpArray=(AnyType ) new Comparablea.length; MSort(a,tmpArray,0,a.length-1);,归并排序算法性能分析,对 n 个记录进行归并排序的时间复杂度为(nlogn)。因为： 每一趟归并的时间复杂度为 O(n)， 总共需进行 log2n 趟。,需要的辅助存储空间为O(n),稳定的排序,交换类排序,交换排序的基本思想： 依次两两比较相邻关键字，并交换不满足排序要求的关键字，直至全部有序。,主要应用： 1）冒（起）泡排序 2）快速排序,起泡排序,假设在排序过程中，记录序列R1.n的状态为：,第 i 趟起泡排序,无序序列R1.n-i+1,有序序列 Rn-i+2.n,n-i+1,无序序列R1.n-i,有序序列 Rn-i+1.n,比较相邻记录，将关键字最大的记录交换到 n-i+1 的位置上,起泡排序,30,65,97,76,13,27,38,49,49,38,97,76,97,13,97,27,97,30,第一趟起泡排序过程,97,65,76,13,27,30,49,38,第一趟起泡排序后的结果,起泡排序,97,65,76,13,27,30,49,38,97,65,76,13,27,30,49,38,13,76,27,76,30,76,76,第二趟,97,65,13,27,30,30,49,38,13,65,65,30,76,76,第三趟,27,65,65,97,13,27,30,30,30,49,38,49,49,49,30,76,76,第四趟,65,65,13,49,27,起泡排序,97,13,27,30,30,30,49,38,49,49,49,30,76,76,第四趟,65,65,13,49,27,97,27,30,13,38,49,76,第五趟,65,13,38,27,38,38,30,38,97,30,30,27,13,49,76,第六趟,65,38,38,30,起泡排序朴素算法,public static void BubbleSort(AnyType a) for(int i=a.length-1;i0;i-)for(int j=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,起泡排序改进算法,ublic static void BubbleSort(AnyType a) int i = a.length-1;/比较i个数中的最大值，结果放入ai-1中 while(i0) int lastExchangeIndex = 0; for (int j=0; ji; j+) if (aj+pareTo(aj)0) SwapReferences(a,j,j+1); lastExchangeIndex = j; i = lastExchangeIndex; ,起泡排序-性能分析,0,关键字在记录序列中顺序有序）：只需进行一趟起泡,关键字在记录序列中逆序有序）：需进行n-1趟起泡,O(n2),时间复杂度：,稳定性：,是一种稳定的排序方法,n-1,快速排序-基本思想,快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。也是一种分治的策略。,快速排序-基本思想,将数组S快速排序的基本算法由四步组成：,1.如果S中元素的个数是0或者1，则返回。,2.取S中任一个元素v，称之为枢纽元或者枢轴(pivot)。,3.将S-v划分成两个不相交的集合S1和S2: S1=xS-v | xv, S2=xS-v | xv,4.返回quicksort(S1)后跟v，继而返回quicksort(S2),快速排序-基本思想,首先对无序序列进行“一次划分”，之后分别对分割所得两个子序列“递归”进行快速排序。,14,36,52,58,61,49,23,97,80,75,52,枢轴,对S1再进行快速排序,对S2再进行快速排序,对枢轴元素的选取形成了不同的设计决策。比较理想的情况是S1,S2尽可能具有一样多的元素。很像我们希望的二叉树保持平衡。,快速排序-选取枢轴,错误的做法：,三数中值分割法(Median-of-Tree Partitioning),安全的做法：,随机选择枢轴。,使用左端、右端和中心位置上的三个元素的中值作为枢轴。,v=6,快速排序-分割策略,1.将枢轴与最后的元素交换使得枢轴离开被分割的数据段。,快速排序-分割策略,2.将大元素推向数组的右边，将小元素推向数组的左边。,2,8,5,9,3.将枢轴与i所指的元素交换。,6,9,位置pj的每一个元素都是大元素。,快速排序举例,0 1 2 3 4 5 6 7 8 9,pivot=,65,0,65,26,57,81,一次快速排序过程：,92,快速排序举例,13,81,92,43,65,31,57,26,0,75,pivot=65,13, 26, 57, 43, 0, 31 65 81,92, 75,pivot=31,13,26,0 31 43,57,75 81 92,pivot=81,pivot=13,0 13 26,0，13，26,31，43，57，,65，,75，81，92,快速排序算法三数中值分割法,private static AnyType median3(AnyType a,int left,int right)int center=(left+right)/2;if(pareTo(aleft)0)SwapReferences(a,left,center);if(pareTo(aleft)0)SwapReferences(a,left,right);if(pareTo(acenter)0)SwapReferences(a,center,right);SwapReferences(a,center,right-1);return aright-1;,快速排序算法,ublic static void QuickSort(AnyType a,int left,int right) if(right-leftCUTOFF) /当数组元素的个数大于CUTOFF时，采用快速排序，否则采用插入排序。 AnyType pivot=median3(a,left,right);/选择枢轴 /一次快速划分排序 QuickSort(a,left,i-1); QuickSort(a,i+1,right); else InsertionSort(a,left,right); /插入排序,/一次快速划分排序int i=left,j=right-1;for(;) while(a+pareTo(pivot)0) /找到第一个大于pivot的元素 if(ij) SwapReferences(a,i,j); else break;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)的排序方法中快速排序平均性能最好。,快速排序是一种不稳定的排序方法。,小结和作业,重点：掌握算法的设计思想；手工排序方法；算法； 算法的时间复杂度和空间复杂度。,作业：P213,7.15（用快速排序和归并排序完成）,
