内部算法性能分析 第5章 排序算法的改进
h=high; //大于区间内最后一个元素的值数组边界下标 for(i=low+1;i { t=r[i];r[i]=r[l+1];r[l++]=t; //小于区间内第一个元素的值入置low区间内 } else if(r[i]>r[high]) { t=r[i];r[i]=r[high-1];r[high--]=t; / /大于区间内最后一个元素的值放置H区内 i--;n--; //下一个比较位置不变，循环次数减一 } t=r[L];r[L]=r[low]; r[low]=t; //将小于区间内第一个元素的边界下标元素与第一个元素互换 t=r[H];r[H]=r[high]; r[high]=t; //将大于区间内最后一个元素边界下标元素与最后一个元素互换 QSort (L ,low,L-1) ; //对分解后的第一部分递归快速排序 QSort (L ,L + 1 ,H - 1) ; // 对分解后的第二部分递归快速排序 QSort (L ,H + 1 ,high) ; // 对分解后的第三部分递归快速排序 以上分析可知 Low和 High分别指向区间的第一个元素和最后一个元素 ,并保证 L [Low] < L [ High ] ,L和 H两个折针所指向的元素分别是第一个和第二个枢轴元素 ,同样保证 L [L ] < L [ H] ,经过一趟排序后 ,即确定了两个枢轴元素的位置 ,然后对三个子序列分别进行递归分解 ,每分解一次就确定两个元素的位置 ,直到整个序列有序为止 算法分析：双倍快速排序算法在经过一趟快速排序后可以同时确地两个元素的位置 ,而快速排序算法经过一趟快速排序后只能确定一个元素的位置 ,前者将带排序列分解成三个待排序列 ,而后者仅仅分解成两个序列 ,所以就这一点上来看 ,对同数量级的序列 ,双倍快速排序在时间性能上要优于快速排序 ,空间性能上 ,两者上相同的 ,只有一个辅助空间。双倍快速排序是一个快速原地置换排序也是一个稳定排序法。 5.3选择排序的算法 该算法在一定程度上克服了传统排序算法交换次数过多的缺陷, 但其效率仍较为低下, 能否在进行第 i 趟排序时, 在第 i～n 个项目中既选择一个关键字最大的项目, 又选择一个关键字最小的项目, 然后将其交换至它们应在的位置以进一步提高效率呢? 22 内部算法性能分析 第5章 排序算法的改进 易知, 若需对第 1～n 个项目组成的序列采用改进后的选择法进行排序, 无需进行( n- 1) 趟排序, 最多只需进行[ n/ 2] 趟排序( 符号[ n/ 2] 指不大于( n/ 2) 的最大整数, 下同) . 第 i 趟排序前, 关键字最大的( i-1)个项目及最小的( i- 1) 个项目已被交换至它们应在的位置, 故第 i 趟排序仅需对剩下的第 i～( n- i+ 1)个项目进行. 在第 i 个项目的关键字与其后的第( i+ 1) ～n 个项目的关键字都比较完后, 选择第 i～n 个项目中关键字最“大”项目交换至第 i 个项目的位置, 并选择关键字第 i“小”的元素交换至第( n- i+ 1) 个项目的位置. 所以改进后的选择法排序的关键在于在进行第 i 趟排序时, 在第 i～( n- i+ 1) 项目中找出关键字最“大”的项目的下标序号( 即位置) 及关键字最“小”的项目的下标序号, 然后将关键字最“大”的项目及关键字最“小”的项目进行合理高效的移动。 在进行第 i 趟排序时, 容易做到在 i～( n- i+ 1) 项目中既找出关键字最“大”的项目的下标序号 max -col, 又找出关键字最“小”的项目的下标序号 mincol, 但在进行将关键字最“大”的项目移至第 i 个项目的位置及将关键字最“小”的项目移至第( n+ 1- i) 个项目的位置的过程时却须仔细斟酌, 尤其要注意移动项目的顺序及项目移动过程中其下标序号( 即位置) 的动态变化, 否则极易出现错误. 下面让我们来深入分析,确定项 目移动过程的顺序: ( 1) 当剩余的未排序项目即第 i~( n- i+ 1) 项目中关键字最“大”的项目不是第i 个项目, 即其下标序号 max co l≠i 时, 首先应将第 i 个项目与第 max co l 个项目相交换, 然后:若第 i~(n- i+ 1) 项目中关键字最“小”者即是原来第 i 个项目, 即 m inco l= i 时, 因原来第个项目已交换至第 max col个项目, 故应将第 max co l 个项目与第( n- i+ 1) 个项目相交换;若第 i~( n- i+ 1) 项目中关键字最“小”者不是原来第 i 个项目, 即 mincol≠i 时, 应将第 mincol 个项目与第( n- i+ 1) 个项目相交换; ( 2) 当剩余的未排序项目即第i～( n- i+ 1) 项目中关键字最“大”的项目即是第 i 个项目, 即其下标序号 maxcol= i 时,故无需将第 i 个项目与第max co l 个项目相交换, 此时若第 i～( n- i+ 1) 项目中关键字最“小”者不是原来第( n+ 1- i) 个项目, 即 mincol≠n+ 1- i 时, 应将第 mincol 个项目与第( n- i+ 1) 个项目相交换, 这样进行项目的移动才可避免发生错误如上所述对传统的选择排序算法进行改进, 可使其效率得到一定程度的提高, 根据其特点姑且将其命名为双向选择排序算法. 当然若某一趟排序过程中项目间未进行交换操作, 则意味着所有 n 个项目已排好序, 无需再进行下一趟排序。 算法如下： for ( i= 1; i< = n/ 2; i+ + ) times = 0; max = array[i] ; m axco l= imin= array [i] ; mincol= i; fo r ( j= i+ 1; j< = n- i+ 1; j+ + ) 23 内部算法性能分析 第5章 排序算法的改进 { if ( array[j] > max) { max = array[ j] ; maxcol=i; times+ + } if ( array [j] < min) { min= array [j] ;mincol=j;times + + ; } } if ( maxcol!=i) { temp= array[maxcol] ; array[ max col] = array [i] ; arra y[i] = temp; if ( mincol= = i) { temp= array[ max col] ; array[ m ax co l] = array[ n- i+ 1] ; array[ n- i+ 1] = temp; else { temp=array[mincol]; array[mincol]=array[n-i+1]; array[n-i+1]=temp; } } else {if(mincol!=n+1-i) { temp=array[mincol]; array[mincol]=array[n+1-i]; array[n+1-i]=temp; } } 注: 为与上面的分析相对应, 该参考程序中数组元素的下标由 1 开始, 但 C 语言中数组的下标由 0 开始, 参考程序中并未使用数组元素 array ( 0) . 若不想浪费任何一个存贮空间, 可定义数组 array , 使其下标变化范围为由 0～( n- 1) , 将原数组第 1～n 个元素依次移至第 0～( n- 1) 个元素位置, 编程时再做必要的调整即可 5.4 堆排序的改进算法 从堆的特性可以看出， 在 k1 ， k2 ， ?，kn 是基本有序时， 尾结点在 24 内部算法性能分析 第5章 排序算法的改进 从堆底逆序上升至堆顶后往往又被筛回到底层附近，而每下筛一层需进行2 次键比较，这使得重新建堆的算法往往运行在最坏情况下。为了减少重新建堆过程中的键比较次数，设计先从根开始， 每次只通过一次键比较使最大的子结点上升一层，在进行至第 d 次之后，通过将尾结点键值和当前结点的父结点键值作比较，决定尾结点是上升还是下筛。如果仍需下筛，则再通过d次键比较使当前结点下降 d 层，然后再判定尾结点是要上升还是下筛。这样一直做下去，可知最坏情况是降至底层后再上升 d 层，所以每次重新建堆至多作( h + [ h/ d ]+ d)次键比较。设k1，k2，?，kn存于数组k [1 ]至k [ n ]中，则改进后的算法可描述为： 建立初始堆： 从堆的特性可以看出， 在 k1 ， k2 ， ?， kn 是基本有序时， 尾结点在从堆底逆序上升至堆顶后往往又被筛回到底层附近，而每下筛一层需进行2 次键比较，这使得重新建堆的算法往往运行在最坏情况下。为了减少重新建堆过程中的键比较次数，设计先从根开始， 每次只通过一次键比较使最大的子结点上升一层，在进行至第 d 次之后，通过将尾结点键值和当前结点的父结点键值作比较，决定尾结点是上升还是下筛。如果仍需下筛，则再通过d次键比较使当前结点下降 d 层，然后再判定尾结点是要上升还是下筛。这样一直做下去，可知最坏情况是降至底层后再上升 d 层，所以每次重新建堆至多作( h + [ h/ d ]+ d)次键比较。设k1，k2，?，kn存于数组k [1 ]至k [ n ]中，则改进后的算法可描述为： 建立初始堆 buildheap () {for ( i = n/2 ; i >=1 ; i -- ) shift ( i ， n) ;} / 3 buildheap3/ shift (int i ， int n) / 3将 k[ i ]～k[ n ]整理成堆3/ { x = k [ i ] ; j = 23 i ; while ( j <= n) {if ( j < n && k [ j ]< k [ j + 1 ]) ++ j ; if ( x >= k [ j ]) break ; k [ i ]= k [ j ] ; i = j ; j = 23 i ;} k [ i ]= x ;} / 3shift3 重新建堆 rebuild (int x ;int n ;intdeep) { i = 1 ; j =23 i ; d =0 ; while ( j <= n) { d = d + 1 ; 25 内部算法性能分析 第5章 排序算法的改进 if ( j < n && k [ j ]< k [ j +1 ]) ++ j ; if ( d = deep) { d = 0 ; if ( x >= k [ j ]) break ;} k [ i ]= k [ j ] ; i = j ; j = 23 i ;} while ( i > 1 && x > k [ n/2 ]) { k [ i ]= k [ n/ 2 ] ; i = n/ 2 ;} k [ i ]= x ;} / 3rebuild3/ 在堆深 h ≤[log2 n]时(此时堆中的元素一般说来已基本有序) ，重新建堆实际上变成先通过h 次比较降至堆底，然后再适当上升将尾结点放在正确的位置。 heapsort () {buildheap ; for ( j = n ; j >= 2 ; j -- ) { x = k [ j ] ; k [ j ]= k [1 ] ; rebuild( x ， j -1 ，[ log 2 n ]) }} 算法分析堆排序算法因其比较和所需额外空间少而被广泛地采用。 最坏的情况下有 n?1t(n)???([logi?22i]?[log2i]/d?d)??2)?d(n?1)d?1dn?1?[logi?22i]?d(n?1)d?1d (nh?2h?1当d = 4时，有t ( n) = (5/4) nlog 2 n + O( n)，为了确定 d 的最佳取值， 通过对f ( d) = h + h/ d + d 求极限，可知当 d = h时f ( d)有极小值( h + 2 h) 。 又通过对 t(n)?d?1dn?1?[logi?22i]?d(n?1)求极限可知当 n?1d??[logi?22i]/n?1=(nh?2h?1?2)/n?1 ?h?1时， t ( n)最小。再先取 d?[h]，以后每次重新建堆时都使用d值， t(n)?h?1h(nh?2h?1?2)?(n?1)h?nh?2nh?n 所以可以得出结论：在最坏情况下改进算法的时间复杂度为 t(n)?nlog2n?cnlog2n,1?c?2 当n?16时，有t(n)?2nlog2n，虽然log2n不是一个常数，但相对 n 来说， 其增长非常慢。所以n?2400时，log2n?20。所以n越大改进的效果就越明显。 5.5.2插入改进算法 26