ds10.4陆小马功钟浩.pptVIP

* 10.4 选择排序 简单选择排序和堆排序 10.4 选择排序 1. 简单选择排序 2. 堆排序 1. 简单选择排序 思路：每趟排序在待排记录中选出一个最小（或最大）的，交换到恰当的位置。 80 49 36 14 58 61 52 80 49 36 14 58 61 52 80 49 36 14 58 61 52 80 49 36 14 58 61 52 80 49 36 14 58 61 52 80 49 36 14 58 61 52 80 49 36 14 58 61 52 1. 简单选择排序：算法 /// 选择排序 template typename T void SelectionSort(T a[], int n) { for (int i = 0; i n - 1; i++) { // 从 a[i..n-1] 中选出最小的 a[k] int k = i; int j = i + 1; for (; j n; j++) if (a[j] a[k]) k = j; // a[k] 与 a[i] 交换 if (j != k) swap(a[k], a[i]); } } 1. 简单选择排序：性能分析 简单选择排序是不稳定的排序方法 (101, 102, 9) → (9, 102, 101) 1. 简单选择排序：性能分析 最好情况：待排记录顺序有序 比较：n(n-1)/2 移动：0 最坏情况：需要 n-1 次交换 比较：n(n-1)/2 移动：3(n-1) 平均情况：O(n2) 比较次数总是 n(n-1)/2 能否用较少的比较选出最小(或最大)元素呢？ 堆排序... 2. 堆排序 思路：利用堆的特点，在 O(log n) 时间内求出最大值，实现排序。 堆的定义： 序列{K1,K2, ..., Kn}满足Ki≤K2i，Ki≤K2i+1，称为小顶堆；若满足Ki≥K2i，Ki≥K2i+1，称为大顶堆，其中i=1, 2, ..., n/2。 特点：小顶堆的堆顶(第一个元素)为最小元素，大顶堆的堆顶为最大元素。 Ki K2i K2i+1 2. 堆排序：堆 判断序列(12,36,24,85,47,30,53,91)是否构成堆。 用Ki作为编号为 i 的结点，画一棵完全二叉树。 12 36 24 85 47 30 53 91 Ki K2i K2i+1 小顶堆 2. 堆排序：建立堆 方法：小堆变大堆 例：把(24,85,47,53,30,91,12,36)调整成小顶堆。 24 85 47 53 30 91 12 36 24 85 47 53 30 91 12 36 24 85 47 36 30 91 12 53 24 85 12 36 30 91 47 53 24 30 12 36 85 91 47 53 12 30 24 36 85 91 47 53 2. 堆排序 堆排序： (1) 将待排序列建立大顶堆 (2) 堆顶元素与堆中最后一个元素交换 (3) 除去堆中最后一个元素，将剩余元素调整成大顶堆 (4) 重复步骤 (2)--(3) n-1 次，完成排序 12 24 30 36 47 53 85 91 24 12 30 36 47 53 85 91 36 30 24 12 47 53 85 91 30 12 24 36 47 53 85 91 85 53 47 36 30 24 12 91 前面元素调整成大顶堆 53 36 47 12 30 24 85 91 47 36 24 12 30 53 85 91 91 85 47 53 30 24 12 36 24 85 47 53 30 91 12 36 建大顶堆 36 85 47 53 30 24 12 91 交换堆顶和堆中最后一个元素 对序列 (24,85,47,53,30,91,12,36) 进行堆排序的过程（堆视角） *