四、(8 分)对下列数据表，写出采用希尔排序算法排序的每一趟结果。 （100，12，20，31，1，5，44,66，61，200，30，80，150，4，8） 设增量序列为: <tex>d=\{ 5,3,1\} </tex>

首先，我们先使用增量 `d = {5, 3, 1}` 对给定的数据进行希尔排序。

第一趟排序，增量为 5：
初始数据表：100，12，20，31，1，5，44，66，61，200，30，80，150，4，8

按照增量 5 进行分组，得到 5 个子序列：
1. 100，5，150
2. 12，44，4
3. 20，66，8
4. 31，61
5. 1，200，30，80

对每个子序列进行插入排序：
1. 排序后的子序列：5，100，150
2. 排序后的子序列：4，12，44
3. 排序后的子序列：8，20，66
4. 排序后的子序列：31，61
5. 排序后的子序列：1，30，80，200

合并所有子序列得到：5，100，150，4，12，44，8，20，66，31，61，1，30，80，200

第一趟排序结果：5，100，150，4，12，44，8，20，66，31，61，1，30，80，200

第二趟排序，增量为 3：
上一趟排序结果：5，100，150，4，12，44，8，20，66，31，61，1，30，80，200

按照增量 3 进行分组，得到 3 个子序列：
1. 5，4，8，1
2. 100，12，20，30
3. 150，44，66，80，31，61，200

对每个子序列进行插入排序：
1. 排序后的子序列：1，4，5，8
2. 排序后的子序列：12，20，30，100
3. 排序后的子序列：31，44，61，66，80，150，200

合并所有子序列得到：1，4，5，8，12，20，30，100，31，44，61，66，80，150，200

第二趟排序结果：1，4，5，8，12，20，30，100，31，44，61，66，80，150，200

第三趟排序，增量为 1：
上一趟排序结果：1，4，5，8，12，20，30，100，31，44，61，66，80，150，200

按照增量 1 进行分组，得到 1 个子序列：
1. 1，4，5，8，12，20，30，100，31，44，61，66，80，150，200

对子序列进行插入排序：
排序后的子序列：1，4，5，8，12，20，30，31，44，61，66，80，100，150，200

第三趟排序结果：1，4，5，8，12，20，30，31，44，61，66，80，100，150，200

最终排序结果：1，4，5，8，12，20，30，31，44，61，66，80，100，150，200