某序列,其关键字分别为{98,44,57,12,29,64,38,82},分别采用直接插入排序法和二路归并排序法对该序列进行递增排序,写出每一趟的排序结果。
时间: 2023-09-10 09:12:53 浏览: 127
好的,我来分别演示直接插入排序法和二路归并排序法对该序列进行递增排序的过程。
1. 直接插入排序法:
第一趟排序:{98},插入44后变为{44, 98};
第二趟排序:{44, 98},插入57后变为{44, 57, 98};
第三趟排序:{44, 57, 98},插入12后变为{12, 44, 57, 98};
第四趟排序:{12, 44, 57, 98},插入29后变为{12, 29, 44, 57, 98};
第五趟排序:{12, 29, 44, 57, 98},插入64后变为{12, 29, 44, 57, 64, 98};
第六趟排序:{12, 29, 44, 57, 64, 98},插入38后变为{12, 29, 38, 44, 57, 64, 98};
第七趟排序:{12, 29, 38, 44, 57, 64, 98},插入82后变为{12, 29, 38, 44, 57, 64, 82, 98}。
最终排序结果为{12, 29, 38, 44, 57, 64, 82, 98}。
2. 二路归并排序法:
第一趟排序:{98, 44} -> {44, 98};
第二趟排序:{57, 12} -> {12, 57};
第三趟排序:{29, 64} -> {29, 64};
第四趟排序:{38, 82} -> {38, 82};
第五趟排序:{44, 98, 12, 57} -> {12, 44, 57, 98};
第六趟排序:{29, 64, 38, 82} -> {29, 38, 64, 82};
第七趟排序:{12, 44, 57, 98, 29, 38, 64, 82} -> {12, 29, 38, 44, 57, 64, 82, 98}。
最终排序结果为{12, 29, 38, 44, 57, 64, 82, 98}。
注意,二路归并排序法中的每一趟排序是指将两个有序序列合并成一个有序序列的过程。在这个过程中,我们需要开辟一个与原序列同样大小的额外空间来存储归并后的有序序列。
阅读全文