【HC】基础算法代码
快速排序:def quick_sort(lst): if not lst: return [] pivot = lst left = quick_sort( if x < pivot]) right = quick_sort( if x >= pivot]) return left + + right1234567归并排序:def merge_sort(lst): if len(lst) <= 1: return lst mid = len(lst) // 2 left = merge_sort(lst[: mid]) right = merge_sort(lst) return merge(left, right) def merge(left, right): l, r, res = 0, 0, [] while l < len(left) and r < len(right): if left <= right: res.append(left) l += 1 else: res.append(right) r += 1 res += left res += right 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 > lst: j += 1 elif temp > lst: break else: lst = lst i, j = j, 2 * j + 1 lst = temp def heap_sort(lst): if lst == []: return [] end = len(lst) for i in range((end // 2) - 1, -1, -1): siftup(lst, lst, i, end) for i in range(end - 1, 0, -1): temp = lst lst = lst 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 > x: end = mid - 1 elif lst < 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 < x: start = mid + 1 else: end = mid - 1 mid = (start+end) // 2 return starthttp://cdn.u1.huluxia.com/g3/M01/38/FC/wKgBOV3JQjGAM724AAB7c6R6rKQ892.jpg
页:
[1]