常见三种排序方法ppt课件.ppt

数组操作 1 选择排序法 2 冒泡排序法 3 比较排序法 1 顺序查找法 2 折半查找法 1 数组元素插入 2 数组元素删除 1 选择排序 第17 26套的填空题 简单选择排序 从1到n选出关键值最 大 小的记录 交换到第一个位置上 然后从2到n选出键值最 大 小的记录 交换到第二个位置上 5471582931547158293154715829315471582931 i 0 初态 数组下标01234 k i 交换 判断a j a k 用选择法对数组inta 5 54 71 58 29 31 进行升序排序 k j 2971585431 2971585431 2971585431 2971585431 k i 交换 2931585471 判断a j a k k j k j k j 判断a j a k 选择排序法 由小到大排序 选择法 递增 基本思想 1 从n个数的序列中选出最小的数 与第1个数交换位置 2 除第1个数外 其余n 1个数再按 1 的方法选出次小的数 与第2个数交换位置 3 重复 1 n 1遍 最后构成递增序列 实现方法 采用双重循环 循环的嵌套 外循环为i 控制排序趟数内循环为j 第i趟排序过程中的下标变量 选择 排序法的结构形式 for i 0 ia j k j if k i t a i a i a k a k t include include stdlib h voidmain constintN 10 inti j k t a N for i 0 ia j k j if k i t a k a k a i a i t for i 0 i N i printf 5d a i printf n 第二种 冒泡法 由小到大排序 基本思想 1 从第一个元素开始 对数组中两两相邻的元素比较 将值较小的元素放在前面 值较大的元素放在后面 一轮比较完毕 最大的数存放在a N 1 中 2 然后对a 0 到a N 2 的N 1个数进行同 1 的操作 次最大数放入a N 2 元素内 完成第二趟排序 依次类推 进行N 1趟排序后 所有数均有序 实现方法 采用双重循环 循环的嵌套 2 冒泡排序 交换排序 俩俩比较待排序记录的键值 若逆序 则交换 直到全部满足为止 交换排序 冒泡 排序法特点 逐个对数组中每相邻二数进行比较 若条件满足 则互相交换 否则保持原位置不变 千万要注意 若有n个数据 需要进行i n 1轮比较 每轮中比较的次数为j n i 1次 排序过程 设数据存于A数组中 n个数据 按递增次序排序 A 0 与A 1 比较A 0 A 1 不换 否则对调A 1 与A 2 比较A 1 A 2 不换 否则对调 A n 2 与A n 1 比较A n 2 A n 1 不换 否则对调 冒泡法排序 用冒泡法对10个数排序 由小到大 482759 248579 245879 245789 245789 245789 冒泡排序的结构形式 递增 for i 0 ia j 1 t a j a j a j 1 a j 1 t for i 1 ia j 1 t a j a j a j 1 a j 1 t 关键代码 for i 0 ia j 1 t a j a j a j 1 a j 1 t include defineN6voidmain inti j t a N printf inputNnumbers n for i 0 ia j 1 t a j a j a j 1 a j 1 t for i 0 i N i printf 5d a i printf n 冒泡程序 第三种 比较排序 上机19 52套编程题 for i 0 ia j t a i a i a j a j t 注意a i 与a j 比较 补充知识一 查找 查找的方法很多 如 顺序查找 二分法查找等等 1 顺序查找 最简单的查找方法 基本思想是利用循环顺序扫描整个数组 依次将每个元素与待查找值比较 直至找到或找不到 对于无序数组 顺序查找是唯一可行的办法对大批量数据用顺序查找占机器时间较多 intSearch longa intn longx inti for i 0 i n i if a i x return i return 1 2 二分法查找 折半查找 二分法查找的条件 必须是有序数列 即数组中的各元素已按数值大小按递增或递减次序排列 查找过程 1 将数列对分 找出中间数据 2 用此数据与要查的数据比较 3 数值相等则结束查询 否则确定要查的数据所在区间 逐步缩小查找范围 每次将数列区间缩小一半 直到找到或找不到为止 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 08 14 23 37 46 55 68 79 91 折半查找 二分法查找 08 14 23 37 46 55 68 79 91 下标012345678 折半查找 1 5 6 9 11 17 25 34 38 41 下界low 上界up 中值mid 共有10个已排好序的数据 查找9 intBinSearch longa intn longx intlow high mid low 0 high n 1 while lowa mid low mid 1 elseif x a mid high mid 1 else return mid return 1 折半查找程序 includemain intup 9 low 0 mid found 0 find inta 10 1 5 6 9 11 17 25 34 38 41 scanf d 补充知识二 数组元素的插入 删除 1 插入数据在有序数组中插入数据后 数组仍然有序 要求数组有足够的空间 前提 被操作数组已经是有序数组 操作前后不改变数组的有序性 插入过程 1 确定数据插入位置 2 从最后一个元素开始逐个后移 直到将第i个位置腾出 a i 1 a i 3 将数据插入到指定下标元素位置中 插入运算 ai 1 a1 a0 alength ai 1 ai x x 2 删除数据在有序的数组中删除数据后 数组仍然有序 删除过程 1 确定数据删除位置i 2 从第i 1个位置开始逐个向前移动原数组元素 a i a i 1 下面介绍引用一维数组元素的三种方式 1 下标方式形式 数组名 下标 如a i 2 地址方式形式 地址 如 a i 等价a i 3 指针方式形式 指针变量名如 inta 10 p p 一维数组与指针 1数组就是连续存放的若干元素的集合 2数组名就是指向数组第一个元素的首地址 指