插入排序：表插入

所謂插入排序之表排序，是利用靜態鏈表的形式，分兩步完成排序。

一，對一個有序的循環鏈表，插入一新的元素，修改每個節點的後繼指針的指向，使順著這個指針的指向，元素是有序的。在這個過程中，我們不移動或交換元素，只是修改指針的指向。

二，順著指針的指向調整元素的位置，使其在鏈表中真正做到物理有序。

思路：

構建一新的結構體類型，使其封裝了值域和指針域。並增加一節點，當做頭節點，為循環終止創造條件，頭節點值域存貯的值應不小於原序列中的最大值。初始化靜態鏈表：使第一個節點和頭節點構成循環的鏈表。由於鏈表中只有一個元素，那當然是有序的。把後續的節點依次插入到該循環鏈表中，調整各節點的指針指向，使其沿著指針方向是有序的。
關鍵代碼：

const int MAX = 1000;    //這裡的最大值，應設置好 
typedef struct rec   //Record 靜態鏈表的節點類型 
{
	int data;
	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 = 0;
	}
	rec[0].data = MAX;
	rec[0].next = 1;    //頭節點和第一個節點構成了循環鏈表 
	int p, q;
	for (int i = 2; i < n + 1; i++)
	{
		q = 0;
		p = rec[q].next;    //p指向當前待比較的節點，q指向前一個
		while (rec[i].data >= rec[p].data)     // >= 保證了排序的穩定性 
		{
			q = p;
			p = rec[q].next;
		}
		rec[i].next = p;
		rec[q].next = i;
	}
	p = rec[0].next;
	int i=0;
	while(p!=0)  //順著靜態鏈表的指針指向，回寫數據到原數組 
	{
		a[i++]=rec[p].data;
		p=rec[p].next;
	}
	delete[]rec;   //釋放空間 
}

小結： 說它是插入排序，是因為，每次都是把一個新的數據插入到原本有序的序列中，並且是從序列的頭部開始比較。 大家測試下，看是否有問題。 p.s 也可以把靜態鏈表也調整成物理有序的，比較簡單，大家先想下，後續補上。