数据结构(C语言版)第10章 内部排序.ppt

10.1 概述 排序——将数据表（a1,a2,……，an）调整为按关键字从小（大）到大（小）排列的过程。 几个术语—— 增排序 减排序 单关键字/多关键字 稳定排序： 排序过程中关键字相同的元素的相对次序不变。 不稳定排序： 排序过程中关键字相同的元素的相对次序发生变化。 内部排序：所有数据在内存 外部排序：部分数据在内存，部分数据在外存（涉及到内外存的交换） 10.1 概述 基本方法： 插入方法 交换方法 选择方法 归并方法 基数方法 评价指标： 时间：比较/移动/交换元素的次数 空间：辅助空间 10.2 插入排序 直接插入排序 希尔排序 10.2 插入排序 — 直接插入排序 基本思想： 将待排序表看作左右两部分， 其中左边为有序区， 右边为无序区, 整个排序过程就是将右边无序区中的元素逐个插入到左边的有序区中，以构成新的有序区。 10.2 插入排序 — 直接插入排序实例 用直接插入排序算法对数据表A=(12,5,4,9,5)从小到大进行排序。 10.2 插入排序 — 直接插入排序算法(1) 10.2 插入排序 — 直接插入排序算法(2) 10.2 插入排序 — 直接插入排序算法分析 稳定性： 稳定排序。 空间性能: 需要一个记录的辅助存储空间 。 时间性能: 与数据表初始状态有关。 最好（有序） 最坏（逆序） 平均 比较： n-1 (n+2)(n-1)/2 O(n2) 移动： 2(n-1) (n+4)(n-1)/2 因而适用于基本有序，规模小的数据 思考：能不能在进行一次插入过程中保证至少有一个元素停留在最终的位置上呢？ 10.2 插入排序 — 希尔排序 基本思想： 将待排序列划分为若干组，在每组内进行直接插入排序，以使整个序列基本有序，然后再对整个序列进行直接插入排序。 分组方法： 对给定的一个步长d(d0)，将下标相差为d的倍数的元素分在一组。 d的取值依次为: d1=n/2, d2=d1/2, ……，dk=1 10.2 插入排序 — 希尔排序实例 10.2 插入排序 — 希尔排序算法及分析 void shell_sort(elementtype A[]){ d=n/2; while(d=1) { //通过步长控制排序的执行过程 for(i=d+1;i=n;i++) {// 依次插入元素A[i]到本组前面的有序子表中 x=A[i];j=i-d; //j指向当前空位置的同一组的前一个位置 while(j0x.keyA[j].key ){ A[j+d].key=A[j].key; j=j-d; //往后移动元素，腾出前面的空位 } A[j+d]=x; // 插入 } d=d/2; } } 稳定性：不稳定。例：6，3，1，3，9，4 空间性能：1个辅助空间。 时间性能: 与数据表初始状态关系不大： 需要循环log2n趟，每趟O(n) 因而时间复杂度为O(nlog2n) 10.3 交换排序 交换排序基本思想：两两比较待排序元 素，发现倒序即交换。 冒泡排序 快速排序 10.3 交换排序 — 冒泡排序 基本思想： 从一端开始，逐个比较相邻的两个元素，发现倒序即交换。 这里按从后往前（从下往上）逐个比较相邻元素。 10.3 交换排序 — 冒泡排序实例 用冒泡排序算法对数据表A=(12,5,4,9,5)从小到大进行排序。 10.3 交换排序 — 冒泡排序算法 简单算法：void bubble_sort(elementtype A[ ],int n){ for (i=1; in; i++ )  for (j=n; j=i+1;j-- ) if (A［j］.keyA［j-1］.key) A［j］==A［j-1］; } 10.3 交换排序 — 冒泡排序算法分析 改进的算法的时间复杂度：受数据表初始状态影响 正序 比较元素的次数为n-1次，而交换次数为0 O (n) 逆序 比较和交换次数为n(n-1)/2 P203 O (n2) 一般