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