一、基本思想
直接插入排序即是在要排序的数组中，假设前n-1（n>=2）个数已经是排好序的，现在要把第n个数插入到前n个已经排好序的数组中，使得这n个数也变成有序的，如此反复循环，使得要排序的数组中的最后一个元素也排好序。
直接插入排序.png
二、代码实现
void insertsort(int a[],int n)
{
int i,j,temp;
for (i = 1 ;i < n ; i++) {
temp = a[I];//把待排序元素赋给temp，
j = i - 1;
while (j >= 0 && (temp < a[j])) {//循环的作用是将比当前元素大的元素都往后移动一个位置
a[j + 1] = a[j];
j--;
}
a[j+1]=temp;//元素后移后要插入的位置就空出了，找到该位置插入
}
}
时间复杂度为：O（n^2）
注明：本文参考自 [翡翠森林Z的博客]（http://www.jianshu.com/p/1f952b77c6a00B0920080）
网友评论