排序算法—插入排序之直接插入排序

直接插入排序就是從無序區，依次取出一個資料，通過大小比較，插入到有序區，直到資料全部有序為止。

下面是我對直接插入排序過程的一種了解，就像排序 撲克牌中的順子一樣：

首先假設你手中有 5 張撲克牌，依次是：4，2，5，3，1。

a.把牌背面面向你，現在你不清楚牌裡面的數字。

b.從 左向右 翻一張牌  （現在，數字4 就是我們的有序區）

4  X X X X

c. 現在我們從 左向右 再翻開一張牌 它的名字叫 "card"（是數字 2）。

4 2 X X X

d. 把 card 和 有序區 的牌，從右向左， 依次進行大小比較，規則如下： 

規則一：如果 card 不 小于 有序區左鄰的第一張牌（因為有序區 有序，是以card 不會小于 有序區任一張牌） ，則繼續去下一張牌；

規則二：如果 "card"小于有序區 的某張牌 B，就把 card 取出來，card的位置就空了出來；

然後把有序區 從牌 B（包括B)到末尾的全部牌右移一個位置（上面空位置消失），B的位置就空了出來；

最後把 card 放在 空的位置；

可見 2 < 4  ，那就把 2 抽出來 ，2的位置空了出來

4 _X X X

把 4 移到2的位置，4的位置空了出來

_ 4 X X X

最後把 2 放在空的位置

2 4 X X X

e. 重複 步驟 c -d :

翻牌：

2 4 5 X X 

比較并插入：（符合規則一）

2 4 5 X X

翻牌：

2 4 5 3 X

比較并插入：（符合規則二）

2 4 5 _ X

2 _ 4 5 X

2 3 4 5 X

翻牌：

2 3 4 5 1

比較并插入：（符合規則二）

2 3 4 5 _

_ 2 3 4 5

1 2 3 4 5

排序完成

我的排序代碼如下：

void insertsort(int a[],int n)
{
	int i =0;
	int j =0;

	int flag = 0;  //儲存和有序區 比較的那個數字
	for(i =1;i<n;i++)//從第二個開始,第一個數作為有序區
	{
		flag =  a[i];
		for(j = i;j>0&&a[j-1]> flag;j--)
		{
			a[j] = a[j-1]; //向右移動有序區
		}
		a[j] = flag; //把數字 插入有序區
	}
}