数据结构(第10章排序)讲解.ppt

第10章 内部排序 第10章 内部排序 10.2 插入排序 直接插入排序 直接插入排序 直接插入排序 直接插入排序 直接插入排序 10.2 插入排序 折半插入排序 10.2 插入排序 希尔排序 希尔排序 希尔排序 10.2 插入排序练习 分别用直接插入排序和希尔排序法对下列关键字进行排序，写出每趟排序结果，其中希尔排序的增量为（3,1） {21，25，49，25，16，08} 10.3 快速排序 起泡排序 10.3 快速排序 快速排序 快速排序 快速排序 快速排序 快速排序 10.4 选择排序 简单选择排序 简单选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 树形选择排序 10.4 选择排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 堆排序 10.5 归并排序 10.5 归并排序 10.5 归并排序 10.6 基数排序 10.6 基数排序 10.6 基数排序 10.6 基数排序 10.6 基数排序 10.6 基数排序 10.6 基数排序 10.7各种内部排序方法的比较讨论 10.7各种内部排序方法的比较讨论 本章学习要点 本章练习 本章练习 本章练习 二、树形选择排序 若待排记录序列的长度为n，则树形选择排序也需进行n-1趟。与简单选择排序类似，第1趟选取最小的记录，第2趟选取次小的记录，…，下面结合例子（P280）来介绍。 例一、用树形选择排序法对下面的序列排序。 （49，38，65，97，76，13，27，49） 首先进行第1趟，即选取最小的记录。为此，把待排序记录都作为最下层的叶子结点，并将叶子结点两两比较，直到求出最小值,并输出最小值(13)。 13 49 27 13 76 97 65 38 49 38 38 65 13 27 13 二、树形选择排序 若待排记录序列的长度为n，则树形选择排序也需进行n-1趟。与简单选择排序类似，第1趟选取最小的记录，第2趟选取次小的记录，…，下面结合例子（P280）来介绍。 例一、用树形选择排序法对下面的序列排序。 （49，38，65，97，76，13，27，49） 然后进行第2趟，即选取次小的记录。为此，只需把最小值叶子结点(13)用∞代替，重新进行比较，而且只需调整祖先结点，其他 结点保持不变。 27 49 27 ∞ 76 97 65 38 49 38 38 65 27 27 76 二、树形选择排序 若待排记录序列的长度为n，则树形选择排序也需进行n-1趟。与简单选择排序类似，第1趟选取最小的记录，第2趟选取次小的记录，…，下面结合例子（P280）来介绍。 例一、用树形选择排序法对下面的序列排序。 （49，38，65，97，76，13，27，49） 接下来进行第3趟，即选取第3小的记录。为此，只需把次小叶子结点(27)用∞代替，重新进行比较，且只需调整祖先结点，其他 结点保持不变。 经过n-1趟后，就得到了有序的序列。 38 49 ∞ ∞ 76 97 65 38 49 38 38 65 49 49 76 下面对树形选择排序的性能进行分析。 由例子可以看出，除了第1趟求最小记录外，其它各趟只需比较3次，即树的高度-1次。 由于具有n个叶子结点的完全二叉树的高度为 ┌log2n┐+1，所以除第1趟外，其它各趟仅需比较┌log2n┐次，因此，树形选择排序的时间复杂度为O(n log2n)。 由此可见，树形选择排序在进行第i趟时，由于充分利用了其它趟的比较结果，使得效率得以提高。但是它也有缺点，需要较多的辅助空间来保存中间结果。 于是，人们又提出了改进方案即堆排序，堆排序的时间复杂度依然为 O(n log2n)，但只需一个记录大小的辅助空间。 三、堆排序 则称之为堆。进一步地，前一种称为小顶堆，后一种称为大顶堆。 为了介绍堆排序，先来复习一下完全二叉树的知识。 或者 一个序列（k1，k2，…， kn），如果满足： 一棵有 n个结点的二叉树，如果它与同深度的满二叉树的前 n个结点一一对应，则该二叉树被称为完全二叉树。 完全二叉树非常适于用顺序存储表示，方法是按照层序依次将结点存放在数组中。这样一来，每个完全二叉树对应一个序列。 另外，有n个叶子结点的完全二叉树的高度为┌log2n┐+1。 小顶堆：(12，36，24，85，47，30，53，91) 大顶堆：(96，83，27，38，11，9)