InsertionSort(插入排序)原理及C++代码实现

2020-01-14 16:01:00来源:博客园 阅读 ()

容器云强势上线!快速搭建集群,上万Linux镜像随意使用

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
如有疑问请与原作者联系

标签:实现for常用理解时间原理

版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有

上一篇:C++ 进程和匿名管道使用学习

下一篇:MergeSort(归并排序)原理及C++代码实现