void InsertionSort(int a[],int len); /* 算法: */
//由小到大的直接插入排序 direct insertionsort
void InsertionSort(int a[],int len) { int i,j; int temp; for(i=1;i<len;i++){ //假定序列中第一个元素a[0]有序，对剩余的len-1个元素排序
temp = a[i]; //记录待排序列中的第一个元素
j = i-1; //指向已排好序列的最后一个元素
while(j>=0&&temp<a[j]){ a[j+1] = a[j]; //从右往前依次后移
--j; } a[j+1] = temp; //找到插入位置
} } /*算法分析: time-complexity: 最坏情况,原序列逆序，i{a[1]-->a[n-1]},step{1,2,3,...,n-1} 等差数列求和: (n-1)(1+n-1)/2 = n(n-1)/2,所以时间复杂度为O(n2); 最好情况下,序列有序,内层循环条件始终不成立，时间复杂度为O(n); space-complexity: O(1); 算法稳定. */
