数据结构课件.ppt

《数据结构课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第9章排序9.1排序的基本概念9.2简单排序方法9.3先进排序方法9.4各种排序方法的综合比较9.5外排序简介9.1排序的基本概念1.排序是按关键字的非递减或非递增顺序对一组记录重新进行排列的操作。描述如下：假设含有n个记录的序列为{r1，r2，…，rn}它们的关键字相应为{k1，k2，…，kn}使其关键字满足如下非递减（或非递增）关系：也就是使记录序列重新排列成一个按关键字有序的序列2.排序的稳定性假设Ki=Kj(1≤i≤n，1≤j≤n，i≠j)，若在排序前的序列中Ri领先于Rj(即i

2、；若相同关键字的领先关系在排序过程中发生变化，称为不稳定的排序。证明一种排序方法是稳定的，要从算法本身的步骤中加以证明。证明排序方法是不稳定的，只需给出一个反例说明在排序过程中，一般进行两种基本操作：①比较两个关键字的大小；②将记录从一个位置移动到另一个位置。三种常见的存储方法：向量结构：将待排序的记录存放在一组地址连续的存储单元中。由于在这种存储方式中，记录之间的次序关系由其存储位置来决定，所以排序过程中一定要移动记录才行。链表结构：采用链表结构时，记录之间逻辑上的相邻性是靠指针来维持的，这样在排序时，就不用移动记录元素，而只需要修改指针

3、。这种排序方式被称为链表排序。记录向量与地址向量结合：将待排序记录存放在一组地址连续的存储单元中，同时另设一个指示各个记录位置的地址向量。在排序过程中不移动记录本身，而修改地址向量中的“地址”，排序结束后，再按照地址向量中的值调整记录的存储位置。这种排序方式被称为地址排序。为了讨论方便，假设待排记录的关键字均为整数，从数组下标为1的位置开始存储，下标为0的位置存储监视哨，或空闲不用。#defineMAXSIZE20/*一个用作示例的小顺序表的最大长度*/typedefintKeyType;typedefstruct{KeyTypekey

4、;OtherTypeotherdata;}RecordType;typedefstruct{RecordTyper[MAXSIZE+1];/*r[0]闲置或作为判别标志的“哨兵”单元*/intlength;/*顺序表长度*/}SqList;/*顺序表类型*/根据在排序中涉及的存储器不同，将排序方法分为两大类：（1）内部排序：整个排序过程完全在内存中进行。（2）外部排序：由于待排序记录数据量太大，在排序过程中需要对外存进行访问的排序过程。按排序算法的时间复杂度来分，可分为三类：（1）简单的排序方法，其时间复杂度为O（n2）；（2）先进的排序方

5、法，其时间复杂度为O（nlogn）；（3）基数排序，其时间复杂度为O（d*n）。9.2.1简单选择排序（selectionsort）在简单选择排序的过程中，待排记录序列的状态为：基本思想：第i趟排序操作：从无序序列R[i..n]的n-i+1记录中选出关键字最小的记录R[j]和R[i]交换，从而使有序序列区从R[1..i-1]扩大至R[1..i]，如图9.1所示。有序序列R[1…i-1]无序序列R[i..n]9.2简单排序方法常用的有简单选择排序、插入排序和起泡排序。一趟简单选择排序算法voidSelectPass(SqList*L,inti

6、){RecordTypetemp;j=i;/*j指示关键字最小记录的位置，初值设为i*/for(k=i+1;k<=L->length;k++)if(L->r[k].keyr[j].key)j=k;/*暂不进行记录交换，只记录位置*/if(i!=j){/*最后交换记录R[j]和R[i]*/temp=L->r[j];L->r[j]=L->r[i];L->r[i]=temp;}}/*SelectPass整个选择排序是一趟选择排序过程的多次重复，其算法如下：voidSelectSort(SqList*L)/*对顺序表L作简单选择排序*/{R

7、ecordTypetemp;for(i=1;ilength;++i)/*选择第i个小的记录，并交换到位*/{j=i;for(k=i+1;k<=L->length;k++)/*在L.r[i..L.length]中选择key最小的记录*/if(L->r[k].keyr[j].key)j=k;if(i!=j){temp=L->r[j];L->r[j]=L->r[i];L->.r[i]=temp;}/*与第i个记录交换*/}}/*SelectSort例如，对下列一组关键字：（491，38，65，492，76，13，27，52）算法分

8、析：时间复杂度：移动次数：最小0最大3（n-1）比较次数：n-1,n-2,n-3,……,1时间复杂度为O(n2)空间复杂度为O(1)就选择排序方法本身讲，它是一种稳定的排序方法，