InsertionSort（插入排序）原理及C++代码实现

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了InsertionSort（插入排序）原理及C++代码实现，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含605字，纯文字阅读大概需要1分钟。

内容图文

插入排序是最常用的排序之一。

在输入规模较小的时候，插入排序的性能较好。

最好情况下插入排序的时间复杂度是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 }

注：指针需要支持随机访问

内容总结

以上是互联网集市为您收集整理的InsertionSort（插入排序）原理及C++代码实现全部内容，希望文章能够帮你解决InsertionSort（插入排序）原理及C++代码实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---