插入排序与希尔排序

插入排序（Insertion-Sort）是一种简单直观的 排序 算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

操作步骤：

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）。

示例，动图演示：

Python 实现

def insertion_sort(nums):
    for i in range(len(nums)):
        tmp = nums[i]
        index = i
        while index > 0 and nums[index-1] > tmp:
            nums[index] = nums[index-1]
            index -= 1
        nums[index] = tmp
        print(nums)

时间复杂度

• 平均时间复杂度：O(n**2)。
• 最优时间复杂度：O(n)。
• 最坏时间复杂度：O(n**2)。
• 空间复杂度：O(1)。
• 稳定性：稳定。

希尔排序

基本思路

递减增量排序算法，对 插入排序 的改进，实质是分组插入排序，又叫 缩小增量排序 。 希尔排序 提升排序的奥秘就在于 数据元素越有序，使用插入排序效率越高 。

操作步骤：

插入排序
插入排序

示例，动图演示：

Python 实现

def shell_sort(nums):
    step = len(nums) // 2
    while step:
        for i in range(step, len(nums)):
            print(i)
            while i >= step and nums[i - step] > nums[i]:  # 子序列执行插入排序
                nums[i], nums[i - step] = nums[i - step], nums[i]
                i -= step
        step = step // 2
    return nums