插入排序

插入排序实现的原理是将数组分为已排序和未排序两部分，比如现在有数组[2, 5, 4, 3, 6, 1]。

首先将数组分为两部分
已排序：2
未排序：5, 4, 3, 6, 1

然后从未排序的头部取数据，与已排序的数据依次比较来找到这个数据应该在已排序区间的哪个位置。

代码实现

"""
    插入排序
    Author: xingrui
"""


# 插入排序 - 正序
def insertSortWithAsc(nums: list) -> list:
    length = len(nums)

    for i in range(1, length):
        temp = nums[i]

        j = i - 1
        for j in range(j, -1, -1):
            if temp < nums[j]:
                nums[j + 1] = nums[j]
                j = j - 1
            else:
                break

        nums[j + 1] = temp

    return nums


# 插入排序 - 逆序
def insertSortWithDesc(nums: list) -> list:
    length = len(nums)

    for i in range(1, length):
        temp = nums[i]

        j = i - 1
        for j in range(j, -1, -1):
            if temp > nums[j]:
                nums[j + 1] = nums[j]
                j = j - 1
            else:
                break

        nums[j + 1] = temp

    return nums


if __name__ == "__main__":
    nums = [4, 5, 2, 2, 1, 6]

    insertSortWithAsc(nums)
    print('插入排序，正序排列', nums)

    insertSortWithDesc(nums)
    print('插入排序，逆序排列', nums)

插入排序与冒泡排序比较

插入排序和冒泡排序的最好和最坏时间复杂度都分别是和，同时空间复杂度都是O(1)。但是在数据很大的时候，插入排序和冒泡排序还是有很大区别的。

冒泡排序在数据交换的时候，需要一个一个临时值，并且要将相邻的两个元素重新赋值，因为在数据很大的时候，多两次赋值操作可能会造成性能上巨大的不同。

我生成了一个长度一万的随机数组

"""
    数字工具
    Author: xingrui
"""
import numpy as np

# 生成随机数组
def randomArray() -> list:
    return np.random.randint(50, size = 10000)


if __name__ == "__main__":
    print(randomArray())

然后分别用冒泡排序和插入排序对和这个数组进行排序并计算耗时：

"""
    测试
    Author: xingrui
"""

from NumberUtils import randomArray
from BubbleSort import bubbleSortWithAsc
from InsertSort import insertSortWithAsc
import time
import copy


if __name__ == "__main__":
    array = randomArray()
    a, b = copy.deepcopy(array), copy.deepcopy(array)
    print(array)

    start = time.time()
    print('冒泡排序： ', bubbleSortWithAsc(a))
    print('冒泡排序耗时： ', time.time() - start)

    start = time.time()
    print('插入排序： ', insertSortWithAsc(b))
    print('插入排序耗时： ', time.time() - start)

最终的耗时如下：

排序耗时

可以看到，在数据规模很大的情况下，使用插入排序要比冒泡排序耗时更短。当然，这可能和机器有关系，我使用的是win10，内存8g的电脑，unix系统上没有试过，所以这个结论并不严谨。

文章参考

https://visualgo.net/en/sorting
https://www.cnblogs.com/q735613050/p/7253073.html
https://www.jianshu.com/p/a0aa94ef8ab2/
https://www.zhihu.com/question/24613226
https://blog.csdn.net/tiange_xiao/article/details/80808081