资源描述：
《一种基于直接选择排序算法的改进.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、2004年12月广西师范学院学报(自然科学版)Dec.2004第21卷第4期JournalofGuangxiTeachersEducationUniversity(NaturalScienceEdition)Vol.21No.4文章编号:1002-8743(2004)04-0093-04一种基于直接选择排序算法的改进梁文忠(广西大学梧州分校梧州543002)摘要:依据直接选择排序算法的基本原理,将排序过程中的每一趟循环从只能确定一个元素经排序后的位置,改进为可以确定两个元素的位置,从而减少排序所需的循环.关键词:
2、排序;二元;策略中图分类号:TP312文献标识码:A排序是数据处理中的一种重要运算,排序的本质就是将一组数据元素的无序序列按一定规律进行排列,使其成为有序序列.一些常用的排序算法如插入排序、交换排序、选择排序等,其排序方法主要是通过关键字之间的比较和记录的移动来实现.这些排序算法的一个共同之处,在于若要将一组包含n个数据元素的无序序列排成有序序列,一般情况下均要经过n-1趟循环的处理,且每一趟循环的处理只能确定一个数据元素经排序后的位置.实际上,我们对排序过程中序列的交换位置并不关心,而只需要将无序序列变为有序序列.其实我们甚至也不必限制排序过
3、程中每趟循环交换元素的个数.为了讨论方便起见,本文假设待排序的一组记录存放在一组地址连续的存储单元中,并设记录关键字为整数,因而待排序记录的数据类型为:typedefstruct/*记录为一结构类型*/{intkey;/*关键字域*/elemtpotheritem;/*记录的其它域*/}recdtype;recdtypeR[];/*R为一记录类型数组*/1直接选择排序直接选择排序是内排序中的一种重要排序策略,直接选择排序的基本原理是在排序过程的每一步中,都对未排序的元素进行线性搜索,以决定剩余元素中的哪一个元
4、素要与它应占据的那个位置的元素进行交换,从而移到它在数组中的正确位置上.为了便于后面的讨论,不妨先来看看直接选择排序(有序表是从左侧构造的,即按照从小到大的顺序排列):每次从待排序的区间中选出关键字最小的记录,把它与当前区间的第一个记录交换位置.假设开始时待排序的区间为R[0]~R[n-1],经过第一次选择和交换后,R[0]中存放最小的记录;第二次待排序的区间是R[1]~R[n-1],经过选择和交换后,R[1]成为最小的记录;依此类推,经过n-1次选择和交换后,R[0...(n-1)]成为有序表,即可实现排序.(在此略去直接选择排序的排序算法).用
5、直接选择排序对有n条记录的数据进行排序时,因每趟循环之后只能确定1个数据排序后的定收稿日期:2004-08-09作者简介:梁文忠(1963-),男,广西贺州人,高级讲师,从事计算机程序设计和数据结构的教学及研究.94广西师范学院学报(自然科学版)第21卷位,通常都需要n-1趟的循环来对数据进行选择和交换处理.2改进设想本文对直接选择排序的一种改进设想,主要是将排序过程中的每一趟循环从只能确定一个元素经排序后的位置,改进为可以确定两个元素的位置,从而减少排序所需的循环.为了便于讨论,在此暂且称之为二元选
6、择排序算法.2.1二元选择排序的基本原理每次从待排序的区间中选出关键字最小与最大的记录,把它们分别与当前区间的首尾两个记录交换位置.假设开始时待排序的区间为R[0]~R[n-1],经过第一次选择和交换后,R[0]中存放最小的记录,R[n-1]中存放最大记录;第二次待排序的区间是R[1]~R[n-2],经过选择和交换后,R[1]成为最小的记录,R[n-2]成为最大记录;依此类推,经过不超过(n-1)/2次选择和交换后,R[0...(n-1)]成为有序表,即可实现排序.2.2二元选择排序算法的排序过程例1假定n=7,文件中各个记录的关键字
7、为(48,36,65,97,15,27,48),以下是每趟选择和交换后的记录排列情况,其中方括号内表示待排序区间,方括号外表示已排序区间.初始关键字[48366597152748]第一趟排序后15[3665484827]97第二趟排序后1527[364848]6597第三趟排序后152736[48]4865最后排序结果152736484865977个数据总共经过3趟循环构成了一个有序表;例2假定n=8,文件中各个记录的关键字为(48,36,65,97,15,27、52、88),以下是每趟选择和交
8、换后的记录排列情况,其中方括号内表示待排序区间,方括号外表示已排序区间.初始关键字[4836659
