直接插入排序是插入排序的一种，算法简单，适用于数据量小的情况。1. 算法思想 ...
直接插入排序是插入排序的一种，算法简单，适用于数据量小的情况。
1. 算法思想
每次从待排序序列中取出一个元素k，插入到已经排好序的序列A[0...i]中合适的位置。插入时k依次由后向前比较，小于k的元素后移。
2. 时间复杂度
最好情况 O(n)：序列正序有序，只需比较n次，不需移动元素最坏情况 O(n^2)：序列逆序有序，每次插入一个元素均需移动前面的所有元素
3. 空间复杂度 O(1)
就地排序，辅助空间为常数级
4. 稳定性
稳定。将k插入到第一个不大于k的元素之后，不改变同值元素的顺序
5. 代码实现（C语言）
void InsertSort(int *A, int n){ int i, j; int tmp; for (i = 1; i < n; ++i) { j = i; tmp = A[j]; while (j > 0 && tmp < A[j - 1]) { A[j] = A[j - 1]; --j; } A[j] = tmp; }}版权声明
本文仅代表作者观点，不代表百度立场。
本文系作者授权百度百家发表，未经许可，不得转载。
上一篇：个总结人5 下一篇：虚拟机扩容手把手教学
