图示
插入排序的基本思想是：对于数组前边部分已经是排好序的了，对于接下来的元素查找其在前面的位置，插入之。如下图中1 2 4 7 已经排好序，接下来找到2的位置，插入到1和3之间。之后同样处理4和9.
参考代码
void insertSort(int A[], int lens) { if (A == NULL || lens <=0) return; for (int i = 1; i < lens; ++i) { for (int j = i-1; j>=0 && A[j] > A[j+1]; --j) swap(A[j], A[j+1]); } }
测试
View Code
复杂度
- 空间复杂度：O(1)
- 时间复杂度
- 最好（已经升序）O(n)
- 最差（已经降序）O(n2)
稳定性
稳定
本文转自jihite博客园博客，原文链接：http://www.cnblogs.com/kaituorensheng/archive/2013/02/24/2925033.html，如需转载请自行联系原作者
