设待排序的关键字序列为(15, 21, 6, 30, 23, 6', 20, 17),若使用希尔排序(增量为5,2,1)方法,需要排序()趟,第二趟的结果为()。(每个关键字以两个空格分隔,单引号为英文状态下的符号, 如:6 23 6' 20 )
时间: 2024-06-05 16:13:06 浏览: 132
常见几种排序方式(选择排序,冒泡排序,快速排序,希尔排序,堆排序,插入排序)
5星 · 资源好评率100%
希尔排序是一种插入排序的高效率版本,通过将待排元素按照一定的间隔进行分组,对每组使用插入排序算法排序,随着间隔逐渐缩小,每组包含的关键字越来越多,当间隔为1时,整个序列被分成一组,算法便终止。
对于给定的序列 (15, 21, 6, 30, 23, 6', 20, 17),我们按照增量序列 (5, 2, 1) 进行排序。首先,增量为5,将序列分成两组:(15, 6', 17) 和 (21, 30, 23, 20, 6)。对每组进行插入排序,得到:
(15, 6', 17) -> (6', 15, 17)
(21, 30, 23, 20, 6) -> (6, 20, 21, 23, 30)
此时,序列变为 (6', 15, 17, 6, 20, 21, 23, 30)。接下来,增量为2,将序列分成5组,对每组进行插入排序,得到:
(6', 17) -> (6', 17)
(15, 20) -> (15, 20)
(6, 21) -> (6, 21)
(23, 30) -> (23, 30)
整个序列,得到:(6', 6, 15, 17, 20, 21, 23, 30)。
最后,增量为1,对整个序列进行插入排序,得到最终的排序结果:(6, 6', 15, 17, 20, 21, 23, 30)。
因此,需要排序3趟,第二趟的结果为:6' 15 6 20 21 23 30。
阅读全文