第9章 排序 课后习题一、选择题1.在排序算法中从未排序序列中依次取出元素与已排序序列初始为空中的元素进行比较要求比较次数尽量少然后将其放入已排序序列的正确位置的算法是B排序。A.冒泡B.直接插入C.选择D.快速解析直接插入排序的核心思想正是将待排序序列中的元素依次取出与已有序序列中的元素从后往前比较找到合适的位置插入。题目中“从未排序序列中依次取出元素与已排序序列中的元素进行比较”正是插入排序的特征描述。“要求比较次数尽量少”提示了插入排序在部分有序时效率高的特点但并非定义关键。其他选项冒泡排序相邻元素两两比较交换不是取元素插入已排序序列。选择排序每次选最小放到已排序序列末尾不是插入比较。快速排序分治法选基准划分不是依次插入已排序序列。2.对n个元素进行冒泡排序要求按升序排序程序中设定某一趟冒泡没有出现元素交换就结束排序过程。某n个元素的序列2, 1, 4, 3, ..., n, n-1共进行了D次比较就完成了排序。A. nB. n-1C. 2nD. 2n-3解析序列特点每两个相邻元素是逆序的21, 43, ..., n n-1n为偶数时最后两个也是逆序。第一趟冒泡相邻比较n-1次将最大元素沉底n移到末尾序列变为1,2,3,4,...,n-2,n-1,n后续有序。第二趟冒泡比较n-2次因为最后一位已有序没有交换结束。总比较次数 (n-1) (n-2) 2n - 3。3.一组记录的关键字序列为(36, 69, 46, 28, 30, 74)利用快速排序以第一个关键字为分割元素经一次划分后的结果为A。A. 30, 28, 36, 46, 69, 74B. 28, 30, 36, 46, 69, 74C. 30, 28, 36, 69, 46, 74D. 30, 28, 36, 74, 46, 69解析以36为枢轴从右向左找小于36的30从左向右找大于36的69交换→ (30, 28, 46, 69, 36, 74)继续右指针找到28左指针找到46交换→ (30, 28, 36, 69, 46, 74)左右指针相遇枢轴到位。最终30, 28, 36, 46, 69, 74。4.设已有m个元素有序在未排好序的序列中挑选第m1个元素并且只经过一次元素间的交换使第m1个元素排序到位该算法是C。A.冒泡排序B.折半排序C.简单选择排序D.归并排序解析简单选择排序每次从剩余序列中选出最小或最大元素与第m1个位置元素交换一次使其到位。符合“一次交换使第m1个元素排序到位”。5.一组记录的关键字序列为(46, 79, 56, 38, 40, 45)利用堆排序堆顶元素是最小元素的算法建立的初始堆为A。A. 38, 40, 45, 79, 46, 56B. 38, 46, 45, 79, 40, 56C. 40, 38, 45, 46, 56, 79D. 38, 79, 45, 46, 56解析建小顶堆过程从最后一个非叶子结点开始向下调整。初始46,79,56,38,40,45调整结点56无需动调整结点79与38交换调整结点46与38交换再与40交换实际需逐步验证最终得到38,40,45,79,46,56。二、问答题1.一组记录的关键字序列为(55, 39, 95, 24, 16, 74, 62, 43, 88)对其进行直接插入排序当把第7个关键字62插入有序表时为找插入位置需进行多少次元素的比较答4次解析前6个排序后为(16,24,39,55,74,95)。插入62时与95,74,55,39比较后插入55和74之间。比较次数 4次与95,74,55,39。2.一组记录的关键字序列为(48, 82, 58, 40, 42, 47)请用堆排序做升序排序给出前三趟的每一趟的结果以二叉树描述6个元素的堆以及逐次取走堆顶元素后5个元素、4个元素、3个元素的堆。答初始建堆小顶堆(40,42,47,82,58,48)第1趟输出40剩余调整堆→ (42,48,47,82,58)第2趟输出42剩余调整堆→ (47,48,58,82)第3趟输出47剩余调整堆→ (48,58,82)3.已知序列{12, 20, 6, 5, 8, 14, 3, 12, 20, 10}请给出采用归并排序法对该序列做升序排序时每一趟的结果。答初始12,20,6,5,8,14,3,12,20,10第1趟2-路归并(12,20), (5,6), (8,14), (3,12), (10,20)第2趟4-路归并(5,6,12,20), (3,8,12,14), (10,20)第3趟8-路归并(3,5,6,8,12,12,14,20), (10,20)第4趟3,5,6,8,10,12,12,14,20,204.已知序列{68, 32, 78, 52, 6, 20, 10, 12, 22, 50}要求按升序排序采用快速排序法试写出每一趟划分的结果。5.举例说明快速排序是一种不稳定的排序算法。答例序列(5, 3, 3, 8, 2)以第一个5为枢轴划分后3和3的相对顺序可能改变证明不稳定。6.已知序列{13, 3, 18, 32, 8, 29, 4, 10, 20, 5, 19}要求对其按下述算法进行升序排序写出每一趟的结果(1)冒泡排序(2)选择排序(3)插入排序。知识点补充一、排序算法稳定性总结稳定排序不稳定排序直接插入排序希尔排序折半插入排序快速排序冒泡排序简单选择排序归并排序堆排序基数排序稳定性判断技巧相邻交换的排序通常稳定冒泡、插入远距离交换的排序通常不稳定希尔、快速、选择、堆二、第2题详解特殊序列冒泡排序比较次数序列特点2, 1, 4, 3, ..., n, n-1n为偶数每对相邻元素逆序21, 43, ..., nn-1第一趟冒泡比较n-1次最大元素n沉底序列变为1,2,3,4,...,n-2,n-1,n已有序第二趟冒泡比较n-2次无交换提前结束总比较次数 (n-1) (n-2) 2n-3答案D三、快速排序不稳定证明第5题反例序列(5, 3¹, 3², 8, 2) 注3¹和3²值相等下标标记区别第一趟划分枢轴5从右找小于52从左找大于58交换2和8 → (5,3¹,3²,2,8)继续从右找小于52已处理继续找到3²从左找大于5无交换枢轴与3² → (3²,3¹,5,2,8)结果两个3的相对顺序从(3¹,3²)变为(3²,3¹) →不稳定四、希尔排序补充增量序列时间复杂度希尔增量n/2, n/4, ..., 1O(n²)Hibbard增量2^k-1O(n^1.5)Sedgewick增量O(n^1.3)特点不稳定优于直接插入排序增量序列最后必须为1五、基数排序类型排序方式稳定性LSD最低位优先从个位到高位稳定MSD最高位优先从高位到低位递归稳定时间复杂度O(d·(nr))d关键字位数r基数如十进制r10n元素个数空间复杂度O(nr)适用场景整数、固定长度字符串六、外部排序阶段操作说明置换选择排序生成初始归并段内存大小限制多路归并合并归并段使用败者树优化最佳归并树哈夫曼树减少归并次数时间复杂度主要由磁盘I/O决定七、排序算法选择建议数据特征推荐算法理由n ≤ 50直接插入/简单选择简单常数小基本有序直接插入/冒泡接近O(n)随机且n大快速排序平均最快稳定性要求归并排序稳定且O(n log n)内存有限堆排序空间O(1)整数且范围小基数排序O(n)外部排序多路归并适合磁盘文件八、第4题解析简单选择排序的“一次交换”简单选择排序特点每趟从剩余元素中选出最小或最大元素与第i个位置元素进行一次交换使该位置元素立即到位与冒泡排序区别冒泡排序可能多次交换选择排序每趟最多一次交换答案C九、排序算法复杂度总表算法最好平均最坏空间稳定性直接插入O(n)O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n)O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定基数排序O(d(nr))O(d(nr))O(d(nr))O(nr)稳定十、问答题第3题归并排序过程序列12,20,6,5,8,14,3,12,20,10趟数结果初始12,20,6,5,8,14,3,12,20,10第1趟[12,20], [5,6], [8,14], [3,12], [10,20]第2趟[5,6,12,20], [3,8,12,14], [10,20]第3趟[3,5,6,8,12,12,14,20], [10,20]第4趟[3,5,6,8,10,12,12,14,20,20]注意当元素个数不是2的幂时最后一组单独处理
数据结构第9章排序：课后习题全解析（插入排序+冒泡排序+快速排序+堆排序+归并排序）
第9章 排序 课后习题一、选择题1.在排序算法中从未排序序列中依次取出元素与已排序序列初始为空中的元素进行比较要求比较次数尽量少然后将其放入已排序序列的正确位置的算法是B排序。A.冒泡B.直接插入C.选择D.快速解析直接插入排序的核心思想正是将待排序序列中的元素依次取出与已有序序列中的元素从后往前比较找到合适的位置插入。题目中“从未排序序列中依次取出元素与已排序序列中的元素进行比较”正是插入排序的特征描述。“要求比较次数尽量少”提示了插入排序在部分有序时效率高的特点但并非定义关键。其他选项冒泡排序相邻元素两两比较交换不是取元素插入已排序序列。选择排序每次选最小放到已排序序列末尾不是插入比较。快速排序分治法选基准划分不是依次插入已排序序列。2.对n个元素进行冒泡排序要求按升序排序程序中设定某一趟冒泡没有出现元素交换就结束排序过程。某n个元素的序列2, 1, 4, 3, ..., n, n-1共进行了D次比较就完成了排序。A. nB. n-1C. 2nD. 2n-3解析序列特点每两个相邻元素是逆序的21, 43, ..., n n-1n为偶数时最后两个也是逆序。第一趟冒泡相邻比较n-1次将最大元素沉底n移到末尾序列变为1,2,3,4,...,n-2,n-1,n后续有序。第二趟冒泡比较n-2次因为最后一位已有序没有交换结束。总比较次数 (n-1) (n-2) 2n - 3。3.一组记录的关键字序列为(36, 69, 46, 28, 30, 74)利用快速排序以第一个关键字为分割元素经一次划分后的结果为A。A. 30, 28, 36, 46, 69, 74B. 28, 30, 36, 46, 69, 74C. 30, 28, 36, 69, 46, 74D. 30, 28, 36, 74, 46, 69解析以36为枢轴从右向左找小于36的30从左向右找大于36的69交换→ (30, 28, 46, 69, 36, 74)继续右指针找到28左指针找到46交换→ (30, 28, 36, 69, 46, 74)左右指针相遇枢轴到位。最终30, 28, 36, 46, 69, 74。4.设已有m个元素有序在未排好序的序列中挑选第m1个元素并且只经过一次元素间的交换使第m1个元素排序到位该算法是C。A.冒泡排序B.折半排序C.简单选择排序D.归并排序解析简单选择排序每次从剩余序列中选出最小或最大元素与第m1个位置元素交换一次使其到位。符合“一次交换使第m1个元素排序到位”。5.一组记录的关键字序列为(46, 79, 56, 38, 40, 45)利用堆排序堆顶元素是最小元素的算法建立的初始堆为A。A. 38, 40, 45, 79, 46, 56B. 38, 46, 45, 79, 40, 56C. 40, 38, 45, 46, 56, 79D. 38, 79, 45, 46, 56解析建小顶堆过程从最后一个非叶子结点开始向下调整。初始46,79,56,38,40,45调整结点56无需动调整结点79与38交换调整结点46与38交换再与40交换实际需逐步验证最终得到38,40,45,79,46,56。二、问答题1.一组记录的关键字序列为(55, 39, 95, 24, 16, 74, 62, 43, 88)对其进行直接插入排序当把第7个关键字62插入有序表时为找插入位置需进行多少次元素的比较答4次解析前6个排序后为(16,24,39,55,74,95)。插入62时与95,74,55,39比较后插入55和74之间。比较次数 4次与95,74,55,39。2.一组记录的关键字序列为(48, 82, 58, 40, 42, 47)请用堆排序做升序排序给出前三趟的每一趟的结果以二叉树描述6个元素的堆以及逐次取走堆顶元素后5个元素、4个元素、3个元素的堆。答初始建堆小顶堆(40,42,47,82,58,48)第1趟输出40剩余调整堆→ (42,48,47,82,58)第2趟输出42剩余调整堆→ (47,48,58,82)第3趟输出47剩余调整堆→ (48,58,82)3.已知序列{12, 20, 6, 5, 8, 14, 3, 12, 20, 10}请给出采用归并排序法对该序列做升序排序时每一趟的结果。答初始12,20,6,5,8,14,3,12,20,10第1趟2-路归并(12,20), (5,6), (8,14), (3,12), (10,20)第2趟4-路归并(5,6,12,20), (3,8,12,14), (10,20)第3趟8-路归并(3,5,6,8,12,12,14,20), (10,20)第4趟3,5,6,8,10,12,12,14,20,204.已知序列{68, 32, 78, 52, 6, 20, 10, 12, 22, 50}要求按升序排序采用快速排序法试写出每一趟划分的结果。5.举例说明快速排序是一种不稳定的排序算法。答例序列(5, 3, 3, 8, 2)以第一个5为枢轴划分后3和3的相对顺序可能改变证明不稳定。6.已知序列{13, 3, 18, 32, 8, 29, 4, 10, 20, 5, 19}要求对其按下述算法进行升序排序写出每一趟的结果(1)冒泡排序(2)选择排序(3)插入排序。知识点补充一、排序算法稳定性总结稳定排序不稳定排序直接插入排序希尔排序折半插入排序快速排序冒泡排序简单选择排序归并排序堆排序基数排序稳定性判断技巧相邻交换的排序通常稳定冒泡、插入远距离交换的排序通常不稳定希尔、快速、选择、堆二、第2题详解特殊序列冒泡排序比较次数序列特点2, 1, 4, 3, ..., n, n-1n为偶数每对相邻元素逆序21, 43, ..., nn-1第一趟冒泡比较n-1次最大元素n沉底序列变为1,2,3,4,...,n-2,n-1,n已有序第二趟冒泡比较n-2次无交换提前结束总比较次数 (n-1) (n-2) 2n-3答案D三、快速排序不稳定证明第5题反例序列(5, 3¹, 3², 8, 2) 注3¹和3²值相等下标标记区别第一趟划分枢轴5从右找小于52从左找大于58交换2和8 → (5,3¹,3²,2,8)继续从右找小于52已处理继续找到3²从左找大于5无交换枢轴与3² → (3²,3¹,5,2,8)结果两个3的相对顺序从(3¹,3²)变为(3²,3¹) →不稳定四、希尔排序补充增量序列时间复杂度希尔增量n/2, n/4, ..., 1O(n²)Hibbard增量2^k-1O(n^1.5)Sedgewick增量O(n^1.3)特点不稳定优于直接插入排序增量序列最后必须为1五、基数排序类型排序方式稳定性LSD最低位优先从个位到高位稳定MSD最高位优先从高位到低位递归稳定时间复杂度O(d·(nr))d关键字位数r基数如十进制r10n元素个数空间复杂度O(nr)适用场景整数、固定长度字符串六、外部排序阶段操作说明置换选择排序生成初始归并段内存大小限制多路归并合并归并段使用败者树优化最佳归并树哈夫曼树减少归并次数时间复杂度主要由磁盘I/O决定七、排序算法选择建议数据特征推荐算法理由n ≤ 50直接插入/简单选择简单常数小基本有序直接插入/冒泡接近O(n)随机且n大快速排序平均最快稳定性要求归并排序稳定且O(n log n)内存有限堆排序空间O(1)整数且范围小基数排序O(n)外部排序多路归并适合磁盘文件八、第4题解析简单选择排序的“一次交换”简单选择排序特点每趟从剩余元素中选出最小或最大元素与第i个位置元素进行一次交换使该位置元素立即到位与冒泡排序区别冒泡排序可能多次交换选择排序每趟最多一次交换答案C九、排序算法复杂度总表算法最好平均最坏空间稳定性直接插入O(n)O(n²)O(n²)O(1)稳定希尔排序O(n^1.3)O(n^1.3)O(n²)O(1)不稳定冒泡排序O(n)O(n²)O(n²)O(1)稳定快速排序O(n log n)O(n log n)O(n²)O(log n)不稳定简单选择O(n²)O(n²)O(n²)O(1)不稳定堆排序O(n log n)O(n log n)O(n log n)O(1)不稳定归并排序O(n log n)O(n log n)O(n log n)O(n)稳定基数排序O(d(nr))O(d(nr))O(d(nr))O(nr)稳定十、问答题第3题归并排序过程序列12,20,6,5,8,14,3,12,20,10趟数结果初始12,20,6,5,8,14,3,12,20,10第1趟[12,20], [5,6], [8,14], [3,12], [10,20]第2趟[5,6,12,20], [3,8,12,14], [10,20]第3趟[3,5,6,8,12,12,14,20], [10,20]第4趟[3,5,6,8,10,12,12,14,20,20]注意当元素个数不是2的幂时最后一组单独处理
