归并排序MergeSort.PPT

(两路)归并排序的主算法 template class Type void dataListType :: MergeSort ( ) { //按对象排序码非递减的顺序对表中对象排序 dataListType tempList ( MaxSize ); int len = 1; while ( len CurrentSize ) { MergePass ( tempList, len ); len *= 2; tempList.MergePass ( this, len ); len *= 2; } } 在迭代的归并排序算法中, 函数MergePass( ) 做一趟两路归并排序, 要调用merge ( )函数 ?n/(2*len)? ? O(n/len) 次, 函数MergeSort( )调用MergePass( )正好?log2n? 次,而每次merge( )要执行比较O(len)次, 所以算法总的时间复杂度为O(nlog2n)。 归并排序占用附加存储较多, 需要另外一个与原待排序对象数组同样大小的辅助数组。这是这个算法的缺点。 归并排序是一个稳定的排序方法。 快速排序的算法思想 分治法 分 （难） 合并（容易） 初始关键字： 28 19 27 48 56 12 10 25 20 50 完成第一趟后 20 19 27 25 10 12 28 56 48 50 完成第二趟 12 19 10 20 25 27 28 50 48 56 完成第三趟 10 12 19 20 25 27 28 50 48 56 快速排序的算法 template class Type void dataListType :: QuickSort ( const int left, const int right ) { //在序列 left?right 中递归地进行快速排序 if ( left right) { int pivotpos = Partition ( left, right ); //划分 //对左序列同样处理 QuickSort ( left, pivotpos-1); //对右序列同样处理 QuickSort ( pivotpos+1, right ); } } int dataListType :: Partition (int s, int t ) { int x, i, j; x=Vector[s]; i=s; j=t; while ( i j) { while ( ( i j) (Vector[j]=x) j=j-1; if (ij) a[i]=a[j]; while ( ( i j) (Vector[i]=x) i=i+1; if (ij) a[j]=a[i]; } Vector[i] =x; return i; } 从快速排序算法的递归树可知, 快速排序的趟数取决于递归树的高度。 附加存储开销: 取决于最大递归调用层次数，与递归树的高度一致。 理想情况: ?log2(n+1)? 。因此，附加存储开销为 O(log2n)。 最坏的情况: 待排序对象序列已经按其排序码从小到大排好序的情况下, 其递归树成为单支树, 每次划分只得到一个比上一次少一个对象的子序列。必须经过n-1 趟才能把所有对象定位，附加存储开销为 O(n)。 算法分析 时间开销: 理想情况: O(nlog2n) 最坏的情况: O(n2) 待排序对象把所有对象定位, 而且第 i 趟需要经过 n-i 次排序码比较才能找到第 i 个对象的安放位置，总的排序码比较次数将达到 快速排序是一种不稳定的排序方法。 对于 n 较大的平均情况而言, 快速排序是“快速”的, 但是当 n 很小时, 这种排序方法往往比其它简单排序方法还要慢。 基本思想: 每一趟 (例如第 i 趟, i = 0, 1, …, n-2) 在后面 n-i 个待排序对象中选出排序码最小的对象, 作为有序对象序列的第 i 个对象。待到第 n-2 趟作完, 待排序对象只剩下1个, 就不用再选了。 §9.4 选择排序 直接选择排序是一种简单的排序方法, 它的基本步骤是： 在一组对象 V[i]～V[n-1] 中选择具有最小排序码的对象； 若它不是这组对象中的第一个对象, 则将它与这组对象中的第一个对象