I'll try anything once

人生苦短,何妨一试

插入排序

前言

插入排序的思想很直观,其在性能上不如一些分治的排序策略,例如快速排序,归并排序。插入排序是一种基于比较的排序算法。

算法思想

其类似于打牌的抓牌环节,抓到牌后都会按照点数插入到合适的位置,核心思想是保证一个已排序区间,剩下的未排序区间依次与前面的已排序区间进行比较,插入到对应的位置。

插入

有关于插入,若是序列是使用数组进行存储,则可以从右向左扫描已排序数组,因为这样可以在性能上有所优化。因为对于数组的插入,其不像链表一样,只需要断链,然后链接,其需要移动大量的元素,才能够进行插入,若是从左向右,譬如数组的长度为n,在位置i插入,则需要扫描i次,然后移动n-i+1次,最后插入数据。若是从右向左,最多需要i次扫描,然后可以边扫描边右移动

基本插入算法

  • 复杂度:O(n^2)
  • 比较次数(查找): O(n^2)
  • 移动次数(插入后导致的移动): O(n^2)

优化一: 使用鶸二分查找

因为已经确定了前面的排序区间是有序的,所以可以直接使用二分查找来确定插入的位置,这样查找的时间就得到了优化

  • 复杂度: O(n^2)
  • 比较次数: O(nlgn)
  • 移动次数: O(n^2)

优化二: 为了优化而优化的链表

使用链表之后,数据结构从数组改为链表,优化了插入的时间,由最初的O(n)优化到了O(1)

  • 复杂度: O(n^2)
  • 比较次数: O(n^2)
  • 移动次数: O(1)

优化三: 终极进化之二叉搜索树

对于以上的优化,只能在插入和查找之中二选一的进行优化。单独提高其中一个仍会使插入算法保持在O(n^2)中,使用二分查找能够将查找次数降到最低—O(lgN),对于插入,为了能实现常数时间的插入,必定需要改变其数据结构。
二叉搜索树刚好满足以上的所有的需求,但是对于这个,应该不算是严格意义的插入排序了,应是更宽泛的定位—基于比较的排序。

  • 第一,其本身定义就支持二分查找,
  • 同时查找到对应的值之后,即可插入,所以插入的时间为常数项O(1)。
    总结
  • 复杂度: O(nlgn)
  • 移动次数: O(1)
  • 比较次数 O(lgn)

实现
首先将数据构造为二叉搜索树,之后再进行中序遍历即可。

Reference

  • 算法新解
  • 算法第四版
点赞
  1. coder说道:

    优化没写完哇 :wink:

    1. kongwiki说道:

      更新完了 :idea:

发表评论

电子邮件地址不会被公开。 必填项已用*标注

15 − 2 =