可南广播电视大学现黄中心 第九章排序课后习题答案 1、单项这择题 (1)A (2)C (3)A 评细解愿步骤如下： 初始：关键宁字 36 366946283084 ↑ ↑6 ①j从后向暗，a们与36比较，84站，继续向前扫描，且户5 3669 46283084 ↑ ↑5 ②j从后向前，们与36比较，30<3站，们置于们的位置，+，得到一2 306946283084 12 ti-s ③i从前月后，可与36比较，696，可置于的位置，j,得到j4 306946286984 12 ④j从后白前，a]与36比较，28<36，们置于a可的位置，+，得到-3 302846286984 ↑3f @i从前向后，可与36比较，46站，可置于0们的位置，小-，得到j=3 302846466984 =3 1j=3 @=3,关键学36放置的位置为国3引，第一次划分的结果为： 302836466984 第1页共10项 饭权所有河南电大现教中心氨颗，年箱@pen.hao西
河南广播电视大学现教中心 第1页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 第九章 排序 课后习题答案 1、 单项选择题 （1） A （2） C （3） A 详细解题步骤如下： 初始：关键字 36 36 69 46 28 30 84 i=1 j=6 ① j 从后向前，a[j]与 36 比较，84>36，继续向前扫描，且 j=5 36 69 46 28 30 84 i=1 j=5 ② j 从后向前，a[j]与 36 比较，3036，a[i]置于 a[j]的位置，j--，得到 j=4 30 69 46 28 69 84 i=2 j=4 ④ j 从后向前，a[j]与 36 比较，2836，a[i]置于 a[j]的位置，j--，得到 j=3 30 28 46 46 69 84 i=3 j=3 ⑥ i=j=3，关键字 36 放置的位置为 a[3]，第一次划分的结果为： 30 28 36 46 69 84
河南厂播电现大学现数中心 (4)C (5)A详细解题步骤如下： 根据序列(46,79,56,38,40,45)，构造完全二叉树如下： 46 79 56 38 4045 根据完全二义树，构造小根雌，首先调整第礼2个元素，即第3个元素56 ①调整第3个元素56,56与45交换，45为顶点的二叉树构成小根堆 46 79 45 38 40 56 ②调整第2个元素9,9与38交换，58为顶点的二义树构成小根堆 46 38 45 79 4056 ③调整第1个元素46.46与38交换，不构成小根堆。46再与40交换 38 38 46 45 40 45 构成小根堆 79 40 56 7946 56 小根堆的序列为(38,40,45,79,46,56) 2、简答题 (1)解容，需要进行三次比较。 当插入2前，前面的序列已经是有序的，如下所示： (162439557495)624388 ①62先与95比较，9562,62插入到95前面 (16243955746295)4388 ②62再与前面的74比较，7462,62插入到74前面 第2项共10项 蚁权所有河南电大现教中心范颖，年箱@xnh:m
河南广播电视大学现教中心 第2页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （4） C （5） A 详细解题步骤如下： 根据序列（46，79，56，38，40，45），构造完全二叉树如下： 46 79 56 38 40 45 根据完全二叉树，构造小根堆，首先调整第 n/2 个元素，即第 3 个元素 56 ① 调整第 3 个元素 56，56 与 45 交换，45 为顶点的二叉树构成小根堆 46 79 45 38 40 56 ② 调整第 2 个元素 79，79 与 38 交换，38 为顶点的二叉树构成小根堆 46 38 45 79 40 56 ③ 调整第 1 个元素 46，46 与 38 交换，不构成小根堆，46 再与 40 交换 38 46 45 79 40 56 38 40 45 79 46 56 构成小根堆 小根堆的序列为（38，40，45，79，46，56） 2、 简答题 （1） 解答：需要进行三次比较。 当插入 62 前，前面的序列已经是有序的，如下所示： （16 24 39 55 74 95）62 43 88 ① 62 先与 95 比较，95>62，62 插入到 95 前面 （16 24 39 55 74 62 95）43 88 ② 62 再与前面的 74 比较，74>62，62 插入到 74 前面
河南广播电视大学现黄中心 (16243955627495)4388 ③62再与前面的55比较，5542 47 构成小根堆 82 4258 824858 第二步：输出堆顶元素进行堆持序 ①输出40后，堆为(42,48,47,82,58) 棕出40 58 线0的酸置 媒与42实格 42 线与4标交黄 47 41 47→8 妃48 58 构城小根缩 ②输出42后，堆为(47,48,58.82) 第3项共10面 饭权所有河南电大现教中心我预，年箱予@peha通
河南广播电视大学现教中心 第3页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn （16 24 39 55 62 74 95）43 88 ③ 62 再与前面的 55 比较，55<62，找到合适的位置，不用比较了 所以一共比较了 3 次。 （2） 进行堆排序，首先建立小根堆，再进行堆顶元素输出。 第一步：根据序列（48，82，58，40，42，47），构造完全二叉树如下： 48 82 58 40 42 47 根据完全二叉树，构造小根堆，首先调整第 n/2 个元素，即第 3 个元素 58 ① 调整第 3 个元素 58，58 与 47 交换，47 为顶点的二叉树构成小根堆 48 82 47 40 42 58 ② 调整第 2 个元素 82，82 与 40 交换，40 为顶点的二叉树构成小根堆 48 40 47 82 42 58 ③ 调整第 1 个元素 48，48 与 40 交换，不构成小根堆，48 再与 42 交换 40 48 47 82 42 58 40 42 47 82 48 58 构成小根堆 第二步：输出堆顶元素进行堆排序 ① 输出 40 后，堆为（42，48，47，82，58） 40 42 47 82 48 58 58 42 47 82 48 42 58 47 82 48 42 48 47 82 58 输出40 58补40的位置 58与42交换 58与48交换 构成小根堆 ② 输出 42 后，堆为（47，48，58，82）
河南广播电视大学现教中心 42 输出2 5参补42的位置 58 5露与47交晚 47 48 47→48 47→48 58 构成小根堆 8258 82 82 ③输出47，雌为《48,82,58) 47 输出47 2补47的位置 2与48交损 82 48 48 58 48 58 82 58构城小根维 82 (3) 因序列中12和20重复出现，为区分数字，重复的数字后面加引号区分 序列更改为(12,20,6,5,8,14,3,12'，20,10)，稳定排序，12与12'，20 与20的位置是不会改变的. 每墙结果如下： 初始【211201【6115】181【141【31【2]【201【101 第一婚 自并后 112201 [S 61 [3 110301 第二塘 白并后 [5612201 【3 12201 I10 201 第三墙 13 5 6 8 1212 期并后 14 201 110 201 第四墙 归并后 【3 56 810 121214 20 201 (4)每墙划分结果如下： 第一播：5032225262010126878 第二插：1232221062050526878 第三墙：6101222322050526878 第四插：6101220223250526878 (5)解容 原序列：{5引2727*1 排序后：【27*27511 (6) 排序结果 第4项共10项 饭权所有河南电大现教中心题视，年箱)@pnhL通
河南广播电视大学现教中心 第4页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 42 48 47 82 58 输出42 58补42的位置 58 48 47 82 58与47交换 47 48 58 82 构成小根堆 ③ 输出 47，堆为（48，82，58） 47 48 58 82 构成小根堆 输出47 82补47的位置 82 48 58 48 82 58 82与48交换 （3） 因序列中 12 和 20 重复出现，为区分数字，重复的数字后面加引号区分 序列更改为（12，20，6，5，8，14，3，12’，20’，10），稳定排序，12 与 12’，20 与 20’的位置是不会改变的。 每趟结果如下： 初始 [ 12 ] [ 20 ] [ 6 ] [ 5 ] [ 8 ] [ 14 ] [ 3 ] [ 12' ] [ 20' ] [ 10 ] [ 12 20 ] [ 5 6 ] [ 8 14 ] [ 3 12'] [ 10 20' ] 第一趟 归并后 [ 5 6 12 20 ] [ 10 20' ] 第二趟 归并后 [ 3 8 12' 20 ] [ 3 5 6 8 12 12' 14 20 ] [ 10 20' ] 第三趟 归并后 [ 3 5 6 8 10 12 12' 14 20 20' ] 第四趟 归并后 （4） 每趟划分结果如下： 第一趟：50 32 22 52 6 20 10 12 68 78 第二趟：12 32 22 10 6 20 50 52 68 78 第三趟：6 10 12 22 32 20 50 52 68 78 第四趟：6 10 12 20 22 32 50 52 68 78 （5） 解答： 原序列：{ 51 27 27* } 排序后：{ 27* 27 51 } （6） 排序结果
河南厂播电现大学现数中心 ①冒泡排序 第一搏：313418328295102019 第二墙：341351832829101920 第三墙1345138183210291920 第四墙：345813101852192920 第五墙：345810131819322029 第大墙：345810131819203229 第七墙：345813101819202932 ②选择排序（直接选择） 第一墙：313183282941020519 第二蜡：341832829131020 519 第三墙：345328291310201819 第四墙：34583229 131020 1819 第五墙，3458102913322 1819 第六持：345810132932201819 第七趟：345810131832202919 第八韬：345810131819202932 第九培：345810131819202932 图插入排序（直接插入） 第一趟：133183282941020519 第二墙：313183282941020519 第三墙：3131832829410205 19 第四墙：313183282941020 19 第五趟：381318322941020519 第六墙：3813182932410 20 19 第七墙：3481318293210 20 19 第八婚：3481013182932 519 第九培：348101318202 519 第十趟：345810131820 3219 第十一崎，345810131819202932 第5项共10项 蚁权所有河南电大现教中心范颖，年箱@xnh:西
河南广播电视大学现教中心 第5页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn ① 冒泡排序 第一趟：3 13 4 18 32 8 29 5 10 20 19 第二趟：3 4 13 5 18 32 8 29 10 19 20 第三趟：3 4 5 13 8 18 32 10 29 19 20 第四趟：3 4 5 8 13 10 18 32 19 29 20 第五趟：3 4 5 8 10 13 18 19 32 20 29 第六趟：3 4 5 8 10 13 18 19 20 32 29 第七趟：3 4 5 8 13 10 18 19 20 29 32 ② 选择排序（直接选择） 第一趟：3 13 18 32 8 29 4 10 20 5 19 第二趟：3 4 18 32 8 29 13 10 20 5 19 第三趟：3 4 5 32 8 29 13 10 20 18 19 第四趟：3 4 5 8 32 29 13 10 20 18 19 第五趟：3 4 5 8 10 29 13 32 20 18 19 第六趟：3 4 5 8 10 13 29 32 20 18 19 第七趟：3 4 5 8 10 13 18 32 20 29 19 第八趟：3 4 5 8 10 13 18 19 20 29 32 第九趟：3 4 5 8 10 13 18 19 20 29 32 ③ 插入排序（直接插入） 第一趟：13 3 18 32 8 29 4 10 20 5 19 第二趟：3 13 18 32 8 29 4 10 20 5 19 第三趟：3 13 18 32 8 29 4 10 20 5 19 第四趟：3 13 18 32 8 29 4 10 20 5 19 第五趟：3 8 13 18 32 29 4 10 20 5 19 第六趟：3 8 13 18 29 32 4 10 20 5 19 第七趟：3 4 8 13 18 29 32 10 20 5 19 第八趟：3 4 8 10 13 18 29 32 20 5 19 第九趟：3 4 8 10 13 18 20 29 32 5 19 第十趟：3 4 5 8 10 13 18 20 29 32 19 第十一趟：3 4 5 8 10 13 18 19 20 29 32
河南广播电视大学现黄中心 课后题第二大题简答题第四小题详解 初始：关键字 63 6832785262010122250 ↑r0 第一随：以68为关键字，进行快速排序 ①j从后向前，们与68比较，50<68，们置于们的位置，i+,得到-2 5032785262010122250 i-2 r0 ②1从翰向后，日与68比较，3268，继续比较，+，得到-3 503边785262010122250 4 i-3 o @i从前向后，可与68比较，7868，门置于们的位置，j-,得到j9 503边785262010122278 i-3 j-9 ④j从后向前，a与68比较，2268，a们置于a的位置，++，得到4 5032225262010122278 ↑ ↑四 @1从赖向后，日与68比较，5268，雏铁比较，+，得到=5 5032225262010122278 i5 TF9 @i从前向后，可与68比较，668，继续比较，+，得到i-6 5032225262010122278 ↑6 ↑P ⑦i从前月后，可与68比较，2068，维续此较，i+,得到-7 503拉225262010122278 ↑m↑ @i从前向后，可与68比较，1068，继续比较，i+,得到-8 5032225262010122278 ↑网 @1从前向后，可与68比较，1268，继块比较，+，得到=9 第5项共10页 版权所有河南电大现餐中心我氧，年前予@pha✉
河南广播电视大学现教中心 第6页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 课后题第二大题简答题第四小题详解 初始：关键字 68 68 32 78 52 6 20 10 12 22 50 i=1 j=10 第一趟：以 68 为关键字，进行快速排序 ① j 从后向前，a[j]与 68 比较，5068，a[i]置于 a[j]的位置，j--，得到 j=9 50 32 78 52 6 20 10 12 22 78 i=3 j=9 ④ j 从后向前，a[j]与 68 比较，22<68，a[j]置于 a[i]的位置，i++，得到 i=4 50 32 22 52 6 20 10 12 22 78 i=4 j=9 ⑤ i 从前向后，a[i]与 68 比较，52<68，继续比较，i++，得到 i=5 50 32 22 52 6 20 10 12 22 78 i=5 j=9 ⑥ i 从前向后，a[i]与 68 比较，6<68，继续比较，i++，得到 i=6 50 32 22 52 6 20 10 12 22 78 i=6 j=9 ⑦ i 从前向后，a[i]与 68 比较，20<68，继续比较，i++，得到 i=7 50 32 22 52 6 20 10 12 22 78 i=7 j=9 ⑧ i 从前向后，a[i]与 68 比较，10<68，继续比较，i++，得到 i=8 50 32 22 52 6 20 10 12 22 78 i=8 j=9 ⑨ i 从前向后，a[i]与 68 比较，12<68，继续比较，i++，得到 i=9
河南广播电视大学现教中心 5032225262010122278 9 意-9，找到68的位置为9，最后的结果为： 503边225262010126够78 第二随：以68为分界，划分左序列为(50,32,22,526,20,10,12)，右序列为(78). 分别对左右序列进行快速排序。 右序列仅有一位，关键字为78，且丁0，排序结果为78。左序列以0为关键字，进行快 速排序。 初始：关键字 503222526201012 i-1 j-8 ①j从后向前，a们与50比较，120，门置于0们的位置，-，得到j-7 123222526201052 -4 7 j从后向前，a们与50比较，10<0，们置于们的位置，+，得到5 123222106201052 i-s ↑m @i从前向后，可与50比较，6<50，继续比较，+，得到-6 123222106201052 ↑7 ⑦1从输向后，a日与50比较，20<50，继续比较，+，得到-7 第7属共10项 饭权所有河南电大现载中心藏预，第箱@pnha通
河南广播电视大学现教中心 第7页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 50 32 22 52 6 20 10 12 22 78 i=9 j=9 ⑩ i=j=9，找到 68 的位置为 a[9]，最后的结果为： 50 32 22 52 6 20 10 12 68 78 第二趟：以 68 为分界，划分左序列为（50，32，22，52，6，20，10，12），右序列为（78）。 分别对左右序列进行快速排序。 右序列仅有一位，关键字为 78，且 i=j=10，排序结果为 78。左序列以 50 为关键字，进行快 速排序。 初始：关键字 50 50 32 22 52 6 20 10 12 i=1 j=8 ① j 从后向前，a[j]与 50 比较，1250，a[i]置于 a[j]的位置，j--，得到 j=7 12 32 22 52 6 20 10 52 i=4 j=7 ⑤ j 从后向前，a[j]与 50 比较，10<50，a[j]置于 a[i]的位置，i++，得到 i=5 12 32 22 10 6 20 10 52 i=5 j=7 ⑥ i 从前向后，a[i]与 50 比较，6<50，继续比较，i++，得到 i=6 12 32 22 10 6 20 10 52 i=6 j=7 ⑦ i 从前向后，a[i]与 50 比较，20<50，继续比较，i++，得到 i=7
河南厂播电现大学现数中心 12 3222106201052 7 i-7 @可j=7,找到S0的位置为)。最后的结果为： 123222106205052 整个第二墙排序的结果为打 1232221062050526感78 第三墙：以50为分界，划分左序列为(12,32,22,10,6,20)，右序列为(52)。分别对 左右序列进行快速排序。 石序列仅有一位，关健学为2，且了8，排序结果为52。左序列以12为关键字，进行快 速排序。 初始：关键字 2 12322210620 4 6 ①j从后白前，们与12比较，2012，维续比较，j,得到广5 12322210620 -1 i-5 ②j从后向暗，a们与2比较，<2，置于可们的位置，+，得到i=2 632210620 -2 -5 ③i从输白后，0与12比较，3212，问置于的位置，j,得到j4 63222103220 2j4 ④j从后白前，们与12比较，1012，a们置于a的位置，+，得到-3 61022103这20 4 @1从翰向后，可与12比较，2212，问置于山的位置，j,得到j3 61022223220 1-3 -3 第8风共0真 蚁权所有河南电大现教中心寇颖，邮箱6@pnh:m
河南广播电视大学现教中心 第8页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 12 32 22 10 6 20 10 52 i=7 j=7 ⑧ i=j=7，找到 50 的位置为 a[7]，最后的结果为： 12 32 22 10 6 20 50 52 整个第二趟排序的结果为： 12 32 22 10 6 20 50 52 68 78 第三趟：以 50 为分界，划分左序列为（12，32，22，10，6，20），右序列为（52）。分别对 左右序列进行快速排序。 右序列仅有一位，关键字为 52，且 i=j=8，排序结果为 52。左序列以 12 为关键字，进行快 速排序。 初始：关键字 12 12 32 22 10 6 20 i=1 j=6 ① j 从后向前，a[j]与 12 比较，20>12，继续比较，j--，得到 j=5 12 32 22 10 6 20 i=1 j=5 ② j 从后向前，a[j]与 12 比较，612，a[i]置于 a[j]的位置，j--，得到 j=4 6 32 22 10 32 20 i=2 j=4 ④ j 从后向前，a[j]与 12 比较，1012，a[i]置于 a[j]的位置，j--，得到 j=3 6 10 22 22 32 20 i=3 j=3
河南广播电视大学现数中心 ④可丁7，找到12的位置为可，最后的结果为： 61012223220 整个第三植排序的结果为： 61012223拉2050526感78 第四随：以12为分界，划分左序列为(6,10》，右序列为(22,32,20)。分别对左右序列 进行快速排序。 左序列： 初始：关键字 10 ↑2 ①j从后白前，们与6比较，10心6，饿续比较，j,得到一】 610 ②i可j-l,找到6的位置为可]，最后的结果为： 610 右序列： 初始：关键字 223220 T ①j从后白前，们与6比较，2022，]置于可的位置，+，得到i-2 203220 ↑2↑时 ②i从前向后，a0与22比较，3222，门置于们的位置，-，得到j=2 203232 i-2 「j2 ③与-2，找到22的位置为2小，最后的结果为 202232 左右序列结束后的结果为： 第9项共10面 版权所有河南电大现教中心我预，年箱予@open.ha通
河南广播电视大学现教中心 第9页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn ⑨ i=j=7，找到 12 的位置为 a[3]，最后的结果为： 6 10 12 22 32 20 整个第三趟排序的结果为： 6 10 12 22 32 20 50 52 68 78 第四趟：以 12 为分界，划分左序列为（6，10），右序列为（22，32，20）。分别对左右序列 进行快速排序。 左序列： 初始：关键字 6 6 10 i=1 j=2 ① j 从后向前，a[j]与 6 比较，10>6，继续比较，j--，得到 j=1 6 10 i=1 j=1 ② i=j=1，找到 6 的位置为 a[1]，最后的结果为： 6 10 右序列： 初始：关键字 22 22 32 20 i=1 j=3 ① j 从后向前，a[j]与 6 比较，2022，a[i]置于 a[j]的位置，j--，得到 j=2 20 32 32 i=2 j=2 ③ i=j=2，找到 22 的位置为 a[2]，最后的结果为： 20 22 32 左右序列结束后的结果为：
可南广播电视大学现黄中心 61012202252 整个第四墙排序的结果为 6101220223250526域78 第10页共10页 蓝权所有河南电大现教中心范颗。船箱o加团
河南广播电视大学现教中心 第10页 共10页 版权所有 河南电大现教中心范颖，邮箱 fy@open.ha.cn 6 10 12 20 22 32 整个第四趟排序的结果为： 6 10 12 20 22 32 50 52 68 78