数据结构chapter 9 排序

《数据结构chapter 9 排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第十章排序将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列；排序的根本目的是提高查找的速度21-Jul-212有序表和无序表队查找性能在研究查找算法时我们发现：对于顺序表，如果表中的元素没有顺序，那么平均查找长度为表长度的一半；而当表中的元素有顺序时，可以采用效率很高的折半查找方法，大大提高查找效率。构造二叉排序树或二叉平衡树的过实质上就是一个排序过程21-Jul-213排序的定义假设含有n个记录的序列为{R1,R2,…,Rn}各个纪录对应的关键字为{K1,K2,…,Kn}排序就是要需要确定{1,2,…,n}的一种排列{P1,P2,..,Pn}它使得其相应的

2、关键字满足下列非递减（或是非递增）的关系:21-Jul-214从而使下面的序列成为一个关键字有序的序列：在排序过程中，如果关键字Ki是记录Ri的主关键字，则任何一个记录的无序序列经过排序后得到的结果是唯一的。如果关键字Ki是记录Ri的次关键字，则排序结果很可能不是唯一的。排序结果21-Jul-215排序方法的稳定性假定排序前序列中有两个记录Ri与Rj，（i≠j），排序前Ri在Rj的前面，且它们的关键字相同，即Ki=Kj.如果排序后Ri仍然在Rj的前面，那么称所使用的排序方法是稳定的；反之则称所用的排序方法是不稳定的。21-Jul-216内部排序与外部排序按待排序记录所在位置（排

3、序过程中涉及的存储器不同）可以将排序方法分为内部排序和外部排序内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序21-Jul-217内部排序策略根据策略不同，内排序可分为：插入排序：直接插入排序、折半插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、堆排序归并排序：2-路归并排序按照排序算法的时间复杂度可以分为简单排序，时间复杂度为O(n2)先进排序，时间复杂度为O(nlogn)基数排序，时间复杂度为O(d·n)每一种不同的方法各有自己的优缺点和不同的应用范围和适用环境21-Jul-218排序的两项基本操作通常情况下排序过程中需要进行两

4、项基本操作（1）比较关键字的大小（2）将记录从一个位置移动到另一个位置。第一种操作通常是必须的，第二种操作通常可以通过改变数据元素的存储结构来避免移动元素。21-Jul-219待排序记录的三种不同的存储方式将待排序的记录保存在一组地址连续的存储单元上。在排序过程中需要移动元素将待排序的记录保存在静态链表中。排序过程中不需移动元素，只需要修改指针。将待排序的元素放置在一组地址连续的存储单元上，同时另外设置一个指示各个记录位置的地址向量，排序结束后再根据地址向量调整元素的位置。这种方法可以减少第一种存储结构所需要移动记录的次数。21-Jul-2110本章约定的待排序元素的存储方式本

5、章假设待排序的数据元素保存在一个地址空间连续的存储单元中。C语言描述如下：#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;InfoTypeotherinfo;}RedType;typedefstruct{RedTyper[MAXSIZE+1];//空余一个单元intlength;}SqList;21-Jul-2111常见的排序方法：插入排序基本思想：先将记录插入到一个已经排好序的有序表中，从而得到一个新的排好序的、记录数增加1的有序表初始的时候可以将序列中第1个记录看成是一个有序子序列，然后从第2个记录开始，

6、每次将一个待排序记录，按其关键字的大小插入到前面已经排好序的文件的适当位置，直至全部记录插完为止。21-Jul-21121、直接插入排序直接插入排序是最简单的排序方法在已排好序的序列中进行查找(顺序查找)确定所应插入的位置，然后进行插入。程序设计中的小技巧：在R[0]位置上的保存待插记录的副本，称为“监视哨”监视哨的作用：自动控制循环的结束直接插入排序过程中有两个基本操作：比较关键字移动记录21-Jul-211349386597已有序列765趟插入493865976趟插入137649386597例：设输入记录的关键字序列为49，38，65，97，76，13，27，49，其直接插

7、入排序过程（关键字非递减的有序序列）：直接插入排序过程示例21-Jul-2114对顺序表L作直接插入排序算法voidInsertSort(SqList&L){for(i=2;i<=L.length;i++){ifLT(L.r[i].key,L.r[i-1].key){L.r[0]=L.r[i];for(j=i-1;LT(L.r[0],L.r[j]);j--)L.r[j+1]=L.r[j];L.r[j+1]=L.r[0];}}}121527208102012152727810201215272