图解排序算法及实现——插入排序（Insertion Sort）

蔚落 2022-05-14 05:16 215阅读 0赞

插入排序（InsertionSort）可以说是最简单直观的排序算法了。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

通常以扑克牌举例： 右边新来的牌，与左边有序的老牌依次比较，最终插到合适的位置。

# 实现 #

*  Basic： 新旧牌每次都要交换一下（两次操作：旧牌后移一位，新牌前移一位）。 （代码见下面**基础版**）
 *  Advanced： 每次比较，旧牌后移一位（一次操作）。新牌最后放到空位上。 （代码见下面**改进版**）

后者即为通常采用的in-place方式（即只需用到 ***O(1)***的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

# 复杂度 #

平均时间复杂度： **O(n^2)**

最坏时间复杂度： **O(n^2）**  
最优时间复杂度： **O(n)**  
最坏空间复杂度： 总共 **O(n)** ，需要辅助空间 **O(1)**

# 图例 #

推荐[VisuAlgo][]，一个数据结构和算法动态可视化的网站。

![插入排序][Insertion_sort_animation.gif]  
图片来源： 维基百科  
![插入排序][SouthEast]  
图片来源： [【图解算法】排序算法——插入排序][Link 1]

# python实现 #

### 基础版 ###

Basic实现方法: 倒序遍历寻找元素arr\[i\]合适的插入位置

def InsertionSort(arr):
        ''' 
        插入排序思路： （扑克牌举例） 右边新来的牌，与左边有序的老牌依次比较，最终插到合适的位置。
    
        实现：
             Basic：    新旧牌每次都要交换一下（两次操作：旧牌后移一位，新牌前移一位）。 
             Advanced： 每次比较，旧牌后移一位（一次操作）。新牌最后放到空位上。
        '''
    
        n = len(arr)
        for i in range(1,n):        
            for j in range(i,0,-1):
                if arr[j-1]>arr[j]:
                    arr[j],arr[j-1] = arr[j-1],arr[j] # 交换
                else:
                    break

### 改进版 ###

Advanced实现方法： 每次比较，旧牌后移一位（一次操作）。新牌最后放到空位上。  
（上面图例中第二张即直观表示了改进版的排序过程）

def InsertionSort(arr):
    
        n = len(arr)    
        for i in range(1,n):        
            temp = arr[i]
            # j保存元素temp应该插入的位置
            for j in range(i,-1,-1):
                if arr[j-1]>temp and j>0:
                    arr[j] = arr[j-1]  # 后移即可
                else:
                    break
            arr[j] = temp

[VisuAlgo]: https://visualgo.net/zh
[Insertion_sort_animation.gif]: http://bubkoo.qiniudn.com/Insertion_sort_animation.gif
[SouthEast]: /images/20220514/63504ccd552748879998e39d47be3a81.png
[Link 1]: https://blog.csdn.net/xiaoping0915/article/details/72949784