第9章 排序.pptVIP

第9章 排序 ② 快速排序递归算法需要堆栈来实现，栈中存放待排序记录序列的首尾位置，一般情况下需要栈空间 O(log2n)；在最坏的情况下，需要的栈空间为 O(n)。 * ③ 快速排序是不稳定的。快速排序不适用于记录基本有序的场合。 9.4 选择排序法 选择排序法的基本思想是：每一趟在 n-i+1 ( i = 1, 2, …, n-1 ) 个记录中选取关键字最小的记录作为有序序列中的第 i 个记录。 选择排序法包括简单选择排序和堆排序。简单选择排序 (simple selection sort) 是一种最简单且最为广大读者熟悉的选择排序法。堆排序 (heap sort) 是对树型选择排序方法的一种改进，避免了重复比较。 简单选择排序 * 堆排序 (1) 算法思想 简单选择排序的基本思想：将 n 个待排序记录存放在 L.r[1 . .n] 中，对 n 个待排序记录进行 n-1 趟扫描： * 1. 简单选择排序 ① 第 1 趟扫描选出 n 个记录中关键字值最小的记录，并与 L.r[1] 记录交换位置； ② 第 2 趟扫描选出余下的 n-1 个记录中关键字值次最小的记录，并与 L.r[2] 记录交换位置； 依此类推至第 n-1 趟扫描结束，所有记录有序。 void SelectSort ( SqList L ) // 对顺序表 L 作简单选择排序 { for ( i = 1; i L.length; ++i ) // 选择第 i 个小记录并交换到位 { k = i; for ( j = i+1; j L.length; ++j ) // 选择 key 最小的记录 if ( L.r[j].key L.r[k].key ) k = j; if ( i ! = k ) { temp = L.r[i]; L.r[i ] = L.r[k]; L.r[k] = temp; } } // for } // SelectSort (2) 算法描述 * (3) 算法分析 * ① 初始文件有序时，移动记录为 0 次； ② 初始文件逆序时，移动记录至多为 3(n-1) 次； ③ 初始文件随机时，外循环 i = 1 时，内循环要做 n-1 次比较；当外循环 i = 2 时，内循环要做 n-2 次比较；依此类推，当外循环 i = n-1 时，内循环要做 1 次比较。因此，总共比较次数为 n*(n-1)/2。简单选择排序时间复杂度为 O(n2)。 ④ 简单选择排序是不稳定的。 使用简单选择排序法，从 n 个记录中选出关键字值最小的记录需要作 n-1 次比较，然后从其余 n-1 个记录中选出次最小的记录需要作 n-2 次比较，……。显然，相邻两趟中的某些比较是重复的。为了避免重复比较，可以采用树型选择排序方法。 * 2. 堆排序 (1) 树型选择排序的基本思想 * ① 把 n 个记录的关键字两两比较，将其中关键字值较小的 n/2 个关键字取出，然后将这 n/2 个关键字进行两两比较，继续选择较小的关键字，直至选出一个最小关键字值； ② 对余下的 n-1 个记录的关键字进行第 2 趟两两比较，再选出一个次小关键字；如此反复，直至结束。 这种两两比较的过程可以用一棵有 n 个叶子结点的树来描述。上面一层分支结点两两比较得到较小的关键字。依次类推，树根表示最后选出来的最小关键字，已经选出来的关键字的叶子结点用 ∞ 表示。 (2) 堆排序 * 树型选择排序算法克服了简单选择排序中比较次数过多的缺点，可把每趟比较的结果保存下来，比较的过程就是修改从树根到刚改为 ∞ 的叶子结点这一路径上各结点的值的过程。每趟都经过 log2n 次比较就选择出一个最小关键字值，因此，总比较次数(nlog2n)。 但是这种方法的缺点是占用较多的存储空间来保存比较的结果。因此，1964 年威洛姆斯 (J.willioms) 提出对树型选择排序方法的改进方法??堆排序。堆排序只需一个记录大小的辅助空间，与树型选择排序相比，在存储空间及比较次数方面作了一些改进。 (3) 堆的定义 如果用一维数组依次存放该序列，并且把这个一维数组看成是一棵完全二叉树的顺序存储表示，则堆的含义可以这样认为：在这个二叉树中，所有的非叶子结点的关键字值 ki 均不大于（或不小于）其左右两个分支结点（即左