#include<stdio.h>
void Print(int array[],int len){
	for(int i=0;i<len;i++){
		printf("%d ",array[i]);
	}
	printf("\n");
} 
/*直接插入排序*/
/*
*算法描述：
*1.將待排序序列分為兩部分，一部分有序一部分無序
*2.第一個元素為有序序列，從第二個元素到最后為無序序列 
*3.將無序序列中每一個元素依次插入到有序序列的合適位置--從小到大（從大到小） 
*合適的位置：待排序元素大于或等于（小于）該元素 
*/ 
void InsertSort(int array[],int len){
	int i,j;
	//第一個for循環 遍歷無序序列 
	for(i=1;i<len;i++){  //從數組的第二個元素開始依次遍歷無序序列 
	 	int tem = array[i];  //臨時保存將要排序的元素 
	 	//第二個for循環遍歷有序序列 
	 	for(j=i-1;tem<=array[j]&&j>=0;j--){  //將待排序元素依次和有序序列中的元素比較 
	 		//待排序元素 小于 有序序列中當前元素時 將該元素后移
	 		array[j+1] = array[j];
	 	}
	array[j+1] = tem;  //待排序元素 大于 有序序列最后一個元素 直接將該元素插入到有序序列最后 
	}
	printf("\n排序完成!\n\n");
}

main(){ 
	int array[10] = {4,3,10,5,6,7,1,2,8,9} ;
	int len = sizeof(array) / sizeof(int);
	printf("初始序列：\n");
	Print(array,len);
	InsertSort(array,len);
	printf("排序后序列：\n");
	Print(array,len);
}