资源描述：
《数据结构第九章 排序.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。
1、数据结构第九章排序学校：新会电大老师：陈锡能《数据结构》目录第一章绪论第二章线性表第三章稀稀矩阵和广义表第四章栈和队列第五章树和二叉树第六章二叉树的应用第七章图第八章查找第九章排序第九章排序9.1排序的基本概念9.2选择排序9.3交换排序9.4归并排序9.5各种内排序方法的比较9.1排序的基本概念排序就是把一组记录（元素）按照某个域的值的递增（即由小到大）或递减（即由大到小）的次序重新排列的过程。排序域（排序项）：用于排序的域排序码：该域中的每一个值（它与一个记录相对应，排序码相同的记录可能有多个）输入：n个记录R1，R2，…，Rn，
2、其相应的关键字分别为K1，K2，…，Kn输出：Ril，Ri2，…，Rin，使得Ki1≤Ki2≤…≤Kin(或Ki1≥Ki2≥…≥Kin)9.1排序的基本概念稳定的排序：对于具有同一排序码的多个记录来说，若采用的排序方法使排序后记录的相对次序不变，则称此排序方法是稳定的，否则称为不稳定的排序。例子：排序码为（23,15,72,18,23,40）稳定排序结果：（15,18,23,23,40,72）不稳定排序结果：（15,18,23,23,40,72）排序稳定判定的基本原则：排序过程存在不相邻元素之间的互换，则可能改变具有相同排序码元素的前
3、后位置，因此是不稳定的。排序过程只在相邻元素之间互换，则不改变具有相同排序码元素的前后位置，因此是稳定的。9.1排序的基本概念排序的分类：内排序：排序过程全部在内存中进行外排序：排序过程需要不断地进行内存和外存之间的数据交换内排序速度比外排序快，但数据量要小内排序方法种类：9.2选择排序9.2.1直接选择排序9.2.2堆排序（重点）选择排序(SelectionSort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。常用的选择排序方法有直接选择排序和堆排序。9.2.1直接
4、选择排序1、算法的基本思想：直接选择算法每次从待排序的区间中选择出具有最小排序码的元素，把该元素与该区间的第一个元素交换位置第一次（即开始）待排序区间包含所有元素R[0]~R[n-1]，经过选择和交换后，R[0]为具有最小排序码的元素；第二次排序区间为R[1]~R[n-1]，经过选择和交换后，R[1]为仅次于R[0]的具有最小排序码的元素；第三次排序区间为R[2]~R[n-1]，经过选择和交换后，R[2]为仅次于R[0]和R[1]的具有最小排序码的元素；依次类推，经过n-1次选择和交换后，R[0]~R[n-1]就成为了有序表，整个排序
5、过程结束。9.2.1直接选择排序2、算法描述（见P301～302）3、算法分析关键字比较次数无论文件初始状态如何，在第i趟排序中选出最小关键字的记录，需做n-i次比较，因此，总的比较次数为：n(n-1)/2=0(n2)记录的移动次数当初始文件为正序时，移动次数为0文件初态为反序时，每趟排序均要执行交换操作，总的移动次数取最大值3(n-1)直接选择排序的平均时间复杂度为O(n2)直接选择排序是一个就地排序，辅助空间为O(1)稳定性分析：直接选择排序是不稳定的，例子：[2，2，1]9.2.1直接选择排序4、算法演示：关键字序列(49,38
6、,65,97,76,13,27,49)1、算法的基本思想：堆排序是利用堆（采用大根堆）的特性进行排序的过程，包括初始堆（筛运算）和利用堆排序这两个阶段。小根堆：根结点(堆顶)的关键字是堆里所有结点关键字中最小者大根堆：根结点(堆顶)的关键字是堆里所有结点关键字中最大者堆中任一子树亦是堆堆排序特点堆排序(HeapSort)是一树形选择排序。堆排序的特点是：在排序过程中，将R[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系【参见二叉树的顺序存储结构】，在当前无序区中选择关键字最大(或最小)的
7、记录。9.2.2堆排序（重点）2、算法描述（见P304～306）3、算法分析堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成堆排序的最坏时间复杂度为O(nlog2n)。堆排序的平均性能较接近于最坏性能由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件堆排序是就地排序，辅助空间为O(1)稳定性分析：不稳定的排序方法9.2.2堆排序（重点）4、算法演示：关键字序列(42,13,24,91,23,16,05,88)9.2.2堆排序（重点）9.3交换排序9.3.1气泡排序9.3.2快速排序（重点）交换排序的基本
8、思想是：两两比较待排序记录的关键字，发现两个记录的次序相反时即进行交换，直到没有反序的记录为止。常用的交换排序方法有气泡排序和快速排序。1、算法的基本思想：气泡排序（又称冒泡排序）的基本思想是通过相邻元素之间的比较和交换
