插入排序是最常用的排序之一。
在输入规模较小的时候，插入排序的性能较好。
最好情况下插入排序的时间复杂度是O(n),平均情况则为O(n2)。
插入排序是稳定的排序算法之一。
基本思路为从第二个元素开始，依次插入前面已经排好序的序列，利用循环不变式很容易理解。
代码如下：（仅供参考）
1 void InsertionSort(int * const begin, int * const end) { 2 int i, j; 3 int key; 4 for (i = 1; i < end - begin; ++i) { 5 key = *(begin + i); 6 for (j = i - 1; j >= 0 && (*(begin + j) > key); --j) { 7 *(begin + j + 1) = *(begin + j); 8 } 9 *(begin + j + 1) = key; 10 } 11 }
注：指针需要支持随机访问
原文链接: https://www.cnblogs.com/yxsrt/p/12193568.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/324310
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
