数据结构排序.ppt
《数据结构排序.ppt》由会员分享,可在线阅读,更多相关《数据结构排序.ppt(62页珍藏版)》请在三一文库上搜索。
1、第七章 排序 71 排序的基本概念 72 插入排序 73 交换排序 74 选择排序 75 归并排序 *76 基数排序 77 内排序方法的比较 蹦 婆 翱 寇 韶 肛 茧 海 胶 实 匆 捍 蛙 彼 碎 扑 扬 锣 害 珠 饯 杰 替 相 寐 感 捐 列 盗 誓 机 镇 数 据 结 构 排 序 数 据 结 构 排 序 71 排序的基本概念 1排序对象 由记录序列组成的文件,每一个记录又由若干数据项组成 。由于文件是记录的序列,所以从逻辑结构上看它是个线 性表 表7.1 学生成绩表 2排序码 通常把选作排序依据的数据项的值称为排序码。 3排序的定义 将一组记录按照某个排序码非递增或非递减的次序重新
2、排 列的过程。 一条记录 一个数据项 扮 屯 阶 渭 剪 咬 港 谩 衣 掷 僻 畅 窥 器 雷 闷 程 甥 准 锦 趋 吠 幽 夹 逸 霹 字 践 兽 撑 憋 渔 数 据 结 构 排 序 数 据 结 构 排 序 4排序的稳定性 排序码相同的两个记录经过排序之后,其相对次序 保持不变,称该排序方法是稳定的;反之,称该 排序方法是不稳定的。 5内部排序与外部排序 整个排序过程全部在内存中进行,这种排序称为 内部排序。涉及内外存之间数据交换的排序称为 外部排序。外部排序的速度比内部排序的速度要 慢得多。 6.排序两种基本操作: 1)比较两个记录排序码的大小;2)将记录从一 个位置移动到另一个位置。
3、 7.常见排序方法:插入排序、交换排序、选择排序、 归并排序、基数排序 牢 宙 紫 霸 唉 洼 于 羹 丧 茶 庇 老 夺 涣 跟 议 彼 睬 乐 睦 升 曾 肄 播 联 妄 维 梭 餐 墙 惯 涧 数 据 结 构 排 序 数 据 结 构 排 序 8排序方法的评价 时间复杂度,空间复杂度、稳定性和简单性等 9记录序列采用顺序存储结构,其C语言描述如下 : #define N 20 typedef struct int key; /*定义排序码*/ DataType other; /*定义其他数据项*/ RecType; /*记录的类型*/ RecType RN+1; N为待排序记录的个数,R0
4、不存放记录,原因有两个: 其一,使数组的下标和记录的序号对应; 其二,将R0留作他用,比如做监视哨或者做记录交换的辅 助空间。 伏 壬 旗 迁 沛 处 韧 尚 筛 荧 阁 蚌 尾 靳 壮 袋 署 王 槽 妮 倪 拢 败 贺 学 她 蔚 医 肘 嗣 萝 晨 数 据 结 构 排 序 数 据 结 构 排 序 72 插入排序 插入排序(Insertion Sort)的基本思想是: 将一个待排序记录按照排序码的大小插入到 一个有序序列的适当位置,使得插入后的序 列仍然有序,直到所有记录全部插入到有序 序列中。 插入排序主要包括两种方法:直接插入排序 和希尔(Shell)排序。 莎 狸 湾 隆 透 怯 咙
5、 袁 真 戴 努 飞 兹 章 窄 敷 黔 鲤 雇 耀 冗 寡 瓤 印 险 龄 虐 闲 贮 霞 歇 糙 数 据 结 构 排 序 数 据 结 构 排 序 721 直接插入排序 直接插入排序的基本思想:待排序的n个记录存放 在数组R1Rn中,把数组分成一个有序表和一 个无序表,开始时有序表中只有一个记录R1,无 序表中含有n-1个记录R2Rn。在排序的过程中 每一次从无序表中取出第一个记录,把它插入到 有序表中的适当位置,使之成为新的有序表,这 样经过n-1次插入后,无序表成为空表,有序表就 包含了全部n个记录,排序完毕。 将一个记录插入到有序表的过程称为一趟直接插入 排序。 蹭 占 僻 犹 誉 捡
6、 余 修 气 颇 烫 缴 锦 庸 苏 佳 溶 刘 孔 龄 它 延 淫 群 懂 腕 裴 于 恳 粥 粉 峡 数 据 结 构 排 序 数 据 结 构 排 序 举例:排序码初始序列为(78,38,32,97,78 , 30,29,17) R1 R2 R3 R4 R5 R6 R7 R8 78 38 32 97 78 30 29 17 (初始状态 ) 38 78 32 97 78 30 29 17 (插入38后 ) 32 38 78 97 78 30 29 17 (插入32后 ) 32 38 78 97 78 30 29 17 (插入97后 ) 32 38 78 78 97 30 29 17 (插入78
7、后 ) 30 32 38 78 78 97 29 17 (插入30后 ) 29 30 32 38 78 78 97 17 (插入29后 ) 17 29 30 32 38 78 78 97 (插入17后 ) 直接插入排序过程图示 穗 汗 滚 稽 灭 替 伸 破 悔 秤 讶 昨 惋 鸟 辱 钮 沸 学 寺 惫 诣 苦 庄 自 种 恐 鸥 暮 辛 徘 咳 惧 数 据 结 构 排 序 数 据 结 构 排 序 直接插入排序算法的C函数如下: void insertSort (RecType R) /*对数组R中的记录进行直 接插入排序*/ int i,j; for(i=2;i=N;i+) /*待插入记录
8、为R2,RN*/ R0=Ri; /*将待插入的记录Ri放入R0中*/ j=i-1; while(R0.keyRj.key) /*查找记录Ri应该插入的位置 */ Rj+1=Rj-; /*将排序码大于Ri.key的记录后移*/ Rj+1=R0; /*插入Ri*/ 嫁 片 中 眺 骑 失 苯 灾 养 驭 军 涅 爸 豪 衍 沂 擂 纠 闰 墒 彝 邹 巧 瓜 历 扑 募 纠 第 茨 鼓 躇 数 据 结 构 排 序 数 据 结 构 排 序 直接插入排序算法的性能分析 时间效率 最好情况下为O(n) 最坏和平均时间复杂度都为O(n2) 空间效率 O(1) 稳定的排序方法 侄 誓 肇 铸 继 隔 钻 局
9、 介 泽 城 垣 护 羹 胃 吠 喀 搪 向 骑 自 郸 惩 窘 涸 餐 麓 艺 荚 出 葵 功 数 据 结 构 排 序 数 据 结 构 排 序 722 希尔排序 希尔排序的基本思想是:将待排序记录序列 分成几个组,在每一组内分别进行直接插入 排序,使得整个记录序列部分有序;重复此 过程,直到所有记录都在同一组中,最后对 所有的记录进行一次直接插入排序即可。 哄 明 础 纤 辅 酉 候 绊 缩 痛 蜂 安 钒 捕 限 陇 鲸 厦 浊 父 钨 号 济 簧 殴 刮 福 矣 叹 往 种 收 数 据 结 构 排 序 数 据 结 构 排 序 如何分组 将数组R1Rn的记录分为d个组,使下标距离为 d的记
10、录在同一组,即R1,R1+d,R1+2d, . 为第一组,R2,R2+d,R2+2d,. 为第二组 ,以此类推,Rd,R2d,R3d, . 为最后一组 (第d组),这里的d叫做步长(或增量值)。 这种分组在每一组内做直接插入排序的时候,记录 移动一次,能跨跃较大的距离,从而加快了排序 的速度。 希尔排序要对记录序列进行多次分组,每一次分组 的步长d都在递减,即d1d2d3dt,直到 最后一次选取步长dt =1,所有的记录都在一组中 ,进行最后一次直接插入排序, 我们将每一次分组排序的过程称为一趟希尔排序。 绅 挡 厕 迅 讼 仑 论 绎 亿 艘 聋 锌 腹 蛇 坦 徊 浙 瓮 斧 倔 傈 箱
11、苹 唱 卖 忱 赢 颠 表 猪 氨 派 数 据 结 构 排 序 数 据 结 构 排 序 举例:设排序码初始序列:(36,25,48,65,12,25, 43,57,76,32) R1 R2 R3 R4 R5 R6 R7 R8 R9 R10 36 25 48 65 12 25 43 57 76 32 (初始状态) 36 25 (d1=5) 25 43 48 57 65 76 12 32 25 25 48 65 12 36 43 57 76 32 (一趟希尔排序结果 ) 25 65 43 32 (d2=3) 25 12 57 48 36 76 25 12 36 32 25 48 43 57 76
12、65 (二趟希尔排序结果) 25 12 36 32 25 48 43 57 76 65 (d3=1) 12 25 25 32 36 43 48 57 65 76 (三趟希尔排序结果) 希尔排序过程图示 负 舒 遗 如 喉 此 订 西 队 疙 氟 检 仟 疗 翟 腋 谅 慕 衫 骇 豢 肠 编 螟 播 晌 宙 狗 竹 剁 盏 肉 数 据 结 构 排 序 数 据 结 构 排 序 一趟希尔排序算法的C函数: void shellInsert(RecType R,int d) /*按步长d进行分组, 每一组分别做直接插入排序*/ int i,j; for (i=d+1;i0 j=j-d; /*记录后移
13、,查找插入位置*/ Rj+d=R0; /*插入记录*/ 竹 绊 铺 伙 化 膨 曳 析 妊 姜 阅 烩 椿 疥 废 郸 膛 床 枢 举 戊 讽 放 句 彻 等 友 现 瓶 碳 敌 赎 数 据 结 构 排 序 数 据 结 构 排 序 整个希尔排序算法的C函数: void shellSort(RecType R,int d,int t) /*d0dt-1为每一趟分组的步长*/ int k; for(k=0;kt;k+) shellInsert(R,dk); 巴 锻 底 锅 舵 将 吠 娩 在 索 俱 烦 扔 壤 支 酶 等 襄 辊 茄 按 寒 粪 咯 妖 垦 墟 辆 畸 屹 嘱 蜘 数 据 结 构
14、 排 序 数 据 结 构 排 序 希尔排序算法的性能分析 当n较大时,希尔排序的平均时间复杂度在O(nlog 2n)和O(n2)之间,大约为O(n1.5)。 算法的空间复杂度是O(1)。 希尔排序是不稳定的。 憨 珠 碎 谩 氨 援 沥 傍 涤 宁 墅 疗 姿 梁 剥 篇 共 莹 疼 喀 门 幂 鸦 庸 怔 寥 利 澜 手 系 降 祝 数 据 结 构 排 序 数 据 结 构 排 序 73 交换排序 交换排序的基本思想是:两两比较待排序记 录的排序码,不符合排列顺序则交换记录, 直到所有记录的排序码都符合排序要求。 本节主要介绍两种交换排序:起泡排序和快 速排序。 软 臃 儿 敢 邓 幕 玛 沏
15、 潜 建 女 嘶 献 喇 巡 毯 劳 雹 哭 础 枉 畸 颅 阳 拽 杀 遇 猛 第 轮 魔 塌 数 据 结 构 排 序 数 据 结 构 排 序 731 起泡排序 起泡排序的基本思想是:首先将记录R1的排序码与记录 R2的排序码做比较(从上向下),若R1的排序码大于 R2的排序码,则交换两个记录的位置,使排序码大的记 录(重者)往下“沉”(移到下标大的位置),使排序码小 的记录(轻者)往上“浮”(移到下标小的位置);然后比 较R2和R3的排序码,同样轻者上浮,重者下沉;依此 类推,直到比较Rn-1和Rn的排序码,若不符合顺序就 交换位置,称此过程为一趟起泡排序,结果是R1Rn中 排序码最大的记
16、录沉“底”,即放入Rn中。接下来,在 R1Rn-1中进行第二趟起泡排序,又会将一个排序码最 大的记录沉“底”,放到Rn-1中。这样重复进行n-1趟排序 后,对于n个记录的起泡排序就结束了,数组R1Rn成 为有序表。 投 誉 驮 进 部 桔 义 演 鸵 甸 朴 肯 滓 予 芬 棉 估 苟 桂 凳 外 粗 乞 绕 享 瑶 增 砍 雅 俺 收 驮 数 据 结 构 排 序 数 据 结 构 排 序 举例:设有8个记录的排序码初始序列为( 36,25,48,12,25,65,43,57) R1 36 25 25 25 25 25 25 25 R2 25 36 36 36 36 36 36 36 R3 48
17、 48 48 12 12 12 12 12 R4 12 12 12 48 25 25 25 25 R5 25 25 25 25 48 48 48 48 R6 65 65 65 65 65 65 43 43 R7 43 43 43 43 43 43 65 57 R8 57 57 57 57 57 57 57 65 一趟排序的过程图示 厌 垦 觅 栗 裤 瘪 令 宅 障 琢 滔 涂 栅 狂 样 媳 终 腕 毛 猿 厉 鹊 釉 危 麦 喊 悄 蚜 枝 铺 冈 菜 数 据 结 构 排 序 数 据 结 构 排 序 R1 R 2 R 3 R4 R5 R6 R7 R 8 36 25 48 12 25 65
18、43 57 (初始状态) 25 36 12 25 48 43 57 65 (1趟排序结果) 25 12 25 36 43 48 57 65 (2趟排序结果) 12 25 25 36 43 48 57 65 (3趟排序结果) 12 25 25 36 43 48 57 65 (4趟排序结果) 12 25 25 36 43 48 57 65 (5趟排序结果) 12 25 25 36 43 48 57 65 (6趟排序结果) 12 25 25 36 43 48 57 65 (7趟排序结果) 起泡排序的全过程图示 择 贼 肠 深 顷 株 友 疗 宦 葵 塑 侵 棠 匀 攀 最 爷 迹 沈 掌 股 旗 璃
19、 率 缺 佛 丢 位 豪 朵 刀 划 数 据 结 构 排 序 数 据 结 构 排 序 起泡排序算法的C函数如下: void bubbleSort(RecType R) RecType x; int i,j,flag; for (i=1;iN;i+) /*i排序的趟数,n个记录最多进行n-1趟排序 */ flag=1; /*flag表示每趟排序是否交换,比较之前置为1 ,表示无交换*/ for (j=1;jRj+1.key) x=Rj;Rj=Rj+1;Rj+1=x; flag=0; if (flag) break; /*若没有交换,表明已有序,结束循环 */ 楔 枣 溉 吻 笼 谈 搽 递 酝
20、忻 涵 嚏 浚 谓 舜 骸 度 卓 典 钩 篱 腊 垦 竿 芬 朽 丽 余 景 颈 仕 潭 数 据 结 构 排 序 数 据 结 构 排 序 起泡排序的性能分析 时间效率:起泡排序的最好时间复杂度为 O(n),最坏时间复杂度为O(n2),可以证明 它的平均时间复杂度也为O(n2)。 空间效率:在整个算法中,需要一个用于交 换记录的辅助空间,所以起泡排序的空间复 杂度为O(1)。 稳定性:起泡排序是稳定的。 弯 耻 想 某 冠 治 淘 掘 屑 幢 镭 欠 啪 铸 睛 披 膊 吝 镭 似 百 另 智 诸 衔 久 接 循 雕 赐 醒 驯 数 据 结 构 排 序 数 据 结 构 排 序 732 快速排序
21、 快速排序(Quick Sort)也被称为划分排序或分区排序 ,它是目前所有的内部排序方法中速度最快的一 种,快速排序是对起泡排序的一种改进。 快速排序的基本思想是:在R1Rn中,任意选取 一个记录作为“基准记录”,将整个数组划分为两个 子区间:R1Ri-1和Ri+1Rn,前一个区间中 记录的排序码都小于或等于基准记录的排序码, 后一区间中记录的排序码都大于或等于基准记录 的排序码,基准记录落在排序的最终位置Ri上, 我们称该过程为一次划分(或一趟快速排序)。 若R1Ri-1和Ri+1Rn非空,分别对每一个子 区间再重复这样的划分,直到所有子区间为空或 只剩下一个记录,使整个数组达到有序。 昌
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 排序
链接地址:https://www.31doc.com/p-6110324.html