本章说明101概述102插入排序103快速排序104堆排序

本章说明101概述102插入排序103快速排序104堆排序内容摘要：

上 将 R[high].key 和 枢轴的关键字进行比较，要求 R[high].key ≥ 枢轴的关键字 将 R[low].key 和 枢轴的关键字进行比较，要求 R[low].key ≤ 枢轴的关键字 high 23 low 80 high 14 low 52 例如 R[0] 52 low hig high high low 第十章 内部排序 快速 排序 可见，经过“ 一次划分 ” ，将关键字序列 52, 49, 80, 36, 14, 58, 61, 97, 23, 75 调整为 : 23, 49, 14, 36, (52) 58, 61, 97, 80, 75 在调整过程中，设立了两个指针 : low 和high，它们的初值分别为 : s 和 t, 之后逐渐减小 high，增加 low，并保证 R[high].key≥52，和 R[low].key≤52,否则进行记录的 “ 交换 ”。 第十章 内部排序 快速 排序 int Partition (RedTypeamp。 R[], int low, int high) { pivotkey = R[low].key。 while (lowhigh) { while (lowhigh amp。 amp。 R[high].key=pivotkey) high。 R[low]←→R[high]。 while (lowhigh amp。 amp。 R[low].key=pivotkey) ++low。 R[low]←→R[high]。 } return low。 // 返回枢轴所在位置 } // Partition 第十章 内部排序 快速 排序 int Partition (RedType R[], int low, int high) { }// Partition R[0] = R[low]。 pivotkey = R[low].key。 // 枢轴 while (lowhigh) { } while(lowhighamp。 amp。 R[high].key=pivotkey) high。 // 从右向左搜索 R[low] = R[high]。 while (lowhigh amp。 amp。 R[low].key=pivotkey) ++ low。 // 从左向右搜索 R[high] = R[low]。 R[low] = R[0]。 return low。 第十章 内部排序 快速 排序 三、快速排序 首先对无序的记录序列进行 “ 一次划分 ”，之后 分别 对分割所得两个子序列 “ 递归 ”进行快速排序。 无 序 的 记 录 序 列 无序记录子序列 (1) 无序子序列 (2) 枢轴 一次划分 分别进行快速排序 第十章 内部排序 快速 排序 void QSort (RedTypeamp。 R[], int s, int t ) { // 对记录序列 R[s..t]进行快速排序 if (s t) { // 长度大于 1 } } // QSort pivotloc = Partition(R, s, t)。 // 对 R[s..t] 进行一次划分 QSort(R, s, pivotloc1)。 // 对低子序列递归排序， pivotloc是枢轴位置 QSort(R, pivotloc+1, t)。 // 对高子序列递归排序 第十章 内部排序 快速 排序 void QuickSort( SqList amp。 L) { // 对顺序表进行快速排序 QSort(, 1, )。 } // QuickSort 第一次调用函数 Qsort 时，待排序记录序列的上、下界分别为 1 和。 第十章 内部排序 快速 排序 四、快速排序的时间分析 假设 一次划分所得枢轴位置 i=k，则对 n 个记录进行快排所需时间 其中 Tpass(n)为对 n 个记录进行一次划分所需时间， 若待排序列中记录的关键字是随机分布的，则 k 取 1 至 n 中任意一值的可能性相同。 T(n) = Tpass(n) + T(k1) + T(nk) 第十章 内部排序 快速 排序  nka v ga v ga v g knTkTnCnnT1)()1(1)(设 Tavg(1)≤ b 则可得结果 : )1l n ()1)(22()(  nncbnT a v g结论 : 快速排序的时间复杂度为 O(nlogn) 由此可得快速排序所需时间的平均值为： 第十章 内部排序 快速 排序 若待排记录的初始状态为按关键字有序时，快速排序将蜕化为起泡排序 ，其时间复杂度为 O(n2)。 为避免出现这种情况， 需在进行一次划分之前，进行“予处理”， 即： 先对 R(s).key, R(t).key 和 R[(s+t)/2.key，进行相互比较，然后 取 关键字为 “三者之中” 的记录 为枢轴 记录。 第十章 内部排序 堆 排序 简单选择排序 堆 排 序 目录 第十章 内部排序 堆 排序 一、简单选择排序 假设排序过程中，待排记录序列的状态为： 有序序列 R[1..i1] 无序序列 R[i..n] 第 i 趟 简单选择排序 从中选出 关键字最小的记录 有序序列 R[1..i] 无序序列 R[i+1..n] 第十章 内部排序 堆 排序 简单选择排序 的算法描述如下： void SelectSort (Elem R[], int n ) { // 对记录序列 R[1..n]作简单选择排序。 for (i=1。 in。 ++i) { // 选择第 i 小的记录，并交换到位 } } // SelectSort j = SelectMinKey(R, i)。 // 在 R[i..n] 中选择关键字最小的记录 if (i!=j) R[i]←→ R[j]。 // 与第 i 个记录交换 第十章 内部排序 堆 排序 时间性能分析 对 n 个记录进行简单选择排序，所需进行的 关键字间的比较次数 总计为 移动记录的次数 ， 最小值为 0, 最大值为 3(n1) 2)1()(11nninni第十章 内部排序 堆 排序 二、堆排序 堆是满足下列性质的数列 {r1, r2, … ， rn}： 或    12 2ii ii rr rr    12 2ii ii rr rr堆的定义 : {12, 36, 27, 65, 40, 34, 98, 81, 73, 55, 49} 例如 : 是 小顶堆 {12, 36, 27, 65, 40, 14, 98, 81, 73, 55, 49} 不是堆 (小顶堆 ) (大顶堆 ) 第十章 内部排序 堆 排序 ri r2i r2i+1 若将该数列视作完全二叉树， 则 r2i 是 ri 的左孩子。 r2i+1 是 ri 的右孩子。 12 36 27 65 49 81 73 55 40 34 98 例如 : 是堆 14不 第十章 内部排序 堆 排序 堆排序即是利用 堆的特性 对记录序列进行排序的一种排序方法。 例如： 建大顶堆 { 98, 81, 49, 73, 36, 27, 40, 55, 64, 12 } { 12, 81, 49, 73, 36, 27, 40, 55, 64, 98 } 交换 98 和 12 重新调整为大顶堆 { 81, 73, 49, 64, 36, 27, 40, 55, 12, 98 } { 40, 55, 49, 73, 12, 27, 98, 81, 64, 36 } 经过筛选 第十章 内部排序 堆 排序 void HeapSort ( HeapType amp。 H ) { // 对顺序表 H 进行堆排序。 } // HeapSort for ( i=。 i0。 i ) HeapAdjust ( , i, )。 // 建大顶堆 for ( i=。 i1。 i ) { [1]←→[i]。 // 将堆顶记录和当前未经排序子序列 // [1..i]中最后一个记录相互交换 HeapAdjust(, 1, i1)。 // 对 [1] 进行筛选 } 第十章 内部排序 堆 排序 如何“建堆”。 两个问题 : 如何“筛选”。 定义堆类型为 : typedef SqList H。