第十章内部排序(白底黑字)

《第十章内部排序(白底黑字)》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十章内部排序10.1概述1、排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫~2、排序分类按待排序记录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序按排序依据原则插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序基数排序按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(nlogn)基数排序：T(n)=O(d.n)排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置10.1概述10.1概述3、稳性排序：

2、在待排记录序列中，任何两个关键字相同的记录，用某种排序方法排序后相对位置不变，则称这种排序方法是稳定的，否则称为不稳定的。例设49,38,65,97,76,13,27,49是待排序列排序后:13,27,38,49,49,65,76,97——稳定排序后:13,27,38,49,49,65,76,97——不稳定稳性排序的应用：例股票交易系统考虑一种股票交易(清华紫光)）1）顾客输入：股东帐号、股票代码、申购价格、数量，股票交易系统将用户申购请求插入申购队列队尾；2）股票交易系统按如下原则交易：A）申购价高者先成交B）申购价相同者按申购时间先后顺序成交10.1概述如何实现股票交易系统？申购队列

3、：用线性表表示交易前：将申购队列按申购价排序，显然为满足交易原则，要求排序方法是稳定的申购队列（09,10),(06,10.5),(033,9.8),(051,10))排序后：((06,10.5),(09,10),(051,10),(033,9.8))4、存贮方式待排序的记录序列通常有下列三种存贮方法：1）顺序表2）静态链表：在排序过程，只需修改指针，不需要移动记录；3）待排记录本身有放在连续单元中，同时另建一索引表——用于存放各记录存贮位置；排序时不移过记录本身，而移动索引表中的记录“地址”，在排序结束后再按地址调整记录的存贮位置10.1概述顺序表类型说明#defineMAXSIZE2

4、0//一个用作示例的小顺序表的最大长度typedefintKeyType;//定义关键字类型为整数类型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其它数据项}RedType;//记录类型typedefstruct{RedTyper[MAXSIZE+1];//r[0]闲置或用作哨兵单元Intlength;//顺序表长度}SqList;//顺序表类型10.2插入排序10.2.2直接插入排序基本思想:依次将待排记录插入到有序子表中，并使插入子表后仍保持有序，直到全部记录插入完毕；初始时，有序子表中只有一个元素。插入排序的关键：如何查找插

5、入位置。直接插入排序（也称为顺序插入排序）：排序过程：整个排序过程为n-1趟插入，即先将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，逐个进行插入，直至整个序列有序例：待排记录4938659776132749（49）38659776132749（3849）659776132749（384965）9776132749（38496597）76132749（3849657697）132749（133849657697）2749（13273849657697）49（1327384949657697）一趟直接插入排序10.2插入排序voidInsertSort(SqList&L){/

6、/对顺序表L作直接插入排序。For(i=2;i<=L.length;++i){ifLT(L.r[i].key,L.r[i-1].key){//若L.r[i].key

7、3456789初始时，有序子表中只有一个元素算法评价时间复杂度若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：若待排序记录按关键字从大到小排列(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)10.2插入排序直接插入排序是一个稳定的排序方法,也可以在链式存储的排序表中实现。0移动到哨兵1次，后移i-1次，插入值1次，共为1+(i-1)+1=i+