6.3插入排序（python数据结构与算法）

柔情只为你懂 2021-05-12 11:50 476阅读 0赞

**插入排序 Insertion Sort**是一种简单直观的排序算法。

**工作原理**是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

**别和选择排序搞混**

*  选择排序是从后面【乱序】的数中拿一个放在前面【已排好序】的最后位置
 *  插入排序是从后面【乱序】的数中拿一个放在前面【已排好序】的指定位置

![在这里插入图片描述][20200621220547651.gif]

#### 实现： ####

# 方法一
    def insert_sort(alist):
        """插入排序"""
        length = len(alist)
        for iter_num in range(1, length):
            # 取出当前数的索引， 和他前面的元素作比较
            for index in range(iter_num, 0, -1):
                if alist[index] < alist[index-1]:
                    alist[index], alist[index-1] = alist[index-1], alist[index]
                else:  # 代表以排序完毕
                    break
    # 方法二
    # def insert_sort(alist):
    # length = len(alist)
    # for now_index in range(1, length):
    # index = now_index
    # while index > 0:
    # if alist[index] < alist[index-1]:
    # alist[index], alist[index-1] = alist[index-1], alist[index]
    # index -= 1
    # else:
    # break
    
    
    if __name__ == "__main__":
        alist = [54,26,93,17,77,31,44,55,20]
        insert_sort(alist)
        print(alist)

## 时间复杂度 ##

*  最优时间复杂度：O(n) （升序排列，序列已经处于升序状态）
 *  最坏时间复杂度：O( n 2 n^2 n2)
 *  稳定性：稳定

## 插入排序演示 ##

![在这里插入图片描述][20200621220607945.gif]

[20200621220547651.gif]: /images/20210511/4b5cf63c21ba40db81f391a01151d9a1.png
[20200621220607945.gif]: /images/20210511/0f27e1f1a1684ca68d9e03978de9df99.png