InsertionSort(插入排序)原理及C++代码实现
2020-01-14 16:01:00来源:博客园 阅读 ()
InsertionSort(插入排序)原理及C++代码实现
插入排序是最常用的排序之一。
在输入规模较小的时候,插入排序的性能较好。
最好情况下插入排序的时间复杂度是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
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- C++冒泡排序 (基于函数模板实现) 2020-05-31
- 排序汇总 2020-05-05
- 二叉排序树 2020-05-02
- 排序算法之快速排序代码c++ 2020-04-01
- tmp 2020-04-01
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash