Question

用折半插入排序算法，解決例1.

Answer 1

思路分析：用折半插入排序法將一新數(shù)據(jù)插入到一有序列中，就是反復運用“折半”思想，尋找新數(shù)據(jù)所在的位置的過程.

解：用折半插入排序法，設計算法步驟如下：

第一步：把新數(shù)據(jù)38與“中間位置”的數(shù)據(jù)26比較，由于38＞26，所以應將38放到26的右邊的一半有序列中，即應放到有序列37，39，46，70中.

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

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

10,13,18,26,37,38,39,46,70

溫馨提示

    有序插入排序法就是先比較兩個數(shù)的大小，再把其余的數(shù)依次進行比較插入到這個數(shù)列中.而折半插入排序法是先將新數(shù)據(jù)與“中間位置”的數(shù)據(jù)進行比較，把原有序列折半，直到確定新數(shù)據(jù)應有的位置.