算法课件--第9章(内排序).ppt

第九章内排序 基本概念 插入排序 冒泡排序 选择排序 计数排序 希尔排序 堆排序 快速排序 合并排序 基数排序 设含有n个记录的文件 R1 R2 Rn 其相应的关键字为 K1 K2 Kn 需确定一种排列P 1 P 2 P n 使其相应的关键字满足如下的递增 或递减 关系 KP 1 KP 2 KP 3 KP n 即 使上述文件成为一个按其关键字线性有序的文件 RP 1 RP 2 RP n 这样一种运算称为排序 9 1基本概念 如果在排序期间具有相同关键字的记录的相对位置不变 则称此方法是稳定的 排序 排序的稳定性 即 1 K i K i 1 1 i n 1 2 若在输入文件中i j 且Ki Kj 则在经过排序后的文件中仍Ri先于Rj 排序 内排序 整个排序过程都在内存进行的排序 外排序 当文件很大以至于内存不足以存放全部记录 在排序过程中需要对外存进行存取访问 例如 将下列关键字序列52 49 80 36 14 58 61 23 97 75调整为14 23 36 49 52 58 61 75 80 97 内部排序的方法在排序的过程中 参与排序的记录序列中存在两个区域 有序区和无序区 内部排序的过程是一个逐步扩大记录的有序序列长度的过程 使有序区中记录的数目增加一个或几个的操作称为一趟排序 存放待排序数据的数据结构 typedefstruct intkey datatypeotheritem 其他域 records typedefstructrecordsList n 1 逐步扩大记录有序序列长度的方法大致有下列几类 1 插入类 将无序子序列中的一个或几个记录 插入 到有序序列中 从而增加记录的有序子序列的长度 2 交换类 通过 交换 无序序列中的记录从而得到其中关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 3 选择类 从记录的无序子序列中 选择 关键字最小或最大的记录 并将它加入到有序子序列中 以此方法增加记录的有序子序列的长度 4 归并类 通过 归并 两个或两个以上的记录有序子序列 逐步增加记录有序序列的长度 5 其它方法 内排序 插入类排序 直接插入排序 折半插入排序 希尔排序 交换类排序 冒泡排序 快速排序 选择类排序 选择排序 堆排序 归并类排序 归并排序 其他排序 计数排序 基数排序 9 2计数排序 对每个记录计算文件中有多少个其它记录的关键字大于该记录的关键字值 从而找到该记录的正确排序位置 keyinfocount 设一个记录有三个域 排序算法的思想 for i 1 i n i for j i 1 j n j if R i key R j key R i count R i count 1 elseR j count R j count 1 voidcountsort ListR intn for i 1 i n i R i count 1 对所有元素的count域置1 算法如下 设文件有n个记录 则外循环 i 1时 内循环要做n 1次比较 i 2时 内循环要做n 2次比较 i n 1时 内循环要做1次比较 总的比较次数为 n 1 n 2 1 n n 1 2 算法性能分析 所以 算法所需时间为O n2 由于不需要记录移动和额外空间 同时算法简单 当n较小时 可采用本算法 例关键字序列 46 55 13 42 44 17 05 70 9 3直接插入排序 假设在排序过程中 记录序列R 1 n 的状态为 则一趟插入排序的基本思想为 将记录R i 插入到有序子序列R 1 i 1 中 使记录的有序序列从R 1 i 1 变为R 1 i 显然 完成这个 插入 需分三步进行 1 查找R i 的插入位置j 1 2 将R j 1 i 1 中的记录后移一个位置 3 将R i 复制到R j 1 的位置上 直接插入排序 利用顺序查找实现 在R 1 i 1 中查找R i 的插入位置 的插入排序 注意直接插入排序算法的三个要点 1 从R i 1 起向前进行顺序查找 监视哨设置在R 0 R 0 R i 设置 哨兵 j i 1 while R 0 key R j key j j 1 从后往前找 Return j 1 返回R i 的插入位置为j 1 2 对于在查找过程中找到的那些关键字不小于R i key的记录 并在查找的同时实现记录向后移动 while R 0 key R j key R j 1 R j j j 1 3 i 2 3 n 实现整个序列的排序 排序算法如下 voidinsort Listr intn r为给定的表 其记录为r i i 0 1 n x为暂存单元 for i 2 i n i r 0 r i r 0 作为标志位j i 1 while r 0 key r j key r j 1 r j j j从i 1至0 r j key与r i key进行比较r j 1 r 0 insort 排序的时间分析 实现排序的基本操作有两个 1 比较 序列中两个关键字的大小 2 移动 记录 对于直接插入排序 最好的情况 关键字在记录序列中顺序有序 最坏的情况 关键字在记录序列中逆序有序 总的说来 直接插入排序所需进行关键字间的比较次数和记录移动的次数均为n2 4 所以直接插入排序的时间复杂度为O n2 9 4折半插入排序 排序算法的思想 由于直接插入排序的内循环 从1到i 1 的查找 或说是比较 是在 部分 有序表的环境下进行的 所以内循环用 折半查找法 比用顺序查找法快 算法描述如下 voidbinsort Listr intn for i 2 i n i r 0 r i low 1 high i 1 while low high m low high 2 ifr 0 key r m keyhigh m 1 elselow m 1 for j i 1 j low j r j 1 r j 把从第low起到第i 1各记录后移r low r 0 将第i个记录插入 binsort 9 5冒泡排序 排序算法的思想 比较k1和k2 如果这些关键字的值不符合排序顺序 就交换k1和k2 然后对记录k2和k3 k3和k4等等进行相同的工作 直到kn 1和kn为止 到此得到一个最大 或最小 关键字值存在kn的位置上 通常将此过程叫做一趟 重复这个过程 就得到在位置kn 1 kn 2等处的适当记录 使得所有记录最终被排好序 例如 将5个记录的关键字7 4 8 3 9进行冒泡排序 排序后k1 k2 kn n 5 因为到第四趟就没有交换的偶对了 所以整个排序结束 算法描述如下 voidbubblesort Listr intn for m 1 mr i max r m r m r i r i max all F k while all F k 1 冒泡排序的结束条件为 最后一趟没有进行 交换 冒泡排序是一种稳定的排序算法 时间分析 最好的情况 关键字在记录序列中顺序有序 只需进行一趟起泡 最坏的情况 关键字在记录序列中逆序有序 需进行n 1趟起泡 9 6希尔排序 基本思想 对待排序记录序列先作 宏观 调整 再作 微观 调整 所谓 宏观 调整 指的是 跳跃式 的插入排序 即 将记录序列分成若干子序列 每个子序列分别进行插入排序 待整个序列中的记录 基本有序 时 再对全体记录进行一次直接插入排序 假设将n个记录分成d个子序列 则这d个子序列分别为 R 1 R 1 d R 1 2d R 1 kd R 2 R 2 d R 2 2d R 2 kd R d R 2d R 3d R kd R k 1 d 其中 d称为增量 它的值在排序过程中从大到小逐渐缩小 直至最后一趟排序减为1 例如 第二趟希尔排序 设增量d 3 第三趟希尔排序 设增量d 1 希尔排序的算法描述如下 voidShellInsert Listr intd 本算法对直接插入算法作了以下修改 1 前后记录位置的增量是d 而不是1 2 r 0 只是暂存单元 不是哨兵 当j0 and r 0 r j r j d r j 记录后移 查找插入位置j j d r j d r 0 插入 for i 2 i n i r 0 r i j i 1 while r 0 key r j key r j 1 r j j j 1 r j 1 r 0 VoidShell sort Listr intdlta intt 按增量序列dlta 0 t 1 对顺序表r作希尔排序for k 0 k t k ShellInsert r dlta k 先取定一个两项之间的距离d1 n 其中n为整个表的长度 反复比较每两个相距d1的项 直到以d1为距离划分的组排序好为止 至此一趟排序完成 然后取d2 d1 再继续以d2为距离反复比较每两个相距为d2的项 依此类推 取每个di 1 di 直到dt 1为止 第二趟后结果 d2 2 0517134246559470 13 46分别交换两次 0513174246557094 第三趟后结果 d3 1 NorthChinaElectricPowerUniversity 9 7选择排序 基本思想 首先在n个记录中选择一个具有最小或最大关键字的记录 将选出的记录与记录集合中的第一个记录交换位置 然后在r 2 至r n 中选择一个最小或最大的值与r 2 交换位置 依此类推 直至r n 1 和r n 比较完毕 voidslsort Listr intn 每次从r j j i 1 n 中选了最小值 与r i i 1 2 n 1 交换 进行分类 for i 1 i n 1 i 共进行n 1趟排序 m i for j i 1 j n j if r j key r m key m j m指示关键字最小的记录的序号if m i x r i r i r m r m x 例关键字序列 055 55 60 13 05 94 17 70 利用选择排序算法进行排序 不稳定 算法的复杂性分析 当选则第一个最小值时需进行n 1次比较 选第二个最小值时需进行n 2次比较 选n 1个最小值时需进行n n 1 次比较 所以总的比较次数为 n 1 n 2 2 1 n n 1 2故排序n个记录需要时间为O n2 由于执行一次交换 需三次移动记录 最多交换n 1次 故最多移动次数为3 n 1 NorthChinaElectricPowerUniversity 9 8堆排序 1 定义 堆是由n个记录的线性序列 R1 R2 Rn 其关键字序列 k1 k2 kn 满足下列特性时 称之为堆 或 若将此数列看成是一棵完全二叉树的顺序存储表示 则堆或是空树或是满足下列特性的完全二叉树 其左 右子树分别是堆 并且当左 右子树不空时 根结点的值小于 或大于 左 右子树根结点的值 下列两个序列为堆 对应的完全二叉树如下图 96 83 27 38 11 09 ki k2i ki k2i 1 ki k2i ki k2i 1 大根堆 小根堆 12 36 24 85 47 30 53 91 1 首先将一个关键字集合用完全二叉树的形式排列 如给定关键字集合为 46 55 13 42 94 17 05 70 组成的完全二叉树如下 2 建堆的过程 2 开始建堆 采用筛选法 逐步将大的关键字筛到堆底 筛选法的思想是这样的 假设集合r有m个结点 从某个结点i 第一次i m 2 开始筛选 先看第i个结点的左右子树 设第i个结点的左子树为kj 右子树为kj 1 若kjkj则对调 小的上来大的下去 然后kj作为新的根结点 再对新的根结点的左右子树进行判断 重复上述过程 直到某个结点的左或右子树根结点的下标大于m为止 第一次调用筛选法 m 8 i m 2 4 从i 4开始 看k4的左右子树 仅有左子树 因此42与70比较 42 70 所以不变 j i 2 8 i j 再向下看 此时的i无左右子树 所以返回 如右图所示 第二次调用筛选法 i 3 k3 13 13的左右子树为17和05 因17 05 故沿右子树比较 13 05 进行对调 此时13无左右子树 所以返回 NorthChinaElectricPowerUniversity 05 13 46 55 13 42 94 17 05 70 46 55 05 42 94 17 13 70 先看第i个结点的左右子树 设第i个结点的左子树为kj 右子树为kj 1 若kjkj则对调 小的上来大的下去 然后kj作为新的根结点 再对新的根结点的左右子树进行判断 重复上述过程 直到某个结点的左或右子树根结点的下标大于m为止 第三次调用筛选法 i 2 k2 55 因为42 94 所以沿左子树筛选 42 55 进行对调 此时55还有左子树70 因55 70 所以不变 再向下70无左右子树 所以返回 此时二叉树如右图所示 第四次调用筛选法 i 1 k1 46 因为05 42 所以沿右子树筛选 05 46 进行对调 此时46还有左右子树17 13 因13 17 所以再沿右子树筛选 13 46 所以对调 46无左右子树 所以返回 此时二叉树如右图所示 NorthChinaElectricPowerUniversity 55 42 46 05 46 13 46 42 05 55 94 17 13 70 05 42 13 55 94 17 46 70 先看第i个结点的左右子树 设第i个结点的左子树为kj 右子树为kj 1 若kjkj则对调 小的上来大的下去 然后kj作为新的根结点 再对新的根结点的左右子树进行判断 重复上述过程 直到某个结点的左或右子树根结点的下标大于m为止 3 建堆的算法voidsift Listr intk intm 对m个结点的集合r从某个结点i k开始筛选 如果r j r j 1 j 2i 则沿右 分支筛 否则沿左分支筛 把关键字大的筛到堆底 i k j 2 i x r i r i x 将x放在适当的位置 sift NorthChinaElectricPowerUniversity while jr j 1 key 左子树 右子树j 沿右筛 if x key r j key r i r j i j j 2 i 将关键字小的换到i位置 x key再准备与下一层的比较 elsej m 1 强制跳出while循环 以上面建的堆为例 说明重建堆的执行过程 05 42 13 55 94 17 46 70 70 42 13 55 94 17 46 05 13 42 17 55 94 70 46 46 42 17 55 94 70 05 05 05 70 X 05 42 13 55 94 17 46 70 13 42 17 55 94 70 46 05 13 46 13 70 4 堆排序过程 13 17 42 46 55 94 70 05 13 70 42 46 55 94 05 17 13 42 55 46 70 94 05 17 13 94 55 46 70 05 17 42 46 55 94 70 13 05 X 17 70 17 42 55 46 70 94 17 13 05 42 94 42 70 42 17 13 46 55 94 70 05 42 17 13 70 55 94 05 46 42 17 13 55 70 94 05 46 42 17 13 94 70 05 46 55 94 70 42 17 13 05 46 70 46 X 55 70 94 46 42 17 13 05 55 94 55 70 70 70 94 55 46 42 17 13 05 94 55 46 42 17 13 05 70 94 55 46 42 17 13 05 70 94 70 94 70 55 46 42 17 13 05 堆排序的过程 用拔尖的方法将堆顶输出 把最后一个元素送到树根上 然后从i 1开始 调用筛选算法重新建堆 再将堆顶输出将最后一个送到树根 再重新建堆 如此反复 直到得到最后全部排序好的关键字序列 算法描述如下 voidheapsort Listr intn 对n个结点的集合r进行堆排序 for i n 2 i 1 i sift r i n 从第 n 2 个结点开始进行筛选建初始堆 headsort for k n k 2 k t r k r k r 1 r 1 t printf d r k sift r 1 k 1 重建堆 printf d r 1 输出最后一个元素即最大元素 NorthChinaElectricPowerUniversity 1 对深度为h的堆 筛选 所需进行的关键字比较的次数至多为2 h 1 5 堆排序的时间复杂度分析 因此 堆排序的时间复杂度为O nlogn 3 调整 堆顶 n 1次 总共进行的关键字比较的次数不超过 例 关键字序列 3 27 36 027 输出序列为 3 027 27 36 不稳定 6 堆排序的稳定性分析 NorthChinaElectricPowerUniversity 9 9快速排序 快速排序又称分划交换排序 设输入文件有n个记录R1 R2 Rn 它们对应的关键字是k1 k2 kn 该方法先取序列中任一关键字K 通常取第一个 然后用K从两头到中间进行比较 交换 就能形成一个分划 凡是小于等于K的被移到左边 凡是大于K的被移到右边 1 快速排序的定义 NorthChinaElectricPowerUniversity 2 快速排序步骤 2 从最末项kn开始起指针j倒向前找到第一个kj x key或i j时 则判i j 是 kj送ki i i 1 1 选定k1为起点 且将k1送x 3 从ki项起指针i向前扫描 找到第一个ki x key或i j时 则判i j 是 ki送kj j j 1 4 上述过程进行到i j时停止 将x送ki 同时i i 1 j j 1 即x在正确位置上 并分K为K1和K2两个子集合 5 重复调用上述过程 直到将整个集合排序好为止 例 初始关键字 4655134294051770 将46 x 第一次交换后 55134294051770 第二次交换后 17551342940570 第三次交换后 17134294055570 第四次交换后 17051342945570 至此 完成第一趟排序 17 55 05 94 46 第五趟排序后0513174246557094 第一趟排序后 17051342 46 945570 第二趟排序后 1305 17 42 46 945570 第三趟排序后 05 1317 42 46 945570 第四趟排序后0513174246 7055 94 例 初始关键字 4655134294051770 接上例 voidqksort Listr intL intP 将r L 至r P 进行排序 qksort 3 快速排序算法 do while r j key x key i L j P x r i 置初值 r i x i j 一趟快排结束 将x移至正确位置if L j qksort r L j 反复排序前一部分if i P qksort r i P 反复排序后一部分 NorthChinaElectricPowerUniversity 快速排序是目前内部排序中最快的方法 若关键字的分布式均匀的 可以粗略的认为每次划分都把文件分成长度相等的两个文件 4 快速排序算法的性能分析 但如果原来的文件是有次序的 时间复杂性为O n2 因此 快速排序偏爱一个无次序的文件 令T n 为分类n个记录所需之比较次数 设n 2k 则k log2n 有 T n cn 2T n 2 其中cn为进行一趟排序所需的时间 T n cn 2 cn 2 2T n 4 2cn 4T n 4 kcn 2kT 1 O nlog2n 5 快速排序算法的稳定性分析 例 关键字序列 5 2 02 第一次交换后 02202 5 x 第二次交换后 022 02 至此 完成排序 序列为 02 2 5 第一次交换 022 5 02 x 第一趟 无交换25 第二趟 5 不稳定 02 例K 46 79 56 38 40 84 1 它的初始堆是 2 快速排序第一趟结果 1 2 40 38 46 56 79 84 NorthChinaElectricPowerUniversity 归并排序的基本思想是 将两个或两个以上的有序子序列 归并 为一个有序序列 在内部排序中 通常采用的是2 路归并排序 即 将两个位置相邻的有序子序列归并为一个有序序列 9 10归并排序 NorthChinaElectricPowerUniversity 2 路归并排序算法 voidmerge intL intm intn Listr Listr2 表r可看成两个文件首尾相接的两个文件 即需合并的两个文件为r 合并到第三个表r2上 i L k L j m 1 从L开始while im COPY r j n r2 将r j 至r n 照抄至r2上 即表1完照抄第2个表elseCOPY r i m r2 将r i 至r m 照抄至r2上 merge NorthChinaElectricPowerUniversity 采用2 路归并算法进行排序的思想 先将初始文件分成长度为 的n个子文件并且合并到相邻的子文件 则可以得到大约n 2个长度为2的子文件 重复上述过程 直到仅剩下一个长度为n的文件 下面的例子显示了这个排序过程 直接合并排序 每个子文件用方括号括起来 初始文件2557483712928633 n 8个子文件 25 57 48 37 12 92 86 33 第一趟 2557 3748 1292 3386 第二趟 25374857 12338692 第三趟 1225333748578692 NorthChinaElectricPowerUniversity 设一个辅助数组aux 被用于保存合并x的两个子数组所得的结果 变量size用于控制被合并的子文件的大小 因为每次被合并的两个子文件总是x的两个子数组 所以必须用变量来指出子数组的上下界 ib1和ub1分别表示待合并的第一个子文件的下界与上界 ib2和ub2分别表示待合并的第二个子文件的下界和上界 变量i和j用来指示待合并的两个子文件 即源文件 的元素 变量k用于指示合并得到的目标子文件的元素 归并排序算法 voidmergsort Listx intn x数组用来存放待合并的文件 n为待合并子文件的个数 size 1 置被合并的文件长度为1 while size n ib1 1 为第一个文件初始化下界k 1 k是辅助数组的标号 NorthChinaElectricPowerUniversity while ib1 sizen ub2 n elseub2 ib2 size 1 merge ib1 ub1 ub2 x aux ib1 ub2 1 复制最后一个文件i ib1 while k n aux x x i k i 调整x和问题规模for k 1 k n k x k aux k size 2 size whilesize ndo mergsort 从上面的算法可以看出size变量的取值不超过log2n个 对size的每一个取值都扫描n个记录 所以归并排序的时间复杂性为O nlog2n NorthChinaElectricPowerUniversity 9 11基数排序 借助 多关键字排序 的思想来实现 单关键字排序 的算法 1 多关键字的排序假设有n个记录的序列 R1 R2 Rn 每个记录Ri中含有d个关键字 Ki0 Ki1 Kid 1 则称上述记录序列对关键字 Ki0 Ki1 Kid 1 有序是指 对于序列中任意两个记录Ri和Rj 1 i j n 都满足下列 词典 有序关系 Ki0 Ki1 Kid 1 Kj0 Kj1 Kjd 1 其中K0被称为 最主 位关键字 Kd 1被称为 最次 位关键字 实现多关键字排序通常有两种作法 最高位优先MSD法 先对K0进行排序 并按K0的不同值将记录序列分成若干子序列之后 分别对K1进行排序 依次类推 直至最后对最次位关键字排序完成为止 1 多关键字的排序 NorthChinaElectricPowerUniversity 最低位优先LSD法 先对Kd 1进行排序 然后对Kd 2进行排序 依次类推 直至对最主位关键字K0排序完成为止 排序过程中不需要根据 前一个 关键字的排序结果 将记录序列分割成若干个 前一个 关键字不同的 子序列 例如 学生记录含三个关键字 系别 班号和班内的序列号 其中以系别为最主位关键字 LSD的排序过程如下 NorthChinaElectricPowerUniversity 2 链式基数排序假如多关键字的记录序列中 每个关键字的取值范围相同 则按LSD法进行排序时 可以采用 分配 收集 的方法 其好处是不需要进行关键字间的比较 对于数字型或字符型的单关键字 可以看成是由多个数位或多个字符构成的多关键字 此时可以采用这种 分配 收集 的办法进行排序 称作基数排序法 例如 对下列这组关键字 209 386 768 185 247 606 230 834 539 首先按其 个位数 取值分别为0 1 9 分配 成10组之后按从0至9的顺序将它们 收集 在一起 然后按其 十位数 取值分别为0 1 9 分配 成10组 之后再按从0至9的顺序将它们 收集 在一起 最后按其 百位数 重复一遍上述操作 便可得到这组关键字的有序序列 2 链式基数排序 4 对每个关键字位均重复2 和3 两步 在计算机上实现基数排序时 为减少所需辅助存储空间 应采用链表作存储结构 即链式基数排序 具体作法为 待排序记录以指针相链 构成一个链表 2 分配 时 按当前 关键字位 所取值 将记录分配到不同的 链队列 中 每个队列中记录的 关键字位 相同 3 收集 时 按当前关键字位取值从小到大将各队列首尾相链成一个链表 3 基数排序步骤 例如 有一组关键字 179 208 306 093 859 984 055 009 271 033 这些关键字是10进制数 基数rd 10 位数d 3 文件的初始状态是一个单链表 表头指针指向第一个记录 第一趟分配对最低位关键字 个位数 进行 改变记录的指针值将文件中的记录分配至10个队列 桶 中去 每个队列中的记录关键字的个位数均相等 如图 a 所示 其中f i 和e i 分别为第i个队列的头指针和尾指针 第一趟收集是改变所有非空队尾记录的指针域 令其指向下一个非空队列的队头记录 重新将10个队列中的记录链成一个链表文件 前沿指针 a 第一趟分配之后 b 第一趟收集后的链式 第二趟分配 第二趟收集及第三趟分配和第三趟收集分别是对十位数和百位数进行的 其过程和个位数相同 如图 c 所示 至此 排序完毕 若想从大到小排序 分配的过程与上述相同 收集的过程是从第e 9 队列向第e 0 方向收集 009 208 306 984 093 055 033 859 271 179 093 055 033 e 第三趟分配之后 208 179 271 009 306 984 859 提醒注意 分配 和 收集 的实际操作仅为修改链表中的指针和设置队列的头 尾指针 为查找使用 该链表尚需应用算法Arrange将它调整为有序表 NorthChinaElectricPowerUniversity 基数排序的算法简单描述如下 数据类型定义如下 defineMAX NUM OF KEY8 关键字项数 位数 的最大值 defineRADIX10 defineMAX SPACE10000typedefstruct KeysTypekeys MAX NUM OF KEY 关键字InfoTypeotheritems 其他数据项intnext SLCell 静