基础算法代码

快速排序：def quick_sort(lst): if not lst: return [] pivot = lst[0] left = quick_sort([x for x in lst[1: ] if x < pivot]) right = quick_sort([x for x in lst[1: ] if x >= pivot]) return left + [pivot] + right1234567归并排序：def merge_sort(lst): if len(lst) <= 1: return lst mid = len(lst) // 2 left = merge_sort(lst[: mid]) right = merge_sort(lst[mid:]) return merge(left, right) def merge(left, right): l, r, res = 0, 0, [] while l < len(left) and r < len(right): if left[l] <= right[r]: res.append(left[l]) l += 1 else: res.append(right[r]) r += 1 res += left[l:] res += right[r:] return res1234567891011121314151617181920堆排序：def siftup(lst, temp, begin, end): if lst == []: return [] i, j = begin, begin * 2 + 1 while j < end: if j + 1 < end and lst[j + 1] > lst[j]: j += 1 elif temp > lst[j]: break else: lst[i] = lst[j] i, j = j, 2 * j + 1 lst[i] = temp def heap_sort(lst): if lst == []: return [] end = len(lst) for i in range((end // 2) - 1, -1, -1): siftup(lst, lst[i], i, end) for i in range(end - 1, 0, -1): temp = lst[i] lst[i] = lst[0] siftup(lst, temp, 0, i) return lst12345678910111213141516171819202122232425二分查找：# 一般二分查找def binsearch(lst, x): start, end = 0, len(lst)-1 while start<= end: mid = (start+ end) // 2 if lst[mid] > x: end = mid - 1 elif lst[mid] < x: start = mid + 1 else: return True return False# 二分查找第一次出现indexdef binsearch_get_lower(lst, x): start, end = 0, len(lst)-1 mid = (start+end) // 2 while start <= end: if lst[mid] < x: start = mid + 1 else: end = mid - 1 mid = (start+end) // 2 return start