54 lines
1.5 KiB
Python
54 lines
1.5 KiB
Python
|
"""
|
|||
|
|
插入排序：插入数据项来实现排序，始终在数据集的较低位置处维护一个有序的子序列，然后
|
|||
|
|
将新项插入子序列，使得子序列扩大，最终实现集合排序
|
|||
|
|
|
|||
|
|
1. 假设开始的子序列只有一项，位置为 0
|
|||
|
|
2. 对于项 1 至 n-1，从后往前遍历前面的所有项，
|
|||
|
|
3. 比较过程中，每个大于当前项的项，将其值赋值到后一项，相当于往后挪一位
|
|||
|
|
直到找到小于等于当前项的位置，并这个位置的值改为当前项
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
def insert_sort(nums: list[int]):
|
|||
|
|
for i in range(1, len(nums)):
|
|||
|
|
pos = i
|
|||
|
|
cur = nums[i]
|
|||
|
|
|
|||
|
|
while pos > 0 and cur < nums[pos - 1]:
|
|||
|
|
# 将比当前值大的往后移一位
|
|||
|
|
nums[pos] = nums[pos - 1]
|
|||
|
|
pos -= 1
|
|||
|
|
nums[pos] = cur
|
|||
|
|
|
|||
|
|
|
|||
|
|
"""
|
|||
|
|
插入排序优化：由于子序列是已经排序好的序列，所以在插入时可以使用二分查找，
|
|||
|
|
快速地在子序列中找到插入的位置
|
|||
|
|
"""
|
|||
|
|
|
|||
|
|
|
|||
|
|
def bin_insert_sort(nums: list[int]):
|
|||
|
|
for i in range(1, len(nums)):
|
|||
|
|
pos = i
|
|||
|
|
cur = nums[i]
|
|||
|
|
low = 0
|
|||
|
|
high = pos - 1
|
|||
|
|
|
|||
|
|
while low < high:
|
|||
|
|
mid = (low + high) >> 1
|
|||
|
|
if cur > nums[mid]:
|
|||
|
|
low = mid + 1
|
|||
|
|
else:
|
|||
|
|
high = mid - 1
|
|||
|
|
|
|||
|
|
for j in range(i, low, -1):
|
|||
|
|
nums[j] = nums[j - 1]
|
|||
|
|
|
|||
|
|
if nums[low] > cur:
|
|||
|
|
nums[low] = cur
|
|||
|
|
else:
|
|||
|
|
nums[low + 1] = cur
|
|||
|
|
|
|||
|
|
nums = [47, 29, 71, 99, 78, 19, 24, 47]
|
|||
|
|
bin_insert_sort(nums)
|
|||
|
|
print(nums)
|