侧边栏壁纸
  • 累计撰写 247 篇文章
  • 累计创建 16 个标签
  • 累计收到 0 条评论

目 录CONTENT

文章目录

插入排序

kaixindeken
2021-04-19 / 0 评论 / 0 点赞 / 93 阅读 / 692 字

实现原理

插入排序的原理是:我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。

如下图所示:

1.png

在这里搭配动态图查看效果更佳:https://visualgo.net/zh/sorting。

示例代码

插入排序也比较简单,实现代码如下:

void insertionSort(int a[], int N) {
  for (int i = 1; i < N; ++i) { // O(N)
    int X = a[i]; // X is the item to be inserted
    int j = i-1;
    for (; j >= 0 && a[j] > X; --j) // can be fast or slow
      a[j+1] = a[j]; // make a place for X
    a[j+1] = X; // index j+1 is the insertion point
  }
}

性能分析

  • 插入排序需要两个嵌套的循环,时间复杂度是O(n2);
  • 没有额外的存储空间,是原地排序算法;
  • 不涉及相等元素位置交换,是稳定的排序算法。

插入排序的时间复杂度和冒泡排序一样,也不是很理想,但是插入排序不涉及数据交换,从更细粒度来区分,性能要略优于冒泡排序。

0

评论区