406
max col= j; times + + ; }
佳
木
斯
大
学
学
报 (自
然
科
学
版) 2001 年
/ * 将剩余的未排序元素中最大者的下标赋于变量 ma xcol* / / * 统计每轮交换数据的次数* /
if ( array [ j] < min) { min = array [ j] ; mincol= j; times + + ; } } if ( max col! = i) { tem p= array[ max col] ; array[ max col] = array [ i] ; arra y[ i] = tem p; / * 第 i 个元素与第 m axco l 个元素相交换* / if ( minco l= = i) { / * 若剩余的未排序元素中最小者即是先前假定的原来第 i 个元* / / * 第 i 轮双向选择前剩余的未排序元素中最小者应为排序后第 i 小的元素, 故应将其值赋于第( n + 1- i) 个元素* / tem p= array[ max col] ; arra y[ m ax co l] = array[ n- i+ 1] ; arra y[ n- i+ 1] = tem p; else / * 若剩余的未排序元素中最小者不是先前假定的原来第 i 个元素* / { tem p= array[ mincol] ; arra y[ m incol ] = arra y[ n- i+ 1] ; arra y[ n - i+ 1] = tem p; } } else / * 若剩余的未排序元素中最大者即是先前假定的原来第 i 个元素, 故无需将第 i 个元素与第 max col 个元素相交换* / { if ( minco l! = n+ 1- i) { / * 若剩余的未排序元素中最小者的不是原来第( n + 1- i) 个元素* / / * 第 i 轮双向选择前剩余的未排序元素中最小者应为排序后第 i 小的元素, 故应将第 minco l 个元素与第 ( n+ 1- i) 个元素相交换* / tem p= array[ mincol] ; arra y[ m incol ] = arra y[ n + 1- i] ; arra y[ n+ 1- i] = tem p; } } printf( "经第% d 轮双向选择后: ", i) ; fo r ( j= 1; j< = n; j+ + ) { if ( j= = i) printf ( " % c%d " , 24, array [ j] ) ; / * 被选择的最“ 大” 数前面加上一个符号“ ↑” 以强调显示* / else if( j= = n+ 1- i) printf ( " %d% c " , array[ j] , 25) ; / * 被选择的最“ 小” 数后面加上一个符号“ ↓” 以强调显示* / else printf ( " %d " , array[ j] ) ; } printf( "/ n" ) ; tem pchar= get ch( ) ; if ( times= = 0) break; } printf( "/ n" ) ; if ( i> n/ 2) i- - ; / * 若需进行[ n/ 2] 轮排序, 则上面用于排序的循环结束后, i> [ n/ 2] , 须进行调整* / / * 显示每一轮排序的结果后换行* / / * 显示每一轮排序的结果后暂停, 用户按任一键后继续进行下一轮排序* / / * 若某一轮排序过程中没有进行数据交换, 则可提前结束循环* / / * 显示每一轮经双向选择排序的结果* / / * 第 i 轮双向选择前剩余的未排序元素中最小者应为排序后第 i 小的元素, 故应将其值赋于第( n+ 1- i) 个元素* / / * 将第 m incol 个元素与第( n- i+ 1) 个元素相交换* / / * 因原来第 i 个元素已交换至第 m axco l 个元素, 故应将第 max col 个元素与第( n- i+ 1) 个元素相交换* / / * 若剩余的未排序元素中最大者不是先前假定的原来第 i 个元素而是原来第 ma xcol 个元素* / / * 将剩余的未排序元素中最小者的值赋于变量 min * / / * 将剩余的未排序元素中最小者的下标赋于变量 mincol* / / * 统计每轮交换数据的次数* /
{ times = 0; max = array[ i] ; m axco l= i; min = array [ i] ; mincol= i; / * 每轮交换数据的次数初值设为 0* / / * 第 i 轮选择浮沉前, 先假定第 i 个元素为剩余的未排序元素中最大者, 相应地最大元素的下标初值置为 i* / / * 第 i 轮选择浮沉前, 先假定第 i 个元素为剩余的未排序元素中最小者, 相应地最小元素的下标初值置为 i* /
2 算法的实现
上述改进后的选择排序算法原理简单, 容易实现 , 且不存在存贮空间及运行时间方面的浪费. 笔者利 用 C 语言编程实现了该算法, 参考程序如下 :
# incl ude< s t dio. h> # incl ude< all oc. h> void m ain ( ) { / * 该程序利用改进后的选择法进行非递增排序 * / int n, i, j, t imes , t emp, m ax , mi n, max col, min col; int * array; ch ar t empchar; cl rscr( ) ; print f ( " 请输入需排序的数据个数 n : ") ; scanf ( "% d", &n) ; ar ray= ( int * ) malloc( ( n + 1) * sizeof( int ) ) ; print f ( " 请输入 % d 个数据 : ", n ) ; f or ( i= 1; i< = n; i+ + ) scanf ( "% d", array+ i) ; print f ( " 原始顺序为 : / n") ; f or ( i= 1; i< = n; i+ + ) print f ( "% d", array [ i] ) ; print f ( "/ n") ; f or ( i= 1; i< = n/ 2; i+ + ) / * 利用双向选择法排序, 最多只需进行[ n/ 2] 轮循环( 符号[ n/ 2] 指不大于( n/ 2) 的最大整数, 下同) * /
1 问题的分析
易知, 若需对第 1 ～n 个项目组成的序列采用改进后的选择法进行排序 , 无需进行 ( n- 1) 趟排序 , 最 多只需进行[ n/ 2] 趟排序 ( 符号 [ n/ 2] 指不大于 ( n/ 2) 的最大整数, 下同 ) . 第 i 趟排序前, 关键字最大的 ( i1) 个项目及最小的 ( 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 小” 的项目的下标序号 m incol, 但在进行将关键字最“ 大” 的项目移至第 i 个项目的位 col , 又找出关键字最“
第 19 卷 第 4 期 2001 年 12 月
佳 木
斯
大
学
学
报
(自
然
科
学
版)
Vol. 19 No. 4 Dec. 2001
Journal of Jiamusi Universi ty( Natural Science Edi tion)
文章编号 : 1008- 1402( 2001) 04- 0404- 04
0 问题的提出
比较交换排序算法是一种最简单的且为人们所熟知的籍助“ 交换” 进行排序的算法 . 其方法是在由第 1～ n 个项目组成的序列中, 首先将第一个项目的关键字与其后第 2 ～n 个项目的关键字进行比较 , 若发现 逆序( 即与所要求的次序不一致 ) 就交换这两个项目 , 经过一趟排序将关键字最大或最小的项目交换到第 一个项目的位置; 然后将第 2 个项目与其后第 3～n 个项目的关键字进行比较 , 凡与所要求的次序不一致, 就交换这两个项目 , 经第 2 趟排序后将关键字次大或次小的项目交换至第 2 个项目的位置; …, 将第 i 个 项目的关键字与其后的第( i+ 1) ～ n 个项目的关键字进行比较, 凡出现逆序, 就交换这两个项目 , 经第 i 趟 排序将关键字第 i 大或第 i 小的项目交换至第 i 个项目的位置 ; …… , 经过( n- 1) 趟排序, 将待排序的无序 序列按要求完成排序工作. 选择法排序算法是对比较交换排序算法的改进 , 其方法是在进行第 i 趟排序 时 , 将第 i 个项目的关键字与其后的第 ( i+ 1) ～n 个项目的关键字进行比较过程中, 不必凡出现逆序, 就交 换这两个项目 , 而是在第 i 个项目的关键字与其后的第 ( i+ 1) ～n 个项目的关键字都比较完后 , 选择第 i～ n 个项目中关键字最大或最小的项目交换并将其交换至第 i 个项目的位置. 该算法在一定程度上克服了比 较交换排序算法交换次数过多的缺陷, 但其效率仍较为低下 , 能否在进行第 i 趟排序时 , 在第 i～n 个项目 中既选择一个关键字最大的项目 , 又选择一个关键字最小的项目, 然后将其交换至它们应在的位置以进一 步提高效率呢 ?