数据结构与算法之内排序(ppt 87页).ppt

7内排序 内排序 2 主要内容 内部排序 外部排序稳定 不稳定排序排序算法性能分析内部排序算法 内排序 3 设n个记录的序列为 R1 R2 R3 Rn 其相应的关键字序列为 K1 K2 K3 Kn 此操作过程称为排序 排序 内排序 4 内部排序 指的是待排序记录存放在计算机随机存储器中进行的排序过程 外部排序 指的是待排序记录的数量很大 以致内存一次不能容纳全部记录 在排序过程中尚需对外存进行访问的排序过程 内部排序与外部排序 内排序 5 假设Ki Kj 且排序前序列中Ri领先于Rj 若在排序后的序列中Ri仍领先于Rj 则称排序方法是稳定的 若在排序后的序列中Rj仍领先于Ri 则称排序方法是不稳定的 例 序列3158869 若排序后得3688915 稳定的 若排序后得3688915 不稳定的 稳定排序与不稳定排序 内排序 6 排序的时间复杂性 排序过程主要是对记录的排序码进行比较和记录的移动过程 因此排序的时间复杂性可以算法执行中的数据比较次数及数据移动次数来衡量 当一种排序方法使排序过程在最坏或平均情况下所进行的比较和移动次数越少 则认为该方法的时间复杂性就越好 分析一种排序方法 不仅要分析它的时间复杂性 而且要分析它的空间复杂性 稳定性和简单性等 内排序 7 按照排序过程中所依据的原则的不同可以分类为 插入排序 交换排序 选择排序 归并排序 基数排序 二叉排序树排序 内部排序 内排序 8 思想 利用有序表的插入操作进行排序 有序表的插入 将一个记录插入到已排好序的有序表中 从而得到一个新的有序表 例 序列132738657697 插入49 13273849657697 插入排序 直接插入排序 内排序 9 例 序列49386597761327 初始 S 49 3849 初始 令第1个元素作为初始有序表 依次插入第2 3 k个元素构造新的有序表 直至最后一个元素 直接插入排序算法主要应用比较和移动两种操作 直接插入排序算法描述 内排序 10 voidinsertsort ElemTypeR intn 待排序元素用一个数组R表示 数组有n个元素 for inti 1 i 0 内排序 11 直接插入排序的效率分析 从空间来看 它只需要一个元素的辅助空间 用于元素的位置交换 从时间分析 首先外层循环要进行n 1次插入 每次插入最少比较一次 正序 移动两次 最多比较i次 移动i 2次 逆序 i 1 2 n 1 Cmin n 1Mmin 2 n 1 Cmax 1 2 n 1 n2 n 2Mmax 3 4 n 1 n2 3n 4 2Cave n2 n 2 4Mave n2 5n 6 4因此 直接插入排序的时间复杂度为O n2 直接插入算法的元素移动是顺序的 该方法是稳定的 内排序 12 插入排序 平均情况复杂度对每个i值 考虑平均情况下需要多少次比较 为简化分析 假设所有的值是不相同的 对一个i和临时变量x x有i 1个位置可能会去 012 i 1x A i 比较次数和插入位置的关系 i 6A 0 A 1 A 2 A 3 A 4 A 5 x A 6 内排序 13 插入排序 平均情况复杂度在对序列没有其它任何信息的条件下 x到任何一个位置的概率都是1 i 1 这样 对一个特定的值i 需要的平均比较次数为 把所有n 1次插入累加起来 有 内排序 14 由于直接插入排序算法利用了有序表的插入操作 故顺序查找操作可以替换为折半 二分法 查找操作 例 序列49386597761327 设已形成有序表 3849657697 13 插入元素13 折半插入排序 012345 97 76 65 49 38 13 内排序 15 算法 voidBinaryInsertSort ElemTypeR intn for inti 1 i left j R j 1 R j 元素后移空出插入位R left temp 内排序 16 折半插入效率分析 二分插入算法与直接插入算法相比 需要辅助空间与直接插入排序基本一致 时间上 前者的比较次数比直接插入查找的最坏情况好 最好的情况坏 两种方法的元素的移动次数相同 因此二分插入排序的时间复杂度仍为O n2 二分插入算法与直接插入算法的元素移动一样是顺序的 因此该方法也是稳定的 内排序 17 分析直接插入排序 1 若待排序记录序列按关键字基本有序 则排序效率可大大提高 2 待排序记录总数越少 排序效率越高 希尔 shell 排序 内排序 18 思想 先将待排序记录序列分割成为若干子序列分别进行直接插入排序 待整个序列中的记录基本有序后 再全体进行一次直接插入排序 例 序列493865977613274855419 第一趟排序 131949 2738 4865 5597 476 内排序 19 第二趟排序 13385576 4274965 194897 第三趟排序 413192738484955657697 内排序 20 希尔排序的排序过程 01234567891011 01234567891011 内排序 21 希尔排序的算法templatevoidShellSort TVector intarrSize Ttemp intgap arrSize 2 gap是子序列间隔while gap 0 循环 直到gap为零for inti gap i gap j gap if temp Vector j gap Vector j Vector j gap elsebreak Vector j temp gap int gap 2 内排序 22 希尔排序效率分析 希尔排序的时间复杂性在O nlog2n 和O n2 之间 大致为O n1 3 Flash动画演示 希尔排序是不稳定的排序算法 内排序 23 思想 通过不断比较相邻元素大小 进行交换来实现排序 首先将第一个元素与第二个元素比较大小 若为逆序 则交换 然后比较第二个元素与第三个元素的大小 若为逆序 则交换 直至比较第n 1个元素与第n个元素的大小 若为逆序 则交换 第一趟排序 结果 关键字最大的记录被交换至最后一个元素位置上 交换排序 冒泡排序 内排序 24 交换排序 冒泡排序 优点 每趟结束时 不仅能挤出一个最大值到最后面位置 或者最小值到最前面位置 还能同时部分理顺其他元素 一旦下趟没有交换发生 还可以提前结束排序 内排序 25 例 序列4938761327 38491327 初始 第一趟排序后 最大值 次大值 第二趟排序后 381327 1327 第三趟排序后 第四趟排序后 内排序 26 冒泡排序的算法实现 voidBubblesort ElemTypeR intn intflag 1 当flag为0则停止排序for inti 1 i i j if R j R j 1 发生逆序ElemTypet R j R j R j 1 R j 1 t flag 1 交换 并标记发生了交换if flag 0 return 内排序 27 冒泡排序的效率分析最好情况 若待排序的元素为正序 则只需进行一趟排序 比较次数为 n 1 次 移动元素次数为0 最坏情形 初始排列逆序 算法要执行n 1趟排序 第i趟 1 i n 做了n i次关键码比较 执行了3 n i 次数据元素交换 此时的比较总次数和记录移动次数为 因此冒泡排序算法的时间复杂度为O n2 由于其中的元素移动较多 所以属于内排序中速度较慢的一种 因为冒泡排序算法只进行元素间的顺序移动 所以是一个稳定的算法 内排序 28 冒泡排序的一种改进算法 思想 以首记录作为轴记录 从前 后双向扫描序列 通过交换 实现大值记录后移 小值记录前移 最终将轴记录安置在一个适当的位置 小值记录在前 大值记录在后 轴记录将原序列分割成两部分 依次对前后两部分重新设定轴记录 继而分别再进行快速排序 直至整个序列有序 交换排序 快速排序 内排序 29 快排序 QuickSort 快排序 算法思想取序列的一个元素作为轴 利用这个轴把序列分成三段 左段 中段 轴 和右段 使左段中各元素都小于等于轴 右段中各元素都大于等于轴 这个过程称做对序列分割或划分 左段和右段的元素可以独立排序 将排好序的三段合并到一起即可上面的过程可以递归地执行 直到每段的长度为1 内排序 30 快排序 QuickSort 快速排序实例 快排序 算法思想 内排序 31 快排序 QuickSort 快排序 分割过程快排序是一个分治算法 也是第一个 快排序的关键过程是每次递归的分割过程分割问题描述 对一个序列 取它的一个元素作为轴 把所有小于轴的元素放在它的左边 大于它的元素放在它的右边分割算法 用临时变量对轴备份取两个指针low和high 它们的初始值就是序列的两端下标 在整个过程中保证low不大于high移动两个指针首先从high所指的位置向左搜索 找到第一个小于轴的元素 把这个元素放在low的位置再从low开始向右 找到第一个大于轴的元素 把它放在high的位置 内排序 32 快排序 QuickSort 快排序 分割过程分割算法 重复上述过程 直到low high 把轴放在low所指的位置这样所有大于轴的元素被放在右边 所有小于轴的元素被放在左边 内排序 33 快排序 QuickSort 快排序 分割过程 38659776132749 49 low high pivot 49 01234567 high 386597761349 27 low 273897761349 65 high 273897766549 13 low 273813766549 97 high 49 内排序 34 快排序 QuickSort 快排序 分割过程intPartition TArray intlow inthigh Tpivot Array low while low pivot high Array low Array high while low high 内排序 35 快排序 QuickSort 快排序 算法快排序算法是个递归地对序列进行分割的过程 递归终止的条件是最终序列长度为1 01234567 4938659776132749 76976549 273813 49 49 13 38 27 4965 97 76 131738497697 4965 内排序 36 快排序 QuickSort 快排序 算法voidQuickSort TArray intlow inthigh intPivotLocation if low high PivotLocation Partition Array low high QuickSort Array low PivotLocation 1 QuickSort Array PivotLocation 1 high 内排序 37 3 快速排序的效率分析 若快速排序出现最好的情形 左 右子区间的长度大致相等 则结点数n与二叉树深度h应满足log2n h log2n 1 所以总的比较次数不会超过 n 1 log2n 因此 快速排序的最好时间复杂度应为O nlog2n 而且在理论上已经证明 快速排序的平均时间复杂度也为O nlog2n 若快速排序出现最坏的情形 每次能划分成两个子区间 但其中一个是空 则这时得到的二叉树是一棵单分枝树 得到的非空子区间包含有n i个 i代表二叉树的层数 1 i n 元素 每层划分需要比较n i 2次 所以总的比较次数为 n2 3n 4 2 因此 快速排序的最坏时间复杂度为O n2 快速排序所占用的辅助空间为栈的深度 故最好的空间复杂度为O log2n 最坏的空间复杂度为O n 快速排序是一种不稳定的排序方法 举例 6 7 5 2 5 8 内排序 38 思考题 请给出在最坏情况下只需7次元素比较的5个元素的排序算法 2 请给出一个有效的对n个元素进行排序的算法 使得所有负元素位于非负元素之前 3 请给出一个有效的对n个正整数进行排序的算法 使得所有偶数位于奇数之前 内排序 39 思想 每一趟都选出一个最大或最小的元素 并放在合适的位置 直接选择排序 树形选择排序 堆排序 选择排序 内排序 40 思想 第1趟选择 从1 n个记录中选择关键字最小的记录 并和第1个记录交换 第2趟选择 从2 n个记录中选择关键字最小的记录 并和第2个记录交换 第n 1趟选择 从n 1 n个记录中选择关键字最小的记录 并和第n 1个记录交换 直接选择排序 内排序 41 例 序列4938976576 第1趟选择 3849976576 第2趟选择 3849976576 第3趟选择 3849659776 第4趟选择 3849657697 内排序 42 直接选择排序的算法templatevoidSelectSort TVector intCurrentSize for inti 0 i CurrentSize 1 i intk i 选择具有最小排序码的对象for intj i 1 j CurrentSize j if Vector j Vector k k j 当前具最小排序码的对象if k i 对换到第i个位置Swap Vector i Vector k 内排序 43 直接选择排序复杂度分析时间效率 O n2 虽移动次数较少 但比较次数仍多 空间效率 O 1 没有附加单元 仅用到1个temp 算法的稳定性 不稳定 举例 6 2 6 3 内排序 44 选择排序的主要操作是进行关键字间的比较 在n个关键字中选出最小值 至少需要n 1次比较 在剩余的n 1个关键字中选出最小值 至少需要n 2次比较 如果能利用前n 1次比较所得信息 可以减少后面选择的比较次数 体育比赛中的锦标赛 直接选择排序分析 内排序 45 例 8名运动员要决出冠 亚 季军 按简单选择排序需要比赛7 6 5 18场 若能够利用以前的比赛结果 比赛场次实际可以减少为11场 前提 若甲胜乙 乙胜丙 则甲必能胜丙 冠军 内排序 46 如何求亚军 亚军 可以利用前面的比赛结果 内排序 47 如何求季军 季军 同样可以利用前面的比赛结果 内排序 48 又称锦标赛排序 是一种按照锦标赛的思想进行选择排序的方法 例 序列4938659776132750 第一趟选择 最小值 树形选择排序 内排序 49 第二趟选择 次小值 第三趟选择 次次小值 缺点 需要大量辅助存储空间 内排序 50 堆 一棵完全二叉树 任一个非终端结点的值均小于等于 或大于等于 其左 右儿子结点的值 例 根结点为最小值 根结点为最大值 堆排序 内排序 51 2 把这棵普通的完全二叉树改造成堆 便可获取最小值 思想 3 输出最小值 4 删除根结点 继续改造剩余树成堆 便可获取次小值 5 输出次小值 6 重复改造 输出次次小值 次次次小值 直至所有结点均输出 便得到一个排序 1 将序列构造成一棵完全二叉树 内排序 52 例 序列4938659776132750 1 按顺序依次构造成完全二叉树的结点 2 把完全二叉树改造成堆 从下向上 父子交换 3 取得最小值13 4 删除13 重新改造成新堆 5 取得次小值27 6 删除27 重新改造成新堆 7 取得次次小值38 内排序 53 算法分析 时间效率 O nlog2n 因为整个排序过程中需要调用n 1次堆顶点的调整 而每次堆排序算法本身耗时为log2n 空间效率 O 1 仅在交换记录时用到一个临时变量temp 稳定性 不稳定 优点 对小文件效果不明显 但对大文件有效 内排序 54 归并排序 MergeSort 归并 合并两个有序的序列假设有两个已排序好的序列A 长度为n1 B 长度为n2 将它们合并为一个有序的序列C 长度为n n1 n2 方法很简单 把A B两个序列的最小元素进行比较 把其中较小的元素作为C的第一个元素 在A B剩余的元素中继续挑最小的元素进行比较 确定C的第二个元素 依次类推 就可以完成对A和B的归并 其复杂度为O n 内排序 55 归并排序 MergeSort 归并 合并两个有序的序列 A 138911 B 2571013 C 1235789101113 内排序 56 归并排序 MergeSort 归并 合并两个有序的序列voidmerge TA intAlen TB intBlen TC inti 0 j 0 k 0 while i Alen 内排序 57 归并排序 MergeSort 归并排序归并排序是一个分治递归算法递归基础 若序列只有一个元素 则它是有序的 不执行任何操作递归步骤 先把序列划分成长度基本相等的两个序列对每个子序列递归排序把排好序的子序列归并成最后的结果 内排序 58 归并排序 MergeSort 归并排序 初始序列 8 4 5 6 2 1 7 3 分解 8 4 5 6 2 1 7 3 归并 4 8 5 6 1 2 3 7 归并 4 5 6 8 1 2 3 7 归并 1 2 3 4 5 6 7 8 分解 8 4 5 6 2 1 7 3 分解 8 4 5 6 2 1 7 3 内排序 59 归并排序 MergeSort 归并排序voidMergeSort intA intB intl inth if l h return intm l h 2 MergeSort A B l m MergeSort A B m 1 h Merge A B l m h 注意这里的归并是对一个序列的两段进行归并 需要对上面的算法进行修改 思想是一致的 内排序 60 归并排序 MergeSort 算法分析最坏情况 归并排序是一个递归算法 所以很容易得到算法计算量的递推公式所以算法最坏情况的复杂度为算法需要的辅助空间因为需要一个与原始序列同样大小的辅助序列 这是此算法的缺点 稳定性 稳定 内排序 61 归并排序 MergeSort 其他策略上面归并排序每次迭代时将原序列分割为两个基本等长的序列 称为二路归并排序也可以分割成其他等分 如3 4等等评论 尽管归并排序最坏情况的比较次数比快速排序少 但它需要更多的元素移动 因此 它在实用中不一定比快速排序快 内排序 62 基于比较的算法总是在一系列比较下完成的每次比较都可能出现两种情况 a b和a b 如果以每次比较作为节点 则每个以比较为基础的排序算法都可以用一个二叉树来表示 其中一个中间节点表示一次比较 叶子节点表示排序的一种结果 这样的二叉树称为判定树或决策树举例 比如有一个序列 a b c a b c互不相等 下列算法 先比较a和b 再比较a和c 最后比较b和c可以用下面的判定树表示 以比较为基础的排序算法的下界 内排序 63 a b yes a c yes b c yes a b c a c b no no no c a b a c yes b a c no b c yes b c a c b a no 以比较为基础的排序算法的下界 内排序 64 假设输入为a b c a c b 则算法执行经过的路线为 a b a c b c 需要3次比较假设输入为a b c b a c 则算法执行经过的路线为 a b a c 需要2次比较任何以比较为基础的排序算法都可以表示为一棵决策树树的形状和大小表示的是排序算法的功能和需要排序的元素个数树的高度表示了算法的运行时间任何排序决策树都有n 个叶子 以比较为基础的排序算法的下界 内排序 65 根据数据结构中关于二叉树的性质 有 最坏情况 任何排序算法至少要做次比较平均情况 任何排序算法的平均比较次数的下界是结论 具有O nlgn 复杂度的比较排序算法在渐进意义下是最优的算法 以比较为基础的排序算法的下界 内排序 66 基于分配的排序 桶式排序基数排序 内排序 67 桶式排序 事先知道序列中的记录都位于某个小区间段 0 m 内将具有相同值的记录都分配到同一个桶中 然后依次按照编号从桶中取出记录 组成一个有序序列 内排序 68 桶式排序 m 10初始序列 3 2 4 8 7 1 6 4 9 8 7 出现次数 0 1 1 1 2 0 1 2 2 1开始位置 0 1 2 3 5 5 6 8 10 11排序结果 1 2 3 4 4 6 7 7 8 8 9 内排序 69 桶式排序算法分析 数组长度为n 所有记录区间 0 m 上时间代价 统计计数时 n m 输出有序序列时循环n次总的时间代价为 m n 适用于m相对于n很小的情况空间代价 m个计数器 长度为n的临时数组 m n 稳定 内排序 70 桶式排序和基数排序 桶式排序只适合m很小的情况 当m很大时 可以将一个记录的值即排序码拆分为多个部分来进行比较 基数排序 内排序 71 是一种借助多关键字排序的思想对单逻辑关键字进行排序的方法 1 多关键字排序 扑克牌问题 已知扑克牌中52张牌面的次序关系定义为 例 8 3 花色优先级更高 为主关键字 面值为次关键字 基数排序 内排序 72 2 52张牌排序方法 最高位优先法 MSDF 先按不同 花色 分成有次序的4堆 每一堆均具有相同的花色 然后分别对每一堆按 面值 大小整理有序 最低位优先法 LSDF 先按不同 面值 分成13堆 然后将这13堆牌自小至大叠在一起 2 3 A 然后将这付牌整个颠倒过来再重新按不同的 花色 分成4堆 最后将这4堆牌按自小至大的次序合在一起 收集 分配 内排序 73 3 基数排序 基数排序就是借助于 分配 和 收集 两种操作实现对单逻辑关键字的排序 首先 单逻辑关键字通常都可以看作是由若干关键字复合而成 其次 利用LSDF法实现对若干关键字的排序 例 若关键字是数值 且值域为0 K 999 故可以将K看作是由3个关键字K0K1K2组成 例 603是由603组成 内排序 74 例 序列278109063930589184505269008083 第一趟分配 0123456789 第一趟收集 930 063083 184 505 278008 109589269 第二趟分配 0123456789 第二趟收集 505008109 930 063269 278 083184589 内排序 75 第三趟分配 0123456789 第三趟收集 008063083 109184 269278 505589 930 内排序 76 链式存