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;
}