1.表插入排序只是求得一個有序的鏈表，它是修改指針的值來代替移動記錄，操作過程如下
2.但是這樣只能進行順序查找，不能進行隨機查找，為了能實現有序表的折半查找，需要對記錄進行重新排列。操作過程如下：
3.測試程序如下：
#include<iostream> #include<cstring> #include<algorithm> #include<cstdio> using namespace std; typedef struct xxx{int head;//頭結點 int a[100];int next[100];//記錄下一個元素的位置 int len;xxx(){head = 1;memset(next, 0, sizeof(next));}void outList(){for(int i=1; i<=len; ++i){cout<<a[i]<<" ";}cout<<endl;} }Listx; Listx Lx;void table_insertion_sort(){//表插入排序，相當于靜態鏈表 for(int i=2; i<=Lx.len; ++i){int pre, p;for(p=Lx.head; p && Lx.a[p]<Lx.a[i]; pre=p, p=Lx.next[p]);if(p==0){Lx.next[pre] = i;} else if(p==Lx.head){Lx.next[i] = Lx.head;Lx.head = i;} else {Lx.next[pre] = i;Lx.next[i] = p;} }//輸出for(int i=Lx.head; i; i = Lx.next[i]) cout<<Lx.a[i]<<" ";cout<<endl; }void arrang_table() {int p = Lx.head, q;for(int i=1; i<Lx.len; ++i){while(p < i) p = Lx.next[p];//第i個記錄在表中的位置不應該小于 i，如果小于i，說明該元素已經被交換位置了，可以通過next繼續尋找 q = Lx.next[p];//指向下一個節點 if(p!=i){//第p個元素應該在第i個位置 swap(Lx.a[i], Lx.a[p]);swap(Lx.next[i], Lx.next[p]);Lx.next[i] = p;//該元素之前的位置 p，指向被移走的記錄，使得以后可由while循環找回 }p = q;}for(int i=1; i<=Lx.len; ++i) cout<<Lx.a[i]<<" ";cout<<endl; }int main() {int i;scanf("%d", &Lx.len);for(i=1; i<=Lx.len; i++)scanf("%d", &Lx.a[i]);table_insertion_sort();arrang_table();return 0; }
?
)
