? ? 在前一篇插入排序：表插入中。我們用靜態鏈表的存儲方式。直接插入的策略，構建了一種新的插入排序算法：表插入。
有人可能會想到：相同是靜態鏈表的形式，為什么不使用更高效的折半插入策略呢？這樣的想法真的非常好，假設做到了。顯然是極大的優化。
? ? 我在網上還真看到了相關的內容，大家可搜下《表插入方法的改進》，里面有此想法的介紹。這篇博客就是介紹表插入的還有一種實現：表折半插入。看完一定讓你徹底理解它！
與一般的折半插入相比，有例如以下的幾點變化：
- 為了實現折半查找，我們對靜態鏈表的節點類型做了一些變化：加入了一個前驅指針。
它的意義非常顯然，曾經是high=mid-1，在單向鏈表中我們是做不到的(事實上能夠換種方式做到，只是相對麻煩)，于是加入一指向其前驅的指針。構成雙向鏈表，方便進行此操作。
- while循環的結束條件，有所不同。這個要細致理解！
其它細節，代碼中有詳解
const int MAX=100;
typedef struct rec
{int data;int pre; //前驅 int next; //后繼
}Rec;
void InsertSort(int a[], int n) //表折半插入
{Rec *rec=new Rec[n+1];for(int i=0; i<n; i++){rec[i+1].data=a[i];rec[i+1].next=rec[i+1].pre=0;}rec[0].data=MAX;rec[0].next=rec[0].pre=1;int low,high,mid;int p,k,l;for(int i=2; i<n+1; i++){//依據下面的賦值，我們能夠看出。這里使用的是左閉右閉區間 low=rec[0].next; //low指向最小的 high=rec[0].pre; //high指向最大的 l=i-1; //已有序的元素個數 while(low!=0 && high!=0 && rec[low].data<=rec[high].data) //循環結束條件得理解，特別是前兩個條件。準確的是。第一個條件能夠不要 { mid=low; k=1; l/=2; // l>>=2 減半。為下次循環做好準備 while(k<l) //尋找mid位置 { mid=rec[mid].next; k++; } if(rec[i].data<rec[mid].data) high=rec[mid].pre; else low=rec[mid].next; } //插入第i個節點。相似于雙向鏈表的插入 rec[rec[low].pre].next=i; rec[i].pre=rec[low].pre; //加入前驅指針的作用體如今這里 rec[i].next=low; rec[low].pre=i; } //順著next指針方向打印 printf("表折半插入排序后\n"); p=rec[0].next; while(p!=0) { printf("%-4d",rec[p].data); p=rec[p].next; } printf("\n"); }
細致看完代碼，我想大多數人僅僅剩一個問題可能沒明確，那就是while循環的結束條件為什么還得加上low!=0 和high!=0？
為了解釋清楚。我們畫一個圖，圖中正在插入i=2的節點：
初始化后。low,mid,high顯然都指向1，經過下一步rec[i].data與rec[mid].data比較后，不管結果如何，循環都應結束。
可假設
rec[i].data<rec[mid].data,就有high=rec[mid].pre,即high=1.此時顯然有rec[low]<rec[high],也就是說循環還得接著經進行下去。問題就出在這里！講到這里，你應該明確：即使出現low為0,它也會違反第三條件：rec[low].data<=rec[high].data)(由于rec[0]的值域是最大的)。這就是為什么說，第一個條件low!=0能夠去掉。到此。你應該明確了代碼中全部的凝視。
測試走起啊……
p.s 對rec數組1-n號元素進行重排也是能夠的，做法參照上一篇博客哦，方法一模一樣。
轉載請注明出處，本文地址：http://blog.csdn.net/zhangxiangdavaid/article/details/28635157
若是寫得好。頂一個哦。
代碼就是折騰，越折騰越進步！
專欄文件夾看這里：
- 數據結構與算法文件夾
- c指針
