Question

设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）

Answer 1

问：设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（ ）

答：答案是：45,20,15,50

问：为啥

答：因为希尔排序是一种插入排序，它的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。在第一趟排序中，d=4，则可以将数据分成4组，每组4个数据，分别为：50,40,95,20；15,70,60,45。按照插入排序的思想，每组数据进行排序，可以得到每组排序后的结果：40,50,20,95；15,45,60,70。因此，以增量d=4的一趟希尔排序结束后前4条记录关键字为：45,20,15,50。