插入排序

Aristore2024-11-212024-11-22

像是手动整理一副牌。

实践

def InsertionSort(nums): # 像是手动整理一副牌
	nums = nums[:]  # 创建副本，避免修改原始数据
	# 先设第一个数是排序好的，也就是说目前 [0] 是已排序区间
	for i in range(1, len(nums)): # 遍历未排序区间，因此这里是从 1 开始的
		base = nums[i] # 把未排序区间的第一个值定为基准值
		j = i - 1 # j 是已排序区间的最后一个值的位置
		while j >= 0 and nums[j] >= base: # 从右往左遍历已排序区间，当前位置的元素比基准值大就继续向左遍历
			# 将已排序区间中要插入元素的位置右边的元素依次右移一位(腾出一个位置给 base )
			nums[j + 1] = nums[j]
			j -= 1
		nums[j + 1] = base  # 将 base 插入到正确位置，当前 j 的位置是正确位置的前一个位置
	return nums
	
# 测试
sort.test(InsertionSort)

流程图

  graph TD
    Start["Start: Initialize nums as a copy of input"] --> A["Iterate over nums starting from index 1"]
    A --> B["Set base = nums[i]"]
    B --> C["Set j = i - 1"]
    C --> D{"Is j >= 0?"}
    D -->|No| E["Insert base at position j + 1"]
    E --> F["Return sorted nums"]
    D -->|Yes| G{"Is nums[j] >= base?"}
    G -->|No| E
    G -->|Yes| H["Shift nums[j] to nums[j + 1]"]
    H --> I["Decrement j"]
    I --> D