数据结构-快速和堆排序.ppt

简单选择排序-例子 13 65 97 76 97 65 1 2 3 4 5 6 7 第五趟： i=5 27 38 38 49 76 65 13 65 97 76 97 76 1 2 3 4 5 6 7 第六趟： i=6 27 38 38 49 76 65 97 13 65 97 76 97 97 1 2 3 4 5 6 7 排序结果： 27 38 38 49 76 65 97 i i 简单选择排序-算法 void SelectSort (Elem R[], int n ) { // 对记录序列R[1..n]作简单选择排序。 for (i=1; in; ++i) {//排序的趟数 } } // SelectSort k= SelectMinKey(R, i); // 在 R[i..n] 中选择关键字最小的记录 if (i!=k) R[i]←→R[k]; // 与第 i 个记录交换 简单选择排序-性能分析 1.对n个记录进行简单选择排序，所需进行的关键字间的比较次数总计为： 2.移动记录的次数，当待排序列为正序数为最小，最小值为 0。 3.简单选择排序是一种不稳定的排序方法 ??? 待排序列为逆序数为最大，最大值为3(n-1) 。 简单选择排序-讨论 例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。 原始序列： 21，25，49，25*，16，08 第1趟 第2趟 第3趟 第4趟 第5趟 08，25，49，25*，16，21 08，16, 49，25*，25，21 08，16, 21，25*，25，49 08，16, 21，25*，25，49 08，16, 21，25*，25，49 最小值 08 与r[1]交换位置 交换，不稳定的 简单选择排序-讨论 例：关键字序列T= （21，25，49，25*，16，08），请给出简单选择排序的具体实现过程。 原始序列： 21，25，49，25*，16，08 第1趟 第2趟 第3趟 第4趟 第5趟 08，21，25，49，25*，16 08，16, 21，25，49， 25* 08，16, 21，25, 49, 25* 08，16, 21，25， 49, 25* 08，16, 21，25, 25*，49 移动，稳定的 堆的定义 （13，38，27，50，76，65，49，97） 13 38 27 50 76 65 49 97 （96，83，27，38，11，9） 小顶堆 96 83 27 38 11 9 大顶堆 堆的定义 堆是满足下列性质的数列{r1, r2, …，rn}： 或 (小顶堆) (大顶堆) 若将此序列所存储的一维数组R[1..n]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树： 树中任一非叶结点的关键字均不大于(或不小于)其左右孩子(若存在)结点的关键字。 堆的定义 小顶堆：??? 　根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最小者的堆称为小顶堆。 大顶堆：??? 　根结点(亦称为堆顶)的关键字是堆里所有结点关键字中最大者，称为大顶堆。 注意：??? 　①堆中任一子树亦是堆。???　 ②以上讨论的堆实际上是二叉堆(Binary Heap)，类似地可定义k叉堆。 堆排序 可将堆序列看成完全二叉树，则堆顶元素（完全二叉树的根）必为序列中n个元素的最小值或最大值 堆排序过程—以大顶堆为例 1）将无序序列建成一个堆，得到关键字最大的记录； 2）输出堆顶的最大值后，使剩余的n-1个元素重又建成一个堆，则可得到n个元素的次最大值 3）重复执行，得到一个有序序列，这个过程叫堆排序 堆排序 堆排序需解决的两个问题： 1.如何由一个无序序列建成一个堆？ 2.如何在输出堆顶元素之后，调整剩余元素，使之成为一个新的堆？ 堆排序—筛选 第二个问题解决方法——筛选 方法： 1.输出堆顶元素之后，以堆中最后一个元素替代之； 2.然后将根结点值与左、右子树的根结点值进行比较，并与其中大者进行交换； 3.重复上述操作，直至叶子结点，将得到新的堆，称这个从堆顶至叶子的调整过程为“筛选” 13 97 76