数据结构与算法分析课件第7章.ppt

数据结构与算法分析A Practical Introduction toData Structures and Algorithm Analysis陈 星  第三部分 排序和检索 第7章 内排序 在计算机主存内对一组记录进行排序的标准算法。 先介绍三种简单但较慢（Θ(n2)）的算法. 1. 插入排序。 2. 起泡（冒泡排序）。 3. 选择排序。 再介绍几种复杂但较快的算法. 如Shell排序、快速排序、堆排序、归并排序…… 排序操作中的基本运算. 1. 比较 2. 交换 7.1 排序术语及记号 记录之间通过一个比较器类进行比较。 关键字 是数据元素中的某个数据项。每个记录中都有一个关键码域(key)。 比较器类就是对该关键码进行比较; 设对每一种记录类型都已定义Swap函数。 插入排序的代价分析 7.2.2 起泡排序 起泡排序的基本思想 对所有相邻记录的关键字值进行比效，如果是逆序（a[j]a[j+1]），则将其交换，最终达到有序化。 其处理过程为： 对待排序的记录序列从后向前（或从前向后）进行扫描。 依次比较相邻记录的关键字。 交换比较中发现的逆序。因此关键字值小的记录左移，关键字值大的记录右移。一次扫描后，最小值移动序列的顶端。 做n-1遍从后向前（或从前向后）的扫描和逆序交换，或直到未发现逆序为止。 起泡排序算法 起泡排序代价分析 7.2.3 选择排序 基本思想 ：扫描整个线性表，从中选出最小的元素，将它交换到表的最前面；然后对剩下的子表采用同样的办法，直到子表空为止 。 template class Elem, class Comp void selsort(Elem A[], int n) { for (int i=0; in-1; i++) { int lowindex = i; // Remember its index for (int j=n-1; ji; j--) // Find least if (Comp::lt(A[j], A[lowindex])) lowindex = j; // Put it in place swap(A, i, lowindex); } } 归并排序的关键技术 －将两个有序序列合并为一个有序序列 方法：顺序比较两个表中的元素，将值小者移入合并后的新表中，反复如此，直至所有元素都移入新表。 1 2 3 4 5 6 7 8 38 65 76 49 13 27 39 97 j i 分割中项T 快速排序的分割方法 将序列 38、65 、76 、 49 、13、27、39 、97用快速排序的方法进行排序。 整个表：从38，97和49中取出中项49作为分割中项T进行快速排序 1 2 3 4 5 6 7 8 38 65 76 49 13 27 39 97 1 2 3 4 5 6 7 8 38 65 76 49 13 27 39 97 j i 分割中项T＝49 快速排序的分割方法 将序列 38、65 、76 、 49 、13、27、39 、97用快速排序的方法进行排序。 将分割中项49保存在变量T中，将i所指向的记录38移到分割中项位置。 1 2 3 4 5 6 7 8 65 76 38 13 27 39 97 1 2 3 4 5 6 7 8 38 65 76 49 13 27 39 97 j i 分割中项T＝49 快速排序的分割方法 将序列 38、65 、76 、 49 、13、27、39 、97用快速排序的方法进行排序。 首先指针j指向的记录与T进行比较。97T，不交换。 1 2 3 4