排序算法及算法分析

Hu Junfeng 排序算法及算法分析 2008/05/06 Hu Junfeng 问题的提出： 为什么要排序？有序表的优点？缺点？ 构造关系。 按照什么原则排序？ 比较？ 如何进行排序？ Hu Junfeng 基本概念 排序 （ Sorting）： 简单地说，排序就是把 一组记录 按照某个（或某几个）字 段的值以递增（由小到大）或递减（由大到小）的次序重新排 列的过程。（如按年龄从小到大排序） 学号 姓名 年龄 性别 2004001 张佳 18 男 2004002 王鹏 19 男 2004003 刘宁 17 女 2004004 李娟 18 女 2004005 陈涛 19 男 2004006 李小燕 18 女 Hu Junfeng 作为比较基础的一个 (或多个 )字段，称为 排序码 。排序码可 以是数值、符号或符号串。 排序码 不一定 是关键码， 关键码可以作为排序码 。 关键码是 唯一的，但排序码不一定唯一。排序码不唯一时，排序的结 果可能不唯一。 参与排序的对象，称为记录。一个记录可以包含多个字段。 如果记录集合中存在多个 排序码 相同的记录，经过排序后， 排序码 相同的记录的前后次序保持不变，则这种排序方法称 为是 稳定 的，否则是 不稳定 的。 排序码 与 关键码（ primary key） Hu Junfeng 排序方法可以分为五种 插入 排序、 选择 排序、 交换 排序、 分配 排序和 归并 排序。 在排序过程中，全部记录存放在内存，则称为 内排序 ，如果排序过程中需要使用外存，则称为 外排序。 本章侧重讨论内排序的方法，但有些方法 (特别是归并排序 的思想 )也可以用于外排序。 排序的类型 Hu Junfeng 排序算法的评价 评价排序算法好坏的标准 执行算法所需的时间 执行算法所需要的附加空间 算法本身的复杂程度也是考虑的一个因素 排序的 时间开销 是算法好坏的最重要的标志 排序的时间开销衡量标准 : 算法执行中的比较次数（必须）。 算法执行中的移动次数（有可能避免）。 通常会关注最坏情况和平均情况的开销。 Hu Junfeng 插入排序 选择排序：直接选择排序 交换排序 归并排序 直接插入排序 二分插入排序 起泡排序 快速排序 表插入排序 Shell 排序 堆排序 排序算法 Hu Junfeng 插入排序 基本思想：每步将一个待排序的记录，按其排序 码大小插到前面已经排序的字序列的合适位置， 直到全部插入排序完为止。 0 2 1 1 1( , ,., | , , )k k k na a a b b b x 顺次选取一个元素 插入到合适位置 Hu Junfeng 插入排序的细分类 如何插入到已排好序的序列中？ 直接插入（从后向前找位置后插入） O(n2) 二分法插入（按二分法找位置后插入） O(nlog2n) 表插入排序（按链表查找位置后插入） O(n2) Hu Junfeng 直接插入排序 基本思想： 假定前面 m 个元素已经排序； 取第 (m+1) 个元素，插入到前面的适当位置； 一直重复，到 m=n 为止。 （初始情况下， m = 1） Hu Junfeng 第一趟： 23， 起始只有一个记录 11, 23 11 第二趟： 11， 23， 11， 23， 55 55 第三趟： 11， 23， 55， 11， 23， 55， 97 97 第四趟： 11， 23， 55， 97， 11， 19， 23， 55， 97 19 第五趟： 11， 19， 23， 55， 97， 11， 19， 23， 55， 80， 97 80 示例 ： 23， 11， 55， 97， 19， 80 Hu Junfeng 直接插入排序的算法中记录的数据结构 typedef int KeyType; typedef int DataType; typedef struct KeyType key; /* 排序码字段 */ DataType info; /* 记录的其他字段 */ RecordNode; typedef struct int n; /* n为文件中的记录个数， nMAXNUM */ RecordNode *record; SortObject; Hu Junfeng 直接插入排序算法复杂度评价 极端情况下： 最小比较次数 每个记录仅比较一次 最大比较次数 每个记录比较已 排好序的记录长度 nnC 1m i n 2)1(2 1 21 1 m a x nnniC n i Hu Junfeng 直接插入排序算法评价 2 最小移动次数 最大移动次数 nnM 1mi n 1 1 2 m a x 2)1( n i niM Hu Junfeng 直接插入排序算法评价 3 初始数据状态相关： 文件初态不同时 ， 直接插入排序所耗费的时间有很大 差异 。 若文件初态为 正序 ， 则算法的时间复杂度为 O(n) 若初态为 反序 ， 则时间复杂度为 O(n2) Hu Junfeng 直接插入排序算法评价 4 平均复杂度 插入记录 Ri-1， 有 i种可能的插入位置 ， 即插入到第 0， 1， ， i-1位置上 ， 假设每种情况发生的概率是相等 的 ， 均为 pj = 1/i (j=0,1, ,i-1) 比较次数为 Cj=j+1(j=0, ,i-2,i-2)， 则插入记录 Ri-1 的平均比较次数为 2 1 ) 2 *)1( ( 1 )1( 1 )1( 1 1 0 1 0 1 0 iii i j i j i CP i j i j i j jj Hu Junfeng 直接插入排序算法评价 5 平均复杂度 直接插入排序的 总的比较次数为： )( ) 4 ( 44 3 2 )1( * 2 1 1 1 2 1 2 1 2 1 2 2 2 1 12 nO n O n n nn n l nj n l n j Hu Junfeng 直接插入排序算法评价 6 小结 直接插入排序算法的平均移动次数与平均比较次数同级 ， 也是 O(n2) 直接插入排序的平均时间复杂度为 T(n) = O(n2) 算法中引入了一个附加的记录空间 temp， 因此辅助空间 为 S(n) = O(1) 直接插入排序是 稳定 的 Hu Junfeng 存储结构与算法优化 顺序存储结构： 二分插入算法，减少比较次数。 链式存储结构： 减少移动次数。 Hu Junfeng 二分法插入排序 特点：在直接插入排序的基础上减少比较的次数，即 在插入 Ri时改用二分法比较找插入位置，便得到 二分 法插入 排序 限制：必须采用 顺序存储 方式。 Hu Junfeng 例：有 6个记录 ， 前 5 个已排序的基础上 ， 对第 6个记录排序 。 15 27 36 53 69 42 low mid high 15 27 36 53 69 42 low high mid 15 27 36 53 69 42 high low 15 27 36 42 53 69 (high36 ) ( 4253 ) Hu Junfeng 二分法插入排序算法 void binSort(SortObject * pvector) int i, j, left, mid, right; RecordNode temp; for( i = 1; i n; i+ ) temp = pvector- recordi; left = 0; right = i 1; while (left = right) mid = (left+right)/2； if (temp.key recordmid.key) right = mid-1; else left = mid+1; /while for(j=i-1; j=left; j-) pvector-recordj+1 = pvector-recordj; if(left != i) pvector-recordleft = temp; / for / binSort Hu Junfeng 二分插入排序比较次数 二分插入排序的比较次数与待排序记录的初始状态无关， 仅依赖于记录的个数，插入第 i个记录时，如果 ，则无论排序码的大小，都恰 好经过 次比较才能确定插入位置，如果， 则比较次数为 j+1，因此，将 n(n=2k)个记录 排序的总比较次数为 nji j 2l o g0(2 ij 2lo g 122 jj i nnnnn kkki n i 22 1 2 l og1l og .2210l og Hu Junfeng 二分法插入排序方法性能分析 当 n较大时 ， 比 直接插入排序的 最大比较次数少 得多 。 但 大于 直接插入排序的 最小比较次数 算法的移动次数与直接插入排序算法的相同 最坏 的情况为 n2/2 最好 的情况为 n 平均 移动次数为 O(n2) 二分法插入排序算法的平均时间复杂度为 T(n)= O(n2) 二分插入排序法是 稳定 的排序算法 ,在检索时采用 leftright 结束， left、 right的修改原则是： temp.key recordmid.key，保证排序是稳定的。 Hu Junfeng 结论 移动次数与直接插入排序相同，最坏的情况为 n2/2 ，最好的情况为 n，平均移动次数为 O(n2) 二分法插入排序算法的平均时间复杂度为 T(n)= O(n2) 二分法插入排序是稳定的 Hu Junfeng 表插入排序 表插入排序是在直接插入排序的基础上减少移动的次数 。 基本思想 : 在记录中设置一个指针字段 ， 记录用链表连接 插入记录 Ri时 ， 记录 R0至 Ri-1已经排序 ， 先将记录 Ri脱链 再采用顺序比较的方法找到 Ri应插入的位置 ， 将 Ri插入链表 。 Hu Junfeng struct Node; /* 单链表结点类型 */ typedef struct Node ListNode; struct Node KeyType key; /* 排序码字段 */ DataType info; /* 记录的其它字段 */ ListNode *next; /* 记录的指针字段 */ ; typedef ListNode * LinkList; 表插入算法中记录的数据结构 Hu Junfeng 表插入排序的算法性能分析 第 i趟排序：最多比较次数 i次，最少比较次数 1次。 n-1趟总的比较次数： 最多： 最少： n-1 记录移动次数： 0 时间效率： O(n2) 辅助空间： O(n) 指针 稳定性： p-key key保证稳定的排序。 2 )1(1 1 nnin i Hu Junfeng shell排序 Shell排序法 又称 缩小增量法 ， 由 D.L.Shell在 1959年提出 ， 是对直接插入排序法的改进 思想 : 直接插入排序中 ， 当初始序列为逆序时 ， 时间效率最 差 。 若初始序列基本有序时 ， 则大多数记录不需要插 入 ， 时间效率大大提高 。 另外 ， 当记录数 n较小时 ， n2值受 n的值影响不大 。 Shell排序正是从这两个方面考虑 对直接插入排序进行 改进 。 Hu Junfeng 基本方法 先取一个整数 d1n， 把全部记录分成 d1个组 ， 所有距离为 d1倍数的记录放在一组中 ， 先在各组内排序 然后取 d2 = d1 /k 重复上述分组和排序工作 直到 di=1， 即所有记录放在一组中为止 各组内的排序可以采用直接插入法 ， 也可以采用后面讲到 的其它排序方法 ， 如直接选择排序 。 Hu Junfeng 示例 ： 49, 38, 65, 97, 13, 76, 27, 49 原始序列 49 38 65 97 13 76 27 49 d=4 - - - - - - - d=2 13 38 27 49 49 76 65 97 - - - - - - d=1 13 38 27 49 49 76 65 97 - - - - - - - 排序结果： 13 27 38 49 49 65 76 97 Hu Junfeng shell排序算法分析 Shell排序算法的速度比直接插入排序快 ， 其时间复杂度 分析比较复杂 ， Shell排序的平均比较次数和平均移动次 数都为 n1.3左右 Shell排序算法中增加了一个辅助空间 temp， 因此算法的 辅助空间为 S(n)=O(1) Shell排序是 不稳定的 。 Hu Junfeng di有各种不同的取法： Shell最早提出 d1= ， di+1= ， D.Knuth教授建议取 di+1= 。 一般认为 di都取成奇数、 di之间互素为好，究竟如何选 取 di最好 ?理论上至今仍没有完全解决。 2 n 2 id 3 1id Hu Junfeng 选择排序 思想 ：每趟从待排序的记录序列中 选择关键字最 小的记录 放置到已排序表的最前位置，直到全部 排完。 关键问题 ：在剩余的待排序记录序列中 找到最小 关键码记录。 方法 ： 直接选择排序 堆排序。 Hu Junfeng 直接选择排序 方法是 首先在所有记录中选出排序码 最小 的记录 ， 与 第一个 记录 交换 然后在其余的记录中再选出排序码 最小 的记录与 第二个 记录 交 换 以此类推 ， 直到所有记录排好序 Hu Junfeng Example Hu Junfeng Hu Junfeng 直接选择排序性能分析 选择排序的 比较次数与记录的初始状态无关 。 第 i趟排序：从第 i个记录开始，顺序比较选择最小关键码记录需 要 n-i次比较。 总的比较次数： 移动次数 ： Mmin = 0 (初始为正序时） 最多移动次数： Mmax = 3(n-1) (初始为逆序时，每趟 1次交换， 3 次移动完成） 时间复杂度： T(n)=O(n2)， 辅助空间 1个记录单位： Temp， 稳定性： 不稳定 的排序。 2 )1()(1 1 nninn i Hu Junfeng 39 选择排序 直接选择排序 堆排序 Hu Junfeng 堆排序 (heap sort) 堆的定义 ： n个排序码序列 K=k0,k1,k2,k n-1当且仅当满足如 下条件时，称之为堆。 ki k2i+1 ki k2i+1 ki k2i+2 ki k2i+2 (i=0,1,2,.,n/2-1) 从定义可以看出，若将此序列看成完全二叉树，则堆的含义 表明，完全二叉树中每个非叶结点的排序码均大于等于（或 小于等于）其左右子女结点的排序码。 如果堆中根结点的排序码最小，则称为 小根堆 。 如果堆中根结点的排序码最大，则称为 大根堆 Hu Junfeng 堆排序的主要思想 1. 设法把原始序列构造成一个堆，使得 n个元素的 最大值 处 于序列的第一个位置； 2. 然后交换序列第一个元素 (最大值 元素 )与 最后一个 元素； 3. （选到一个最大的元素） 4. 再把序列的 前 n-1个元素 组成的子序列构成一个新堆，得 到 第二大 元素，把序列的第一个元素与 第 n-1个 元素交换。 5. 再把序列的 前 n-2个元素 构成一个新堆 ，如此操作， 最终整个序列成为有序序列。 Hu Junfeng 关键问题与建堆方法 关键问题 ：如何将原始序列构成初始堆，丢掉最大值后如何构 造新堆？ 初始完全二叉树中， n/2 ， n/2 +1， ， n-1为叶子，以其为 根的子树必然为堆。因此，初始堆建立时，只需要将所有非叶 结点为根的子树调整为堆。 建堆方法 ：可采用“ 筛选法 ”为以 Ri为根的完全二叉树建堆。 假定： Ri 的左、右子树都是堆，可以把 Ri与其左、右子树根结 点 R2i+1、 R2i+2中最大者交换位置。若交换位置后破坏了子树的 堆特性，则再对这棵子树重复交换过程，直到以 Ri为根结点的 子树成为堆 (shift函数 )。 Hu Junfeng 示例 初始序列为 21， 25， 49， 25*， 16， 08 Hu Junfeng 44 Hu Junfeng 45 Hu Junfeng 时间效率评价 建初始堆比较次数 C1： O(n) 重新建堆比较次数 C2： O(nlog2n) 总比较次数 =C1+C2 移动次数小于比较次数 因此， 时间复杂度： O（ nlog2n） 空间复杂度： O（ 1） 适用于 n值较大的情况。 算法稳定性： 不稳定 Hu Junfeng 47 内容提要 排序的基本概念 插入排序 选择排序 交换排序 分配排序 归并排序 Hu Junfeng 48 交换排序 交换排序的基本方法 两两比较 待排序记录的排序码 ， 交换不满足顺序要求的偶 对 ， 直到全部满足为止 交换排序的分类 起泡排序 快速排序 Hu Junfeng 49 起泡排序 方法 先将序列中的第一个记录 R0与第二个记录 R1比较，若前者 大于后者，则两个记录交换位置，否则不交换 然后对新的第二个记录 R1与第三个记录 R2作同样的处理 依次类推，直到处理完第 n-1个记录和第 n个记录 从 (R0， R1)到 (Rn-2， Rn-1)的 n-1次比较和交换过程称为 一次起 泡 经过这次起泡， n个记录中最大者被安置在第 n个位置上 Hu Junfeng 50 此后 ， 再对 前 n-1个记录 进行同样处理 ， 使 n-1个记录 的最大者被安置在整个序列的第 n-1个位置上 。 然后再对前 n-2个记录重复上述过程 ， 这样最多做 n- 1次起泡 就能完成排序 可以设置一个标志 noswap表示本次起泡是否有记录交 换 ， 如果没有交换则表示整个排序过程完成 起泡排序是通过相邻记录之间的比较与交换，使值较 大的记录逐步从前 (上 )向后 (下 )移，值较小的记录逐步 从后 (下 )向前 (上 )移，就像水底的气泡一样向上冒，故 称为 起泡排序 起泡排序方法 Hu Junfeng 51 初始序列为 49, 38, 65, 97, 76, 13, 27, 49，请用起泡排序法 排序 第一趟起泡 38 49 65 76 13 27 49 97 第二趟起泡 38 49 65 13 27 49 76 97 第三趟起泡 38 49 13 27 49 65 76 97 例 题 Hu Junfeng 52 第四趟起泡 38 13 27 49 49 65 76 97 第五趟起泡 13 27 38 49 49 65 76 97 第六趟起泡 13 27 38 49 49 65 76 97 排序结果为 13 27 38 49 49 65 76 97 例 题 (续 ) Hu Junfeng 若文件初状为 正序 ， 则一趟起泡就可完成排序 ， 排序码的比较 次数为 n-1， 且没有记录移动 ， 时间复杂度是 O(n) 若文件初态为 逆序 ， 则需要 n-1趟起泡 ， 每趟进行 n-i次排序码的 比较 ， 且每次比较都移动三次 ， 比较和移动次数均达到最大 值 起泡排序的算法评价 )(2/)1(3)(3 )(2/)1()( 2 1 1 ma x 2 1 1 ma x nOnninM nOnninC n i n i Hu Junfeng 起泡排序的算法评价 (续 ) 起泡排序 最好 时间复杂度是 O(n) 起泡排序 最坏 时间复杂度为 O(n2) 起泡排序 平均 时间复杂度为 O(n2) 起泡排序算法中增加一个辅助空间 temp，辅助空 间为 S(n)=O(1) 起泡排序是 稳定的 Hu Junfeng 课外预习材料： MIT Introduction.to.Algorithms 01.Analysis.of.algorithm Introduction.to.Algorithms.-.02.Solving.Recurrence (part1 chapter4) Hu Junfeng 作业与上机 P278 算法题： 4， 5 （要求在注释部分写算法设计思路 ,分析时间、空间复杂 性） 提交： 5.10