ds10.1-3陆小马功钟浩.pptVIP

10. 排序 插入排序和快速排序 排序 1. 概述 2. 插入排序 3. 快速排序 4. 选择排序 5. 归并排序 6. 基数排序 7. 总结 1. 概述 排序：将一个数据元素的序列重新排列成一个按关键字有序的序列。 排序方法的稳定性：关键字相等的记录 稳定的排序方法：排序后不改变先后顺序 不稳定的排序方法：可能改变先后顺序 内部排序：待排数据都在内存 外部排序：排序过程需要访问外存 1. 概述 按排序方法分 插入排序 交换排序 选择排序 归并排序 计数排序 按工作量分 简单的排序方法 O(n2) 先进的排序方法 O(n log n) 基数排序 O(d×n) 1. 概述 排序的基本操作 比较：比较两个关键字的大小 移动：将记录移动到另一个位置 待排记录的存储 数组 sort ( T a[ ], int n ) 链表 地址 2. 插入排序 思路：将待排记录插入已排好的子序列中，不断扩大有序序列。 算法： （1）直接插入排序 （2）希尔排序 （1）直接插入排序 将待排序记录插入有序序列，重复n-1次 80 49 36 14 58 61 (52) 80 52) 36 14 58 61 (49 80) 52 36 14 58 61 (49 52 49 80) 14 58 61 (36 49 36 52 80) 58 61 (14 49 36 52 58 80) 61 (14 49 36 52 58 61 80) (14 （1）直接插入排序：算法 /// 插入排序 template typename T void InsertionSort(T a[], int n) { for (int i = 1; i n; i++) { // 将 a[i] 插入有序序列 a[0..i-1] 中 auto x = a[i]; int j = i - 1; for (; j = 0 x a[j]; j--) a[j + 1] = a[j]; a[j + 1] = x; } } （1）直接插入排序 性能分析： 最好情况：待排记录顺序有序排列 比较：n-1 移动：0 时间复杂度：O(n) 最坏情况：待排记录逆序有序排列 比较：n(n-1)/2 移动：(n+4)(n-1)/2 时间复杂度：O(n2) 平均情况：O(n2) 稳定性：稳定的排序方法 （2）希尔排序 希尔排序，缩小增量排序 思路：先将待排序列分割成若干个子序列，分别进行直接插入排序，基本有序后再对整个序列进行直接插入排序。 充分利用直接插入排序的特点 待排记录较少时排序快 待排记录基本有序时排序快 （2）希尔排序 80 49 36 14 58 61 52 dk=3 58 14 52 49 80 61 36 dk=2 49 14 52 58 80 61 36 dk=1 49 36 52 58 61 80 14 （2）希尔排序：算法 /// 希尔排序 template typename T void ShellSort(T a[], int n) { int dk = n / 2; while (dk = 1) { // 一趟希尔排序，对dk个序列分别进行插入排序 for (int i = dk; i n; i++) { T x = a[i]; int j = i - dk; for (; j = 0 x a[j]; j -= dk) a[j + dk] = a[j]; a[j + dk] = x; } // 缩小增量 dk = dk / 2; } } （2）希尔排序 性能分析 时间复杂度与增量序列有关 通常认为 O(n3/2) 不稳定的排序方法 不相邻元素间有交换 3. 快速排序 借助“交换”进行排序 （1）起泡排序 （2）快速排序 （1）起泡排序 依次比较相邻元素，‘逆序’则交换， 重复n-1趟 80 49 36 14 58 61 52 36 52 14 58 61 80 49 14 36 52 58 61 80 49 49 14 52 58 61 80 36 49 36 52 58 61 80 14