数据结构第九章排序

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

1、第9章排序排序是一种使用频度非常高的实用技术。它的功能是将一组数据元素的任意序列，重新排列成一个按关键字有序的序列。为了提高计算机的工作效率，人们提出了各种各样的排序方法和算法，本章介绍几种有代表性的排序算法，并分析这些算法的时间复杂度和空间复杂度。9.1排序的基本概念排序：就是将一组无序序列按记录中的关键字排成以该关键字有序的序列的过程。例如：有n个记录的序列{R1，R2，…，Rn}，其相应关键字的序列是{K1，K2，…，Kn}，相应的下标序列为1，2，…n。通过排序，要求找出当前下标序列1，2，…n的一种排列p1，p2，…pn，使得相应关键字满足

2、如下的非递减（或非递增）关系，即：Kp1≤Kp2≤…≤Kpn，这样就得到一个按关键字有序的记录序列：{Rp1，Rp2，…，Rpn}。这种操作过程称为排序。关键字Ki可以是记录Ri的主关键字，也可以是记录Ri的次主关键字。若Ki是记录Ri的主关键字，则任何一个记录的无序序列经过排序后得到的结果是唯一的；若Ki是记录Ri的次主关键字，则经过排序后得到的结果可能不唯一。这是因为在待排序的记录序列中，可能存在两个或两个以上关键字相等的记录。内部排序和外部排序：内部排序是指待排序序列完全存放在内存中所进行的排序过程，排序时不涉及数据的内、外存交换，适合记录较少

3、的序列。如果待排序序列记录数量非常多，排序过程不能一次在内存中完成，必需对外存储器进行访问，这样的排序称为外部排序。本章只涉及内部排序，不考虑外部排序。具有代表性的内部排序有：插入排序、交换排序、选择排序、归并排序和基数排序等五类。排序的稳定性和不稳定性：对需要排序的数据元素序列，将其按关键字进行排序，若相同关键字元素之间的位置关系，排序前与排序后的相对位置不发生变化，称此排序方法满足稳定性；否则称这种排序方法满足不稳定性。评价排序算法好坏的标准主要有两条：一个是算法的执行时间和所需的辅助空间，另外算法本身的复杂程度也是要考虑的一个因素。若排序算法所

4、需的辅助空间并不依赖于问题的规模n，即辅助空间为O(1)，则称之为就地排序。一般的说，非就地排序要求的辅助空间为O(n)。在本章的讨论中，为了讨论方便起见，设记录的关键字均为整数，在以后讨论的大部分算法中，待排序记录的数据类型设为：#defineMAXSIZE20typedefintKeyType;typedefstruct{KeyTypekey;//关键字域……;//其他信息域，如果有其他信息，可以继续添加}RedType;typedefstruct{RedTypeR[MAXSIZE+1];intlength;}SqList;9.2插入排序插入排序

5、的基本思想是：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的表中的适当位置，直到全部记录插入完成为止。也就是说，将待排序的表分成左右两部分，左边为有序表（有序序列），右边为无序表（无序序列）。整个排序过程就是将右边无序表中的记录逐个插入到左边的有序表中，构成新的有序序列。根据不同的插入方法，插入排序算法可以分为直接插入排序、折半插入排序和希尔排序等。9.2.1直接插入排序1.直接插入排序定义直接插入排序是所有排序方法中最简单的一种排序方法。其基本原理是顺序地从无序表中取出记录Ri(1≤i≤n)，与有序表中记录的关键字逐个进行比较，找出其

6、应该插入的位置，再将此位置及其后的所有记录依次向后顺移一个位置，将记录Ri插入其中。2.直接插入排序算法假设待排序的n个记录为{R1，R2，…，Rn}，初始有序表为[R1]，初始无序表为[R2，…，Rn]。当插入第i个记录Ri(2≤i≤n)时，有序表为[R1，…，Ri-1]，无序表为[Ri，…，Rn]。将关键字Ki依次与K1，K2，…，Ki-1进行比较，找出其应该插入的位置，将该位置及其以后的记录向后顺移，插入记录Ri，完成序列中第i个记录的插入排序。当完成序列中第n个记录Rn的插入后，整个序列排序完毕。向有序表中插入记录，主要完成如下操作：⑴搜索插

7、入位置。⑵移动插入点及其以后的记录空出插入位置。⑶插入记录。假设将n个待排序的记录顺序存放在长度为n+1的数组R中，数据元素从R[1]开始存放。R[0]作为辅助空间，用来暂时存储需要插入的记录，起监视哨的作用。直接插入排序算法如下:voidInsert_Sort(SqListL)/*对顺序表L作直接插入排序*/{inti,j;for(i=2;i<=L.length;i++){//i表示待插入元素的下标L.R[0]=L.R[i];//设置监视哨保存待插入元素，腾出R[i]空间j=i-1;//j指示当前空位置的前一个元素while(L.R[0].key<

8、L.R[j].key){//搜索插入位置并后移腾出空间L.R[j+1]=L.R[j];j--;}L.R[j+