Question

試用直接插入排序方法將下面一列無序數(shù)據(jù)按照從大到小的順序進行排序，然后再用折半插入排序法，將6插入到上面排好的有序列中.

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

Answer 1

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

第一步：7  1      （前兩個數(shù)7，1排成有序列）

第二步：7  3  1    （第3個數(shù)3按要求插入到已排好的有序列中）

第三步：12  7  3  1    （第4個數(shù)12按要求插入到已排好的有序列中）

第四步：12  8  7  3  1    （第5個數(shù)8按要求插入到已排好的有序列中）

第五步：12  8  7  4  3  1    （第6個數(shù)4按要求插入到已排好的有序列中）

第六步：12  9  8  7  4  3  1    （第7個數(shù)9按要求插入到已排好的有序列中）

第八步：12  10  9  8  7  4  3  1    （第8個數(shù)10按要求插入到已排好的有序列中）

這時各數(shù)的順序就是符合要求的最終順序.

用折半插入排序法，將新數(shù)據(jù)6插入到上面的有序列中，算法步驟設計如下：

第一步：把新數(shù)據(jù)6與“中間位置”的數(shù)據(jù)8比較，由于6＜8，所以應將6放到8的右邊的一半有序列中，即應放到有序列7，4，3，1中.

第二步：把6與有序列7，4，3，1“中間位置”的數(shù)據(jù)4比較，由于4＜6，所以應將6放到4的左邊的一半有序列中，即應放到有序列7，4中.

第三步：把6與有序列7，4“中間位置”的數(shù)據(jù)7比較，由于7＞6，所以應將6放到7的右邊的一半有序列中，至此排序完成，得到一新的有序列

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