数据结构讲义第10章新.ppt

第10章 排序 10.1 概述 ----1.排序的定义 10.1 概述 ----1.排序的定义 10.1 概述 ----1.排序的定义 10.1 概述 ----1.排序的定义 10.1 概述 ----1.排序的定义 10.1 概述 ----1.排序的定义 10.1 概述 ----1.排序的定义 10.2 插入排序 10.2 插入排序 ---直接插入排序 10.2 插入排序 ---直接插入排序 10.2 插入排序 10.2 插入排序 ---直接插入排序 10.2 插入排序-------希尔排序 10.2 插入排序-------希尔排序 10.2 插入排序 10.3 快速排序 10.3快速排序------冒泡排序 10.3快速排序------冒泡排序 10.3快速排序------冒泡排序 10.3快速排序------冒泡排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 void SelectSort(rectype R[] ,int n) { for (i=1;i=n-1;i++) { k=i; for (j=i+1;j=n;j++) if (R[j].keyR[k].key) k=j; if (k!=i) { temp=R[i]; R[i]=R[k]; R[k]=temp; } } } 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 现在剩下两个问题： （1）如何由一个无序序列建成一个堆； （2）如何在输出堆顶元素后，调整剩余元素为一个新的堆。 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.4 选择排序 10.7 各种排序方法的比较讨论 一、选取排序方法时需要考虑的因素有： 待排序的记录数目 记录本身信息量的大小 关键字的结构及其分布情况 对排序稳定性的要求 语言工具的条件、辅助空间的大小 习题10 10.1?以关键码序列（503，087，512，061，908，170，897，275，653，426）为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态： （1）直接插入排序； （2）简单选择排序； （3）起泡排序； （4）快速排序； （5）堆排序； （6）归并排序； 10.4.3堆排序 (Heap Sort) 2 堆排序的基本思想： 问题1:当堆顶元素改变时，如何重建堆? “筛选”法调整成堆。 13 38 27 49 76 65 49 97 97 38 27 49 76 65 49 13 27 38 49 49 76 65 97 13 (a)堆 (b)13和97交换后的情形 (c)调整后的新堆 10.4.3堆排序 (Heap Sort) 2 堆排序的基本思想： 问题2:如何由一个任意序列建初堆？ 一个任意序列看成是对应的完全二叉树，由于叶结点可以视为单元素的堆，因而从最后一个非终端接点[n/2]开始以反复利用“筛选”法，直到将整个完全二叉树调整为堆。 10.4.3堆排序 (Heap Sort) 2 堆排序的基本思想： 对无序序列{49,38,65,97,76,13,27,49}建堆示例： 49 38 65 97 76 13 27 49 49 38 13 49 76 65 27 97 49 38 65 49 76 13 27 97 10.4.3堆排序 (Heap Sort) 2 堆排序的基本思想： 对无序序列{49,38,65,97,76,13,27,49}建堆示例： 49 38 13 49 76 65 27 97 13 38 27 49 76 65 49 97 10.4.3堆排序 (Heap Sort) 2 堆排序的基本思想： 问题3:如何利用堆进行排序？ 进行堆排序的步骤：①将待排序记录按照堆的定义建初堆，并输出堆顶元素；②调整剩余的记录序列，利用筛选法