设待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18}, 试分别写出使用以下排序方法，每趟排序结束后

设待排序的关键字序列为{12,2,16,30,28,10,16*,20,6,18}, 试分别写出使用以下排序方法，每趟排序结束后关键字序列的状态。
（1）直接插入排序
（2）希尔排序（增量选取 5、 3 和 1)
【正确答案】：【答案】
（1）直接插入排序
第一趟：[2 12] 16 30 28 10 16* 20 6 18
第二趟：[2 12 16] 30 28 10 16* 20 6 18
第三趟：[2 12 16 30] 28 10 16* 20 6 18
第四趟：[2 12 16 28 30] 10 16* 20 6 18
第五趟：[2 10 12 16 28 30] 16* 20 6 18
第六趟：[2 10 12 16 16* 28 30] 20 6 18
第七趟：[2 10 12 16 16* 20 28 30] 6 18
第八趟：[2 6 10 12 16 16* 20 28 30] 18
第九趟：[2 6 10 12 16 16* 18 20 28 30]
（2）希尔排序
第一趟：10 2 16 6 18 12 16* 20 30 28 （增量选取 5）
第二趟：6 2 12 10 18 16 16* 20 30 28 （增量选取 3）
第三趟：2 6 10 12 16 16* 18 20 28 30 （增量选取 1）
解析：直接插入排序：将无序区的数据以此插入到有序表当中。
希尔排序，按照给定增量分组，在每个组中进行直接插入排序。