数据结构第10章内部排序

《数据结构第10章内部排序》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、三、表插入排序为了减少在排序过程中进行的““移动””记录的操作，必须改变排序过程中采用的存储结构。利用静态链表进行排序，并在排序完成之后，一次性地调整各个记录相互之间的位置，即将每个记录都调整到它们所应该在的位置上。如何在排序之后调整记录序列？算法中使用了三个指针：其中：pp指示第ii个记录的当前位置ii指示第ii个记录应在的位置qq指示第i+1i+1个记录的当前位置voidArrange(voidArrange(SLinkListTypeSLinkListType&SL){&SL){p=SL.r[0].next;p=SL

2、.r[0].next;//p指示第一个记录的当前位置for(i=1;i

3、[i].nextSL.r[i].next=p;=p;//指向被移走的记录}}p=q;p=q;//p指示尚未调整的表尾，//为找第i+1个记录作准备}}}//Arrange10.110.1概述10.210.2插入排序10.310.3快速排序10.410.4选择排序10.510.5归并排序10.610.6基数排序10.710.7各种排序方法的比较讨论10.110.110.110.1概述一、排序的定义二、排序的基本概念三、内部排序方法的分类一、排序的定义一、排序的定义什么是排序什么是排序(Sorting)(Sorting)？？�

4、简单地说，排序就是将一组杂乱无章简单地说，排序就是将一组杂乱无章的数据按一定的规律排列起来（递增的数据按一定的规律排列起来（递增或递减）。或递减）。�排序是计算机中经常遇到的操作。排序是计算机中经常遇到的操作。二、排序的基本概念�数据表数据表(DataList)(DataList)待排序的数据对象的待排序的数据对象的有限集合。有限集合。�关键字关键字(Key)(Key)作为排序依据的数据对象中作为排序依据的数据对象中的属性域。的属性域。�主关键字主关键字不同的数据对象若不同的数据对象若关键字互不关键字互不相同相同，，则这种

5、关键字称为主关键字。则这种关键字称为主关键字。�排序的确切定义排序的确切定义使一组任意排列的对使一组任意排列的对象变成一组象变成一组按关键字线性有序按关键字线性有序的对象。的对象。�排序算法的稳定性判断标准：关键字相同的数据对象在排序过程中是否保持前后次序不变。如2,2*,1，排序后若为1,2*,2则该排序方法是不稳定的。�内排序与外排序与外排序区分标准：区分标准：排序过程是否全部在内存进行。�排序的时间开销它是衡量算法好坏的最重要的标志。通常用算法执行中的数据比较次数和数据移动次数来衡量。�排序的方法有很多，但简单地判断

6、那一种算法最好，以便能够普遍选用则是困难的。�评价排序算法好坏的标准主要有两条：算法执行所需要的时间和所需要的附加空间。另外，算法本身的复杂程度也是需要考虑的一个因素。�排序算法所需要的附加空间一般都不大，矛盾并不突出。而排序是一种经常执行的一种运算，往往属于系统的核心部分，因此排序的时间开销是算法好坏的最重要的标志。三、内部排序的方法内部排序的过程是一个逐步扩大记录的有序序列长度的过程。有序序列区有序序列区无无序序序序列列区区经过一趟排序有序序列区有序序列区无无序序序序列列区区待排序记录在内存中怎样存储和处理？①顺序排序

7、——排序时直接移动记录；②链表排序——排序时只移动指针；③地址排序——排序时先移动地址，最后再移动记录。注：地址排序中可以增设一维数组来专门存放记录的地址。内部排序的算法有哪些？——按排序的规则不同，可分为5类：插入排序、交换排序、选择排序、归并排序、基数排序——按排序算法的时间复杂度不同，可分为3类：�简单的排序算法：时间效率低，O(n2)�先进的排序算法:时间效率高，O(nlog2n)�基数排序算法：时间效率高，O(d×n)d＝关键字的位数(长度)待排记录的数据类型:#defineMAXSIZE1000//待排顺序表最

8、大长度typedefintKeyType;//关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单