插入排序是最常用的排序之一。
在输入规模较小的时候，插入排序的性能较好。
最好情况下插入排序的时间复杂度是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 }
注：指针需要支持随机访问
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/600396.html