数据结构第六章排序资料教学教材.ppt

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

1、数据结构第六章排序资料排序方法可以分为五种：插入排序、选择排序、交换排序、基数排序和归并排序。排序中的基本操作：比较关键码大小和移动记录。评价排序算法好坏的标准主要有两条∶①执行算法所需的时间；②执行算法所需要的附加空间。排序的时间开销可以用算法执行中的比较和移动次数来表示。10-2插入排序插入排序的基本思想：每步将一个待排序的记录按其关键字大小插入到前面已排序表中的适当位置，直到全部插入完为止。直接插入排序假设待排序的n个记录{R0,R1,…,Rn-1}存放在数组中，直接插入法是在插入记录Ri(i=1,2…n-1)时，记录集合被划分为两个区间[R0，Ri-1]和[Ri，R

2、n-1]，其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码Ki与Ki-1，Ki-2,…,K0依次比较，找出应该插入的位置，将记录Ri插入，原位置的记录向后顺移。例：设待排序记录的排序码为：49，38，65，97，76，13，27，49，请用直接插入排法排序。i=2:[49]38659776132749i=3:[3849]659776132749i=4:[384965]9776132749i=5:[38496597]76132749i=6:[3849657697]132749i=7:[133849657697]2749i=8:[1327384965769

3、7]49i=9:[1327384949657697]typedefstruct{KeyTypekey；…；}DataType;voidInsertSort(DataTypeR[],intn){intI;for(i=2;i<=n;i++)if(R[i].key

4、录的次数为0次；最大移动记录的次数为(n+4)(n-1)/2=O(n2)。平均情况下，插入记录大约同前面i/2个记录进行关键码比较和移动，因此插入排序的时间复杂度为O(n2)直接插入排序是稳定的排序算法二分法插入排序由于插入排序的基本操作是在有序表中进行查找,而查找的过程是可以用折半查找来实现的。由此实现的排序称为二分法插入排序。二分法插入排序必须采用顺序存储方式。voidB_InsertSort(DataTypeR[],intn){intI;intcow,high,mid;for(i=2;i<=n;i++){R[0]=R[i];low=1;high=i-1;while(lo

5、w<=high){mid=(low+high)/2;if(R[0].key>R[mid].key)low=mid+1;elsehigh=mid-1;}for(j=i-1;j>=high+1;j--)R[j+1]=R[j];R[high+1]=R[0];}}i=2:[49]38659776132749i=3:[3849]659776132749i=4:[384965]9776132749i=5:[38496597]76132749i=6:[3849657697]132749i=7:[133849657697]2749i=8:[13273849657697]49i=9:[1327384

6、949657697]low=1,high=1low=1,high=2low=1,high=3low=1,high=4low=1,high=5算法分析如下:定位一个关键码的位置需比较次数至多为,比较次数时间复杂度为而移动记录的次数和直接插入排序相同，因此时间复杂度仍为O(n2)二分插入排序是一个稳定的排序方法。表插入排序基本思想：在直接插入的基础上减少移动次数，主要是在记录中设置一个指针字段，记录链接成链表，初始时，链表为空，头结点指针域置为0，并在头结点数据域放比所有记录关键码都大的整数，然后，向链表中插入结点typedefstruct{DataTypedata;intn

7、ext;}NodeType;NodeTypeR[n+1];MAX49386597761327490--------0112030445262738这个有序的链表，查找则只能顺序查找，而不能随机查找若需要，要发对记录进行重排，使其在物理上有序。012345678voidB_InsertSort(NodeTypeR[],intn){inti,j,p;DataTypeS;j=R[0].next;i=1;while(i