2.插入排序（斗地主起牌）

一、思想 

扑克牌起牌

代码：

二、时间复杂度：

最好情况（已经排序好的）：T = O(N)

最坏情况（完全逆序）：T = O(N^2)

三、优劣：

严格的大小比较之后才进行错位插入，具有稳定性。

四、代码实现：

#include<stdio.h>
typedef int ElementType;
void Insertion_Sort(ElementType A[] , int N)
{int i,P;for(P = 1;P<N;P++){ElementType temp = A[P];//模下一张牌 for(i=P;i>0&&A[i-1]>temp;i--){A[i] = A[i-1];//往后错位 }A[i] = temp;//新牌落位 }
}
void display(ElementType x[]){int i;for(i=0;i<10;i++){printf("%d\n",x[i]);}
}
int main(){ElementType A[10] = {0,9,4,5,3,2,8,7,1,6};Insertion_Sort(A,10);display(A);return 0;
}