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

归并排序和交换类排序归并排序和交换类排序起泡排序起泡排序快速排序快速排序7.7归并排序归并排序7.6小结和作业小结和作业交换类排序交换类排序归并排序归并排序归并排序的过程基于下列基本思想进行：归并排序的过程基于下列基本思想进行：将两个或两个以上的有序子序列“归并”为一个有序序列。归并排序归并排序归并排序中的基本操作是归并排序中的基本操作是合并合并两个已排序的表。其中的两个已排序的表。其中的合并算法是取两个输入数组合并算法是取两个输入数组A和和B，一个输出数组，一个输出数组C，以，以及及3个计数器个计数器Actr,Bctr,Cctr。1132426Actr2152738BctrCctr12ActrCctrCctrCctrCctr CctrCctrCctrActr ActrBctr Bctr Bctr131524262738归并排序归并排序在内部排序中，通常采用的是在内部排序中，通常采用的是2-2-路归并排序路归并排序。即：。即：将两个位置相邻的记录有序子序列将两个位置相邻的记录有序子序列有序子序列有序子序列 Rl.m归并为一个记录的有序序列归并为一个记录的有序序列。有有 序序 序序 列列 Tl.n这个操作对顺序表而言，是轻而易举的。这个操作对顺序表而言，是轻而易举的。有序子序列有序子序列 Rm+1.n归并两个有序序列算法归并两个有序序列算法public static AnyType extends Comparable 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&rightPos=rightEnd)if(aleftPpareTo(arightPos)=0)tmpArraytmpPos+=aleftPos+;else tmpArraytmpPos+=arightPos+;归并两个有序序列算法归并两个有序序列算法public static AnyType extends Comparable 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,8036,6814366836,6814,36,68 14,23,36,52,68,80 23归并排序算法归并排序算法public static AnyType extends Comparable 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 AnyType extends Comparable 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.nR1.n的状态为：的状态为：第第 i 趟起泡排序趟起泡排序无序序列无序序列R1.n-i+1有序序列有序序列 Rn-i+2.nn-i+1无序序列无序序列R1.n-i有序序列有序序列 Rn-i+1.n比较相邻记录，将关键字比较相邻记录，将关键字最大的记录最大的记录交换到交换到 n-i+1 的位置上的位置上起泡排序起泡排序306597 76132738 0 1 2 3 4 5 6 7494938jj+19776971397279730jj+1jj+1jj+1jj+1jj+1jj+1第一趟起泡排序过程第一趟起泡排序过程976576 13273049 0 1 2 3 4 5 6 738第一趟起泡排序后的结果第一趟起泡排序后的结果起泡排序起泡排序976576 13273049 0 1 2 3 4 5 6 738976576 13273049 0 1 2 3 4 5 6 73813762776307676第二趟第二趟976513 27303049 0 1 2 3 4 5 6 738136565307676第三趟第三趟276565971327 30303049 0 1 2 3 4 5 6 738494949307676第四趟第四趟6565134927起泡排序起泡排序971327 30303049 0 1 2 3 4 5 6 738494949307676第四趟第四趟656513492797273013 0 1 2 3 4 5 6 7384976第五趟第五趟651338273838303897303027 0 1 2 3 4 5 6 7134976第六趟第六趟65383830起泡排序起泡排序朴素算法朴素算法public static AnyType extends Comparable 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 i减一减一”，但并不是每趟都如此。，但并不是每趟都如此。起泡排序起泡排序例如例如:25531579 89i=7i=613i=2起泡排序起泡排序改进算法改进算法public static AnyType extends Comparable 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(nO(n2 2)时间复杂度：时间复杂度：稳定性：稳定性：是一种是一种稳定稳定的排序方法的排序方法n-1快速排序快速排序-基本思想基本思想快速排序是于快速排序是于19621962年提出的一种年提出的一种划分交换排序。也是一种划分交换排序。也是一种分治分治的策略。的策略。快速排序快速排序-基本思想基本思想将数组将数组S S快速排序的基本算法由四步组成：快速排序的基本算法由四步组成：1.如果如果S中元素的个数是中元素的个数是0或者或者1，则返回。，则返回。2.取取S中任一个元素中任一个元素v，称之为枢纽元或者枢轴，称之为枢纽元或者枢轴(pivot)。3.将将S-v划分成两个不相交的集合划分成两个不相交的集合S1和和S2:S1=xS-v|xv,S2=xS-v|xv4.返回返回quicksort(S1)后跟后跟v，继而返回，继而返回quicksort(S2)快速排序快速排序-基本思想基本思想首先对无序序列进行首先对无序序列进行“一次划分一次划分”，之后，之后分别分别对分对分割所得两个子序列割所得两个子序列“递归递归”进行快速排序进行快速排序。143652586149239780750 1 2 3 4 5 6 7 8 9 1052枢轴枢轴对对S1再进行快速排序再进行快速排序对对S2再进行快速排序再进行快速排序对枢轴元素的选取形成了不同的设计决策。比较理想的对枢轴元素的选取形成了不同的设计决策。比较理想的情况是情况是S1,S2尽可能具有一样多的元素。很像我们希望的尽可能具有一样多的元素。很像我们希望的二叉树保持平衡。二叉树保持平衡。快速排序快速排序-选取枢轴选取枢轴错误的做法：错误的做法：三数中值分割法三数中值分割法(Median-of-Tree Partitioning)将第一个元素作为枢轴；将第一个元素作为枢轴；选取前两个互异的关键字中的较大者作为枢轴。选取前两个互异的关键字中的较大者作为枢轴。安全的做法：安全的做法：随机选择枢轴。随机选择枢轴。使用左端、右端和中心位置上的三个元素的中值作为枢轴。使用左端、右端和中心位置上的三个元素的中值作为枢轴。v=68149635270快速排序快速排序-分割策略分割策略1.1.将枢轴与最后的元素交换使得枢轴离开被分割的数据段。将枢轴与最后的元素交换使得枢轴离开被分割的数据段。81496352708149035276ij快速排序快速排序-分割策略分割策略2.2.将大元素推向数组的右边，将小元素推向数组的左边。将大元素推向数组的右边，将小元素推向数组的左边。8149035276ijj28ij59ij3.3.将枢轴与将枢轴与i i所指的元素交换。所指的元素交换。2145039876ij69位置位置pj的每一个元素都是大元素。的每一个元素都是大元素。快速排序举例快速排序举例 i13 81 92 43 65 31 57 260750 1 2 3 4 5 6 7 8 9pivot=65065 j i26 j i5781 i j13 26 57 43031 65 81 92 75一次快速排序过程：一次快速排序过程：92 i j i i快速排序举例快速排序举例13,81,92,43,65,31,57,26,0,75pivot=6513,26,57,43,0,31 65 81,92,75pivot=3113,26,0 31 43,57 75 81 92pivot=81pivot=130 13 260，13，26,31，43，57，65，75，81，92快速排序算法快速排序算法三数中值分割法三数中值分割法private static AnyType extends Comparable 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;快速排序算法快速排序算法public static AnyType extends Comparable 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=ki=k，则对，则对n n 个记录个记录进行快速排序所需时间：进行快速排序所需时间：其中其中 T Tpasspass(n n)为对为对 n n 个记录进行一次划分所需时间，个记录进行一次划分所需时间，和记录数和记录数n n成正比，可用成正比，可用cncn表示。表示。T(T(n n)=T)=Tpasspass(n n)+T()+T(k-1k-1)+T()+T(n-kn-k)若待排序列中记录的关键字是随机分布的，则若待排序列中记录的关键字是随机分布的，则 k k 取取 1 1 至至 n n 中任意一值的可能性相同。中任意一值的可能性相同。快速排序快速排序-性能分析性能分析结论结论:在所有同数量级在所有同数量级O(nlogn)的排序方法中快速的排序方法中快速排序平均性能最好。排序平均性能最好。快速排序是一种不稳定的排序方法。快速排序是一种不稳定的排序方法。小结和作业小结和作业交换类排序交换类排序 交换类排序的基本思想交换类排序的基本思想 起泡排序起泡排序 快速排序快速排序基本思想基本思想 算法算法实例模拟实例模拟 时间复杂度时间复杂度重点：重点：掌握算法的设计思想；手工排序方法；算法；掌握算法的设计思想；手工排序方法；算法；算法的时间复杂度和空间复杂度。算法的时间复杂度和空间复杂度。归并排序归并排序基本思想基本思想 算法算法实例模拟实例模拟 时间复杂度时间复杂度作业：作业：P213,7.15（用快速排序和归并排序完成）（用快速排序和归并排序完成）