《排序算法及应用》PPT课件.ppt

第六讲排序算法及应用 排序算法的种类 1 选择排序2 冒泡排序3 插入排序4 快速排序5 堆排序 1 选择排序算法基本思想 对待排序的序列进行n 1遍处理 第1遍处理是从a 1 a 2 a n 中选择最小的放在a 1 位置 第2遍处理是从a 2 a 3 a n 中选择最小的放在a 2 位置 第I遍处理是将a i a i 1 a n 中最小的数与a i 交换位置 这样经过第i遍处理后 a i 是所有的中的第i小 即前i个数就已经排好序了 N 1遍处理后 剩下的最后一个一定是最大的 不需要再处理了 a 待排序的数组 从小到大排序简单选择排序 fori 1ton 1do 从第一个元素开始 进行n 1遍处理 forj i 1tondo 第i遍处理 Ifa i a j then 交换a i 和a j begint a i a i a j a j t end 算法的改进 减少交换次数 fori 1ton 1dobegink i forj i 1tondoifa j ithenbegint a k a k a i a i t end end 排序的关键字 2030101516138 2 冒泡排序算法 基本思想 从小到大排序 将待排序的数据看作竖派排的一列 气泡 小的数据比较轻 从而要上浮 共进行n 1遍处理 每一遍处理 就是从底向上检查序列 如果相邻的两个数据顺序不对 即轻 小 的在下面 就交换他们的位置 第一遍处理完后 最轻 的就浮到上面 第二遍处理完后 次轻 的就浮到上面 共需要n 1遍处理即完成排序 简单的冒泡排序fori 1ton 1doforj ndowntoi 1doifa j a j 1 thenbegint a j a j a j 1 a j 1 t end 判断标志 flag true已有序 改进后的冒泡排序fori 1ton 1dobeginflag true forj ndowntoi 1doifa j a j 1 thenbegint a j a j a j 1 a j 1 t flag false end ifflag truethenbreak 某一轮没有交换 说明都已经有序了end 算法的改进 关键字203040506010 测定时间的方法 通过访问MemL Seg0040 006C 来获取当前时间 它返回的是当日零时到现在所经过的时间 单位约为55毫秒 约1 18 2秒 测定执行的时间Starttime endtime longint Starttime MemL Seg0040 006C endtime MemL Seg0040 006C Writeln endtime starttime 18 2 0 2 语句组2运行的时间或 Writeln MemL Seg0040 006C starttime 18 2 0 2 StartTime MemL Seg0040 006C fori 1ton 1doforj ndowntoi 1doifa j a j 1 thenbegint a j a j a j 1 a j 1 t end writeln MemL Seg0040 006c StartTime 18 2 0 2 3 插入排序算法 基本思想 经过i 1遍处理后 a 1 a 2 a i 1 已排好序 第i遍处理是将元素a i 插入到a 1 a 2 a i 1 的适当的位置 从而使得a 1 a 2 a i 1 a i 又是排好的序列 a array 0 n ofinteger a 0 记录当前待插元a i fori 2tondobegina 0 a i 取第i个元素作为待插入元素 j i 1 从已排好的最后一个a i 1 开始比较 whilea 0 a j 时循环结束 a j 1 a 0 在第j 1个位置插入a i 元素 end 4 快速排序算法 基本思想 把待排序的n个元素放到一个中的任一个元素数组中 先取数组中的某一个元素作为一个基准元素 把这个元素放到数组中合适的位置 同时对其他元素进行调整 使得在这个基准元素的右边的所有元素都比这个基准元素大 而基准元素左边的元素都比它小 也就是说 这个基准元素当前所在的位置就是排序后的最终位置 然后再对基准元素的前后两个区间分别进行快速排序 直到每个区间为空后者只有一个元素时 整个快速排序结束 方法一 取数组中的第一个元素作为基准元素 把待排序的数组按照基准元素分为左右两部分的过程称为快速排序的一次划分 一趟排序 待排数组 a 1 a n 一次划分的过程 设I j两个指针 开始时 i 1 j n x a i 基准元素 如果a j x那么j j 1 直到找到a j x 然后 a j a i procedureqsort s t integer s 待排序数组首元素下标 t 末尾元素下标 vari j integer x integer begini s j t x a s x 首元素为基准元素 whilei x and j i dodec j 从未部找比x小的元素a j ifj ithenbegina i a j inc i end 把a j 放在i处 j处空着 while a i x and i j doinc i 继续从前边找比x大元素a i ifi jthenbegina j a i dec j end 把a i 移动到j位置处 i处空着 end a i x 基准元素x放到合适的i位置 ifs i 1 thenqsort s i 1 对基准元素x的左区间再进行快速排序 if i 1 tthenqsort i 1 t 对基准元素x的右区间再进行快速排序 end 主程序的调用 qsort 1 n 方法二 取中间元素为基准元素的算法 procedureqsort l r integer vari j mid integer temp integer begini l j r mid a l r div2 将当前序列在中间位置的数定义为中间数 repeatwhilea i middodec j 在右半部分寻找比中间数小的数 ifij ifl jthenqsort l j 若未到两个数的边界 则递归搜索左右区间 ifi rthenqsort i r end sort 排序算法的应用 1 排队接水有n个人排队在一个水笼头前接水 每个人的接水时间互不相等 找出一种n个人排队接水的顺序 使他们平均等待的时间最短 输入 第一行 n 100 第二行 依次为n个人的接水时间 输出 第一行 所有人的平均等待时间 第二行 接水的顺序 样例 输入 526138输出 8 4031425 varnum t array 1 100 ofinteger n i j sum tem integer beginreadln n fori 1tondoread t i fori 1tondonum i i fori 1ton 1doforj i 1tondoift i t j thenbegintem t i t i t j t j tem tem num i num i num j num j tem end sum 0 fori 1tondosum sum n 1 i t i writeln sum n 0 2 fori 1ton 1dowrite num i writeln num n end 2 主油管的最优位置Olay教授正在为一家石油公司咨询 该公司正在设计建造一条由东向西的管道 该管道要穿过一个有n口井的油田 从每口井中都有一条喷油管沿最短路径与主管道直接相连 或南或北 给定各个井的X和Y坐标 Olay教授如何才能选择主管道的最优位置 即使得个喷管长度总和最小的位置 输入 3233754输出 4 3 成绩排名 问题描述 根据期末考试的成绩单信息 把所有的学生按总分从高到低的顺序输出 输入 第一行 学生的个数n n 100 以下n行 每行包含一个学生的信息 依次是 学号 1 n 姓名 语文成绩 数学成绩 他们中间有且仅有一个空格隔开 输入信息中没有多余的空格 姓名全是字母 长度不大于200 各科成绩不超过100 输出 N行 每行包含一个学生的信息 学号 姓名 总分 中间用一个空格隔开 不能有多余的空格 总分相同的学生 学号大的在前 样例输入 43abc40502gd50401wr60604dsd1020 样例输出 1wr1203abc902gd904dsd30 4 区间合并 问题描述 从键盘上任意输入n个区间 然后按从小到大的顺序依次输出n个区间的并集 输入 第一行 区间个数n 1000 以下n行 每行两个整数a b 1000000000 a b 1000000000 相应区间的坐标 中间一个空格 输出 n个区间的并集 n行 每行一个区间 坐标轴的左边的区间先输出 样例输入 3143578 样例输出 1578 区间的合并 注意 1 区间个数n的范围 1000 2 区间的数据类型和范围 整数类型 109 109 算法一 离散化 思路 设f i 0 1 初始值全部为0 每读入一个区间abFori 1tonForj atobdof j 1 最后输出f j 1的区间 时间复杂度 1012 只能过部分数据 算法二 直接合并 1 按每个区间的左端的的值升序排列 由于N 1000 任意排序算法 注意数据结构的设置 记录类型 二维数组 a array 1 1000 1 2 oflongint a array 1 1000 ofarray 1 2 oflongint 2 合并过程 输出第一个区间的左端点坐标 最小的 依次处理后面的n 1的区间 Ifa I 2 tailTail不变 If a I 1 tail and tail a I 2 Tail a I 2 Iftail a I 1 Writeln tail Write a I 1 Tail a I 2 5 修理牛棚在一个暴风雨的夜晚 农民约翰的牛棚的屋顶 门被吹飞了 好在许多牛正在度假 所以牛棚没有住满 有些牛棚里有牛 有些没有 所有的牛棚有相同的宽度 并且一个紧挨着另一个被排成一行 自门遗失以后 农民约翰很快在牛棚门口之前竖立起新的木板 他的新木材供应者将会供应他任何他想要的长度 但是供应者只能提供有限数目的木板 农民约翰想将他购买的木板总长度减到最少 给出可能买到的木板最大的数目M 1 M 50 牛棚的总数S 1 S 200 牛棚里牛的数目C 1 C S 牛所在的牛棚的编号numbe