軟考軟件設(shè)計(jì)師專題講義九：數(shù)據(jù)結(jié)構(gòu)相關(guān)算法

　　折半插入排序算法分析：

　　直接插入排序的基本操作是向有序表中插入一個(gè)記錄，插入位置的確定通過(guò)對(duì)有序表中記錄按關(guān)鍵碼逐個(gè)比較得到的。平均情況下總比較次數(shù)約為n2/4。既然是在有序表中確定插入位置，可以不斷二分有序表來(lái)確定插入位置，即一次比較，通過(guò)待插入記錄與有序表居中的記錄按關(guān)鍵碼比較，將有序表一分為二，下次比較在其中一個(gè)有序子表中進(jìn)行，將子表又一分為二。這樣繼續(xù)下去，直到要比較的子表中只有一個(gè)記錄時(shí)，比較一次便確定了插入位置。

　　二分判定有序表插入位置方法：

　　① low=1;high=j-1;r[0]=r[j]; // 有序表長(zhǎng)度為j-1，第j個(gè)記錄為待插入記錄

　　//設(shè)置有序表區(qū)間，待插入記錄送輔助單元

　�、� 若low>high，得到插入位置，轉(zhuǎn)⑤

　　③ low≤high，m=(low+high)/2; // 取表的中點(diǎn)，并將表一分為二，確定待插入?yún)^(qū)間*/

　　④ 若r[0].key

　　否則，low=m+1; // 插入位置在高半?yún)^(qū)

　　轉(zhuǎn)②

　�、� high+1即為待插入位置，從j-1到high+1的記錄，逐個(gè)后移，r[high+1]=r[0];放置待插入記錄。

　　【算法10.3】

　　void InsertSort(S_TBL *s)

　　{ /* 對(duì)順序表s作折半插入排序 */

　　for(i=2;i<=s->length;i++)

　　{ s->elem[0]=s->elem[i]; /* 保存待插入元素 */

　　low=i;high=i-1; /* 設(shè)置初始區(qū)間 */

　　while(low<=high) /* 該循環(huán)語(yǔ)句完成確定插入位置 */

　　{ mid=(low+high)/2;

　　if(s->elem[0].key>s->elem[mid].key)

　　low=mid+1; /* 插入位置在高半?yún)^(qū)中 */

　　else high=mid-1; /* 插入位置在低半?yún)^(qū)中 */

　　}/* while */

　　for(j=i-1;j>=high+1;j--) /* high+1為插入位置 */

　　s->elem[j+1]=s->elem[j]; /* 后移元素，留出插入空位 */

　　s->elem[high+1]=s->elem[0]; /* 將元素插入 */

　　}/* for */

　　}/* InsertSort */

　　【時(shí)間效率】

　　確定插入位置所進(jìn)行的折半查找，關(guān)鍵碼的比較次數(shù)至多為 ，次，移動(dòng)記錄的次數(shù)和直接插入排序相同，故時(shí)間復(fù)雜度仍為O(n2)。是一個(gè)穩(wěn)定的排序方法。

　　　　　　　計(jì)算機(jī)軟考軟件設(shè)計(jì)師練習(xí)試題及答案解析匯總