python排序算法-插入排序

文章目录

• 原理
• 动图演示
• 二、代码
• • 1.插入排序
• 总结

原理

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

动图演示

二、代码

1.插入排序

代码如下（示例）：

def insertion_sort(nums):
    """
    :param nums: 无序数组
    :return:
    """
    for i in range(1, len(nums)):
        for j in range(i, 0, -1):
            print(j, nums[j], nums[j - 1])
            if nums[j] < nums[j - 1]:
                nums[j], nums[j - 1] = nums[j - 1], nums[j]
            else:
                break
            print(nums)
    return nums


if __name__ == '__main__':
    arr = [12, 11, 13, 5, 6]
    insertion_sort(arr)
    print("排序后的数组:", arr)
           

时间复杂度：

O(n2)。

总结

工作随笔，希望可以帮助到大家！

如有不足之处，请多多指教！