排序和查找
二分查找
def binary_search(lst, n):
"""返回最左侧插入点位置"""
# 左闭右开区间
left, right = 0, len(lst)
while left < right:
mid = left + (right - left)//2
if lst[mid] == n:
right = mid # 区间向左侧收缩
elif lst[mid] > n:
right = mid # 因为是开区间, 所以这里不用-1
elif lst[mid] < n:
left = mid + 1
return right # left == right
冒泡排序
def bubble_sort(lst):
# 轮次, 最后一个不需要
for i in range(len(lst)-1):
swapped = False
# 末尾的已有序
for j in range(len(lst)-1-i):
if lst[j] > lst[j+1]:
swapped = True
lst[j], lst[j+1] = lst[j+1], lst[j]
# 提前结束
if not swapped:
break
选择排序
def find_least(lst, start=0):
least_idx = start
for k in range(start+1, len(lst)):
# 比 start 小, 但要遍历完全部才能找到最小
if lst[k] < lst[least_idx]:
least_idx = k
return least_idx
def selction_sort(lst):
for i in range(len(lst) - 1):
least = find_least(lst, i)
if least != i:
lst[least], lst[i] = lst[i], lst[least]
return lst
插入排序
def insertion_sort(lst, gap=1):
# 假定第一个元素有序
for i in range(gap, len(lst)):
# 保存待处理的元素
target = lst[i]
# 从 i-1 开始逆序到 0
j = i - gap
while j >= 0 and target < lst[j]:
# 重点: 腾挪位置
lst[j+gap] = lst[j]
j -= gap
# 在目标位置插入(注意是 +1)
lst[j+gap] = target
希尔排序
def shell_sort(lst):
gap = len(lst)//2
# 外循环是 gap 序列
while gap > 0:
# 插入排序
insertion_sort(lst, gap)
gap = gap//2
归并排序
def merge(arr, l, m, r):
# 对列表的左右两部分进行归并
i, j, k = l, m+1, l
# 左右两个子列表均还有值
while i <= m and j <= r:
if arr[i] < arr[j]:
i += 1
else:
val, idx = arr[j], j
# 挪位置
while idx != i:
arr[idx] = arr[idx-1]
idx -= 1
# 插入到 i 位置
arr[i], i, j = val, i+1, j+1
return arr
def merge_sort(arr, l, r):
if l < r:
m = (l+r) // 2
merge_sort(arr, l, m)
merge_sort(arr, m+1, r)
merge(arr, l, m, r)
快速排序
Hoare-Partition
def quick_sort(lst, left, right):
if left < right:
pivot = lst[left] # 选择首元素为基准
i, j = left, right
while i < j:
# 从右边找比基准小的
while pivot <= lst[j] and i<j:
j -= 1
# 从左边找比基准大的
while pivot >= lst[i] and i<j:
i += 1
if i < j:
lst[i], lst[j] = lst[j], lst[i]
# 把基元换到中间 i==j 的位置
lst[left], lst[i] = lst[i], lst[left]
# 对基元左右两边的列表进行递归处理
quick_sort(lst, left, i-1)
quick_sort(lst, i+1, right)
Lomuto-Partition
def quick_sort(array, l, r):
if l < r:
q = partition(array, l, r)
quick_sort(array, l, q - 1)
quick_sort(array, q + 1, r)
def partition(array, l, r):
# 将末尾元素设为基元
x = array[r]
i = l - 1
for j in range(l, r):
if array[j] <= x:
i += 1
# 交换 i、j 对应的元素
array[i], array[j] = array[j], array[i]
array[i + 1], array[r] = array[r], array[i+1]
return i + 1
堆排序
def max_heapify(arr, start, end):
"""
维护最大堆
"""
dad = start
son = dad * 2 + 1
while son <= end:
# 选择两个孩子节点中值较大的节点
if son + 1 <= end and arr[son] < arr[son+1]:
son += 1
# 如果父节点小于子节点，则交换
if arr[dad] < arr[son]:
arr[dad], arr[son] = arr[son], arr[dad]
# 继续递归向下维护最大堆
dad = son
son = dad * 2 + 1
else:
return
def heap_sort(arr):
# 建立最大堆
for i in range(len(arr) // 2, -1, -1):
max_heapify(arr, i, len(arr) - 1)
# 将最大数放到末尾，并递归调用维护最大堆
for i in range(len(arr) - 1, 0, -1):
arr[0], arr[i] = arr[i], arr[0]
max_heapify(arr, 0, i - 1)
return arr