数据结构-03排序

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

1、数据结构（DataStructure）第三章排序（Sorting）天津财经大学商学院管理信息系统系第三章排序3.1排序的基本概念3.2简单排序方法3.3先进法排序方法3.4基数排序3.5各种排序方法的综合比较第三章排序待排序数据元素（记录）的存储结构：typedefintKeyType//定义关键字类型为整型typedefstruct{KeyTypekey;//关键字项InfoTypeotherinfo;//其他数据项}RcdType;//记录类型本章的排序图例只标出了记录的关键字。3.1排序的基本概念

2、3.1.1排序的定义3.1.2排序的特性—稳定性与不稳定性3.1.3排序的分类3.1.4内排序的特点3.1.5选择排序法3.1排序的基本概念3.1.1排序的定义简单定义：排序是按照关键字的非递减或非递增顺序对一组记录重新进行整队（或排列）的操作。数学定义：假设含有n个记录的序列为：{r1,r2,…,rn}(3-1)它们的关键字相应为{k1,k2,…,kn},对式(3-1)的记录序列进行排序就是要确定序号1,2,…,n的一种排列p1,p2,…,pn使其相应的关键字满足如下的非递增(减)关系：kp1≤kp2

3、≤…≤kpn(3-2)也就是使式(3-1)的记录序列重新排列成一个按关键字有序的序列{rp1≤rp2≤…≤rpn}(3-3)3.1排序的基本概念3.1.2排序的特性—稳定性与不稳定性当待排记录中的关键字ki(1,2,…,n)都不相同时，则任何一个记录的无序序列经排序后得到的结果是惟一的。简单地说，稳定性排序--数据排序过后能使值相同的数据，保持原顺序中之相对位置。反之，则称为“不稳定性排序”。若排序的序列中存在两个或两个以上关键字相等的记录时，则排序得到的记录序列的结果不惟一。假设ki=kj(1≤i≤n

4、,1≤j≤n,i≠j)，且在排序前的序列中ri领先于rj(即i

5、两类：1.内部排序（InternalSort）：在排序进行的过程中不使用计算机外部存储器的排序过程。选择排序插入排序起泡排序快速排序归并排序堆排序基数排序2.外部排序（ExternalSort）：在排序进行的过程中需要对外存进行访问的排序过程。3.1.4内排序的特点待排序记录序列的存储结构：constintMAXSIZE=20//定义最大顺序表的长度typedefstruct{RcdTyper[MAXSIZE+1];//r[0]闲置或作为“哨兵”intlength;//顺序表的真正长度}SqList;/

6、/顺序表类型内部排序的过程是一个逐步扩大记录的有序序列的过程。通常在排序的过程中，参与排序的记录序列可划分两个区域：有序序列区和无序序列区，其中有序序列区的的记录已按关键字非递减有序排列。使有序序列中记录的数目至少增加一个的操作称为一趟排序。3.1.5选择排序法思想：在排序过程序中，依次从待排序的记录序列中选择出关键字值最小的记录、关键字值次小的记录、…，并分别有序序列中的第1个位置、第二个位置、……，最后剩下一个关键字值最大的记录位于序列的最后一个位置，从而使待排序的记录序列成为按关键字值由小到大排列

7、的的有序序列。有序序列R[1..i-1]无序序列R[i..n]有序序列R[1..i-1]R[j]R[i]有序序列R[1..i]无序序列R[i+1..n]一趟排序后一趟排序开始3.1.5选择排序法一趟排序算法：voidSelectPass(SqList&L,inti){//已知L.r[1..i-1]中的记录按关键字非递减有序//本算法实现第i趟排序RcdTypeW;intj,k;j=i;//j指示无序序列中第一个记录的位置for(k=i+1;k<=L.length;k++)if(L.r[k].key

8、r[j].key)j=k;//只记录位置if(i!=j)//交换R[j]和R[i];{W=L.r[i];L.r[i]=L.r[j];L.r[j]=W;}}//SelectPass3.1.5选择排序法整个算法：voidSelectSort(SqList&L){RcdTypeW;for(i=1;i