Question

试用直接插入排序方法将下面一列无序数据按照从大到小的顺序进行排序，然后再用折半插入排序法，将6插入到上面排好的有序列中.

7，1，3，12，8，4，9，10

Answer 1

解：用有序列插入法排序，过程如下：

第一步：7  1      （前两个数7，1排成有序列）

第二步：7  3  1    （第3个数3按要求插入到已排好的有序列中）

第三步：12  7  3  1    （第4个数12按要求插入到已排好的有序列中）

第四步：12  8  7  3  1    （第5个数8按要求插入到已排好的有序列中）

第五步：12  8  7  4  3  1    （第6个数4按要求插入到已排好的有序列中）

第六步：12  9  8  7  4  3  1    （第7个数9按要求插入到已排好的有序列中）

第八步：12  10  9  8  7  4  3  1    （第8个数10按要求插入到已排好的有序列中）

这时各数的顺序就是符合要求的最终顺序.

用折半插入排序法，将新数据6插入到上面的有序列中，算法步骤设计如下：

第一步：把新数据6与“中间位置”的数据8比较，由于6＜8，所以应将6放到8的右边的一半有序列中，即应放到有序列7，4，3，1中.

第二步：把6与有序列7，4，3，1“中间位置”的数据4比较，由于4＜6，所以应将6放到4的左边的一半有序列中，即应放到有序列7，4中.

第三步：把6与有序列7，4“中间位置”的数据7比较，由于7＞6，所以应将6放到7的右边的一半有序列中，至此排序完成，得到一新的有序列

12，10，9，8，7，6，4，3，1