【算法】插入排序 Insert Sort

算法介绍

插入排序，依次取数组元素，与已排序的数据进行逐一比较，找到该元素的合适位置，放下该元素，直到完成排序。

视频演示

视频地址：https://www.bilibili.com/video/av18980488

python代码

#-*- coding: utf-8 -*-

# 升序
def insert_sort(data):
    n = len(data)
    # 外循环，依次拿出第 i 个数
    for i in range(1, n):
        cur_data = data[i]
        j=i-1
        # 内循环， 在已排序的数据中，找出当前数应该放的位置
        while j>=0 and cur_data<data[j]:
            data[j+1]=data[j] # 将大的数依次往后挪一位，为当前数腾位置
            j-=1
        data[j+1]=cur_data
    return data

if __name__ == '__main__':
    data = [7, 8, 5, 2, 4, 6, 3]
    sorted_data = insert_sort(data.copy())
    print("排序前：", data)
    print("排序后：", sorted_data)

算法分析

最好情况下，数据刚好是升序，比较次数为 n-1 , 挪动次数为 0;
最坏情况下，数据刚好是降序，比较次数为 n*(n-1)/2， 挪动次数为 n*(n-1)/2.

插入排序时间复杂度为：O(n^2)

插入排序空间复杂度：O(1)