VC编程教程 第9章 排序

《VC编程教程 第9章 排序》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第九章排序[本章学习要求]掌握：排序的基本概念和相关术语。掌握：插入排序的基本思想，直接插入排序算法、折半插入排序算法以及希尔排序算法的实现过程和实现算法。并了解插入排序算法的时间效率和空间效率。掌握：交换排序的基本思想，冒泡排序算法、快速排序算法的实现过程和实现算法。并了解冒泡排序和快速排序的算法评价。掌握：选择排序的基本思想，简单选择排序以及堆排序的实现算法和算法评价。掌握：归并排序的基本思想和2路归并的实现算法。默认的排序数据结构：待排序的记录采用顺序存储，待排序记录的定义为：#defineMAXSIZE100/*假定顺

2、序表的最大长度为100*/typedefintKeyType；/*假定关键字类型为整数类型*/typedefstruct{KeyTypekey；/*关键字项*/OtherTypeother；/*其他项*/}DataType；/*数据元素类型*/typedefstruct{DataTyper[MAXSIZE+1]；/*r[0]闲置或充当哨兵*/intlength；/*顺序表长度*/}SqList；/*顺序表类型*/9.1基本概念排序定义——将一个数据元素（或记录）的任意序列，重新排列成一个按关键码有序的序列叫~排序分类按待排序记

3、录所在位置内部排序：待排序记录存放在内存外部排序：排序过程中需对外存进行访问的排序排序的稳定性若相同关键码元素间的位置关系，排序前与排序后保持一致，称此排序方法是稳定的，否则为不稳定的排序基本操作比较两个关键字大小将记录从一个位置移动到另一个位置排序方法：内排序(本章讨论的方法):待排序的记录在排序过程中全部存放在内存插入排序：直接插入排序、折半插入排序、表插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：简单选择排序、树形选择排序、堆排序归并排序：2-路归并排序基数排序：多关键码排序、链式基数排序外排序：排序过程中需要

4、使用外存。多路平衡归并按排序所需工作量简单的排序方法：T(n)=O(n²)先进的排序方法：T(n)=O(logn)基数排序：T(n)=O(d.n)评价排序算法好坏的标准主要有两条∶第一是执行算法所需的时间；第二是执行算法所需要的附加空间；另外算法本身的复杂程度也是考虑的一个因素。由于排序是经常使用的一种运算，因此，排序的时间开销是算法好坏的最重要的标志。而排序的时间开销又可以用算法执行中的比较和移动次数来衡量。同时排序的稳定性有时也要考虑。9.2插入排序9.2.1直接插入排序假设待排序的n个记录{R0,R1,…,Rn-1}存放

5、在数组中，直接插入法在插入记录Ri(i=1,2…n-1)时，记录集合被划分为两个区间[R0，Ri-1]和[Ri，Rn-1]，其中，前一个子区间已经排好序，后一个子区间是当前未排序的部分，将排序码Ki与Ki-1，Ki-2，…，K0依次比较，找出应该插入的位置，将记录Ri插入，原位置的记录向后顺移。直接插入排序采用顺序存储结构。基本思想：每次将一个待排序的记录，按其关键码大小插入到前面已经排好序的子序列的适当位置，直到全部记录插入完成。例49386597761327i=238(3849)6597761327i=365(384965

6、)97761327i=497(38496597)761327i=576(3849657697)1327i=613(133849657697)27i=1()i=7(133849657697)2727jjjjjj977665493827(13273849657697)排序结果：算法描述for(i=2;i<=n;i++){设置监视哨；寻找插入位置；移动元素；插入；}可以边寻找插入位置边移动元素。算法评价时间复杂度最好情况：若待排序记录按关键字从小到大排列(正序)关键字比较次数：记录移动次数：最坏情况：若待排序记录按关键字从大到小排列

7、(逆序)关键字比较次数：记录移动次数：若待排序记录是随机的，取平均值关键字比较次数：记录移动次数：T(n)=O(n²)空间复杂度：S(n)=O(1)直接插入排序是稳定的排序算法9.2.2折半插入排序排序过程：用折半查找方法确定插入位置的排序叫~例i=1(30)1370853942620i=213(1330)70853942620i=76(6133039427085)20…...i=820(6133039427085)20lhmi=820(6133039427085)20lhmi=820(6133039427085)20ljmh

8、i=820(6133039427085)20lhi=820(613203039427085)for(i=2;i<=n;i++){设置监视哨；寻找插入位置；移动元素；插入；}voidBinaryInsertSort(SqList*s){/*对顺序表S作折半插入排序*/intlo