关 键 词：

语言程序设计 课件 黄维通

资源描述：

C语言程序设计（第3版）课件-黄维通,语言程序设计,课件,黄维通

内容简介：

清华大学黄维通设计制作 1 第7章排序及查找算法及其实现 清华大学黄维通设计制作 2 本章主要内容 排序概述冒泡排序法的设计及其实现选择排序法的设计及其实现插入排序法的设计及其实现SHELL排序法的设计及其实现快速排序设计及其实现查找概述顺序查找及其应用折半查找及其应用 清华大学黄维通设计制作 3 在工程领域的计算机程序设计中 使用最广泛的 也是研究最充分的课题就是排序和查找算法了 有关排序和查找的算法遍布在千千万万的程序中 无论是数据库程序 还是各种编译程序 各种游戏 无一不用到排序和查找算法的 7 1排序概述 清华大学黄维通设计制作 4 所谓排序 就是将一个数据元素 或记录 的任意序列 按照指定的关键字 重新排成一个有序的序列 一般来说 排序处理时要指定排序所基于的关键字 排序算法就是根据关键字来比较的 当排序过程中需要交换的时候 则是对含有关键字的整条信息进行交换 9 1 1排序的概念 清华大学黄维通设计制作 5 假设含n个记录的序列为 其相应的关键字序列为排序的目的是为了确定一个新的序列对应的关键字满足如下的非递减 或非递增 关系 7 1 2序的定义 清华大学黄维通设计制作 6 交换法 7 1 3排序的方法 每次只看相邻的两张牌 若不符合顺序则交换 多次交换直到符合要求 先把牌都抓到手里 先选最大 小的一张放到一边 然后在剩下的里面选最大 小的 依此类推 直到最后 抓牌过程每摸到一张 将它插入合适的位置 直到最后 选择法 插入法 以扑克排序为例 清华大学黄维通设计制作 7 7 2冒泡排序法的设计及其实现 清华大学黄维通设计制作 8 冒泡排序 BubbleSort 算法是最简单 最常见的也是效率最差的算法 适用于小数据量的排序 7 2 1冒泡算法设计思想 清华大学黄维通设计制作 9 例 有一组序列 顺序为5 4 3 2 1 用冒泡算法 对此序列按从小到大顺序排列 include includevoidPrintArray int a intn 输出排序每一步结果的函数 inti for i 0 i n i 输出元素printf 4d a i printf n 7 2 2冒泡算法的实现 清华大学黄维通设计制作 10 voidBubbleSort inta intn 排序函数 inti j tmp tmp存储交换数据intflag 标志变量 如果为0 说明不再交换顺序 排序结束intcount 0 计录交换次数printf initialsorting PrintArray a n 输出排序前的序列for i 0 i n 1 i 开始排序 flag 0 标志初值为0 清华大学黄维通设计制作 11 for j 0 ja j 1 tmp a j a j a j 1 a j 1 tmp flag 1 若发生交换 flag变为1 count 记录已经发生的排序次数printf after dsorting count PrintArray a n 第count次的排序结果if flag 0 每排序一次 flag都清0 若交换不再发生 则排序完成return 清华大学黄维通设计制作 12 voidmain 主函数 int a n 5 i a int malloc n sizeof int 为5个待排序整型数开辟存储空间for i 0 i n i scanf d 排序结束 释放存储空间 initialsorting 54321after1sorting 43215after2sorting 32145after3sorting 21345after4sorting 12345 13 冒泡法实现字符串的降序排列 include includevoidmain char p str 8 Beijing Shanghai Tianjin Changchun Shenyang Baoding Hefei Shenzhen temp inti j for i 0 i 8 i 冒泡法排序for j 0 j 7 i j if strlen p str j strlen p str j 1 temp p str j p str j p str j 1 p str j 1 temp 14 elseif strlen p str j strlen p str j 1 if strcmp p str j p str j 1 1 temp p str j p str j p str j 1 p str j 1 temp else for i 0 i 8 i 输出字符串printf s n p str i printf n 清华大学黄维通设计制作 15 7 3选择排序法的设计及其实现 清华大学黄维通设计制作 16 选择排序法的过程很简单 首次扫描的时候选择出最小的一个元素 将它和第一个位置 也称为当前的基准元素位置 的元素交换 然后从剩下的n 1个元素中选择次小的元素 再和第二个位置 变成当前新的基准元素位置了 的元素交换 不断重复这一过程 直到最后一次从最后两个元素里面选择比较小的一个 然后交换 7 3 1选择排序法设计思想 清华大学黄维通设计制作 17 例 选择排序法 7 3 2选择排序法设计的实现 18 voidSelectSort inta intn inti j tmp tmp为中间变量intmin 保存序列中的最小值printf initialsorting PrintArray a n 输出当前结果for i 0 i n 1 i 开始排序 min i 基准元素的下标for j i j n j 其他元素与该下标下的元素比较 if a j a min 若小于基准元素 则交换min j 把要交换的位置告诉minif min i 若min的值非原来的i 则要交换 tmp a i 与基准元素进行位置交换a i a min a min tmp printf after dsorting i 1 PrintArray a n 清华大学黄维通设计制作 19 7 4插入排序法的设计及其实现 清华大学黄维通设计制作 20 插入排序法的思想是 当插入第i个元素的时候 前面i 1个元素已经排好了 这时只需要用第i个的关键码从最后开始与其他的进行比较 找到合适的位置 将后面的对象依次后移 然后将新的对象插入 7 4 1插入排序法设计思想 21 例 用插入排序法实现排序voidInsertSort int a intn inti j tmp if n 0 printf after dsorting n PrintArray a n elseif n 1 if a 1 a 0 tmp a 1 a 1 a 0 a 0 tmp printf after dsorting n PrintArray a n 7 4 2插入排序法的实现 22 else tmp a n if tmp a 0 for j n 1 j j a j a j 1 其余元素后移a 0 tmp 就插在a 0 位置 elseif a n 1 tmp a n tmp else for i 0 i n i if a i tmp 输出当前结果 清华大学黄维通设计制作 23 voidPrintArray int a intn 输出排序每一步结果的函数 inti for i 0 i n i 输出元素printf 4d a i printf n 清华大学黄维通设计制作 24 voidmain 主函数 int a n 10 i a int malloc n sizeof int 为10个待排序整型数开辟存储空间for i 0 i n i scanf d 排序结束 释放存储空间 清华大学黄维通设计制作 25 前面介绍的几种排序算法都有一个共同的缺点 当序列中元素比较多的时候 排序时间会非常长 甚至长得不可忍受 清华大学黄维通设计制作 26 7 5SHELL排序法的设计及其实现 27 SHELL排序法也称为 缩小增量排序 其基本思想是 设有n个元素的序列 首先取一个整数gap n作为间隔 将全部元素分为gap个子序列 所有距离为gap的元素属于同一个子序列 在每一个子序列中分别采取直接插入算法 然后缩小gap 直到gap 1 将所有对象放到同一个序列再排一次为止 7 5 1SHELL排序法设计思想 28 由于开始的时候gap取值较大 每个子序列中的对象较少 排序速度比较快 待到排序后期 gap取值逐渐缩小 子序列中的元素逐渐变多 但是由于前面排序的基础 大多数对象已经基本有序 在加上直接插入法的合理性 所以排序速度可以一定程度上有所提高 29 对于上述序列 若用SHELL排序法使其按英文字母顺序排列 如果第一次gap取为n 2 那么这里共有6个元素 则gap等于3 相隔三个元素分组形成子序列进行排序 第二遍在上一个gap值的基础上除2取整 结果为2 那么 相隔两个元素进行分组形成子序列进行排序 然后再在上一次的基础上求gap的值 为1 则相邻的元素作为子序列进行排序 最后获得结果 30 关于gap的取法有很多种 最初SHELL认为gap n 2 然后依次取gap gap 2 后来Knuth提出gap gap 3 1 还有人提出都取奇数比较好 总之 不同的研究者提出了不同得算法 但无论哪一种提法都没有得到证明 31 例 对既有序列 10 9 8 7 6 5 4 3 2 1 用SHELL排序法从小到大排序voidshell inta intn intgap i j temp PrintArray a n 原始序列for gap n 2 gap 0 gap 2 printf gap d n gap for i gap i 0 j gap if a j a j gap temp a j a j a j gap a j gap temp PrintArray a n 输出结果 7 5 2SHELL排序法的实现 32 include stdio h include stdlib h voidPrintArray int a intn 输出排序每一步结果的函数 inti for i 0 i n i 输出元素printf 4d a i printf n voidmain 主函数 int a n 10 i a int malloc n sizeof int 为待排序整型数开辟存储空间for i 0 i n i scanf d 排序结束 释放存储空间 清华大学黄维通设计制作 33 7 6快速排序 34 设要排序的数组是a N 首先任意选取一个数据 通常选用第一个数据 作为关键数据 key 然后将所有比它小的数都放到它前面 所有比它大的数都放到它后面 这个过程称为一趟快速排序 7 6 1快速排序法的设计与实现 35 一趟快速排序的算法是 1 设置两个变量i j 排序开始的时候 i 0 j N 1 2 以第一个数组元素作为关键数据 赋值给key 即key a 0 3 从j开始向前搜索 即由后开始向前搜索 j j 1 找到第一个小于key的值a j 并与a i 交换 4 从i开始向后搜索 即由前开始向后搜索 i i 1 找到第一个大于key的a i 与a j 交换 5 重复第3 4步骤 直到i j 3 4步是在程序中没找到时候j j 1 i i 1 找到并交换的时候i j指针位置不变 另外当i j这过程一定正好是i 或j 完成的最后循环结束 36 例如 待排序的数组a的值分别是 49386597761327 初始关键数据取key 49 注意key在程序中不变 其他数据总是跟key进行比较 无论在什么位置 最后的目的就是把key放在中间 小的放前面 大的放后面 上述序列按照算法的第三步从j开始向前搜索进行第一次交换后 27386597761349 按照算法的第四步从前面开始找 key的值 65 49 两者交换 此时i 3 进行第二次交换后 27384997761365 37 按照算法的第五步将又一次执行算法的第三步从后开始向前找 进行第三次交换后 27381397764965 依算法的第四步从前面开始找大于key的值并进行两者交换 此时j 4 进行第四次交换后 27381349769765此时再执行第三步的时候就发现i j 从而结束一趟快速排序 那么经过一趟快速排序之后的结果是 27381349769765 即所以大于49的数全部在49的后面 所以小于49的数全部在49的前面 38 快速排序就是递归调用上述过程 在以49为中点分割这个数据序列 分别对前面一部分和后面一部分进行类似的快速排序 从而完成全部数据序列的快速排序 最后把此数据序列变成一个有序的序列 初始状态 49386597761327 进行一次快速排序之后划分为 273813 49 769765 分别对前后两部分进行快速排序 273813 经第三步和第四步交换后变成 132738 769765 经第三步和第四步交换后变成 657697 完成排序 39 include stdio h intpartions inta intlow inthigh intkey a low p a low 就是a 0 while low key high p a low a low a high a high p while low high 40 voidqsort inta intlow inthigh inti k if low high k partions a low high for i 0 i 11 printf 3d a i i printf n qsort a low k 1 qsort a k 1 high voidmain inti a 11 11 0 12 5 6 13 8 9 14 7 10 for i 0 i 11 printf 3d a i i printf n qsort a 0 10 for i 0 i 11 printf 3d a i i printf n 41 42 下面几种典型的情况可以供参考 对于元素关键码为数值对象的情况 当关键码分布比较均匀的时候 通过简单的算术运算得到关键码的中值即可 对于元素关键码分布不均匀的情况 会出现在某些值附近相对比较集中的情况 这时可能随机选取基准会更好一些 还有一种常用的有效的方法是 从序列中随机选取三个元素 选其中关键码为中值的那个作为基准 清华大学黄维通设计制作 43 归并排序 归并排序法是将两个 或两个以上 有序表合并成一个新的有序表 即把待排序序列分为若干个子序列 每个子序列是有序的 然后再把有序子序列合并为整体有序序列 清华大学黄维通设计制作 44 查找是数据处理中最常见的一种运算 所谓查找就是在数据集合中寻找满足某种条件的对象 7 7查找概述 顺序查找 折半查找 清华大学黄维通设计制作 45 7 8顺序查找及其应用 清华大学黄维通设计制作 46 顺序查找算法的思想很简单 就是在有序集合中从头按照指定的关键码来查找 直到找到符合要求的元素或者没有找到符合要求的元素 7 8 1顺序查找算法的设计思想 47 例 在给定的序列 1 3 5 7 9 11 13 15 中查找指定的数据 本例给定指定序列 在此序列中查找1 4 9 10这4个数据所在的位置 由于我们用数组存储指定的序列 那么 查找的数据所在的位置也是相对于数组下标的位置 7 8 2顺序查找算法的实现 48 includeintSearch inta intn intkey inti for i 0 i n i 进行顺序查找if a i key 逐一进行数据匹配returni 返回匹配数据的数组下标return 1 如果没有找到 返回 1 49 voidmain inta 1 3 5 7 9 11 13 15 intb 1 4 9 10 需查找的序列intna sizeof a sizeof int 指定序列元素个数intnb sizeof b sizeof int 需查找的元素个数inti pos for i 0 i 0 若