插入排序
def insert_sort(list): n = len(list) for i in range(1, n): key = list[i] for j in range(i-1, -1, -1): if list[j] > key: list[j+1], list[j] = list[j], key else: break return list print(insert_sort([3, 2, 5, 1, 4]))
希尔(缩小增量)排序
算法课没有讲希尔排序，所以记录一下其思想和复杂度分析
该方法的基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。
时间复杂度与步长选择有关，最坏情况下 $$ O(n^2) $$
不稳定以 gap 替换插入排序中的 1
def shell_sort(list): n = len(list) gap = n // 2 while gap > 0: for i in range(gap, n, gap): key = list[i] for j in range(i-gap, -1, -gap): if key < list[j]: list[j+gap], list[j] = list[j], key else: break gap //= 2 return list
快排
def quick_sort(list, left, right): if left >= right: return list key = list[right] high = right - 1 low = left while low <= high: if list[low] > key: list[low], list[high] = list[high], list[low] high -= 1 else: low += 1 list[low], list[right] = list[right], list[low] quick_sort(list, left, low-1) quick_sort(list, low+1, right) return listprint(quick_sort([3, 2, 5, 1, 4, 6, 8, 7], 0, 7))
堆排序
def adjust_heap(list, i, n): lchild = 2 * i + 1 rchild = 2 * i + 2 max = i if lchild < n and list[lchild] > list[max]: max = lchild if rchild < n and list[rchild] > list[max]: max = rchild if max != i: list[i], list[max] = list[max], list[i] adjust_heap(list, max, n) def build_heap(list, n): for i in range(int(n/2)-1, -1, -1): adjust_heap(list, i, n)def heap_sort(list): build_heap(list, len(list)) for i in range(len(list)-1, -1, -1): list[0], list[i] = list[i], list[0] adjust_heap(list, 0, i) return listlist = [3, 2, 5, 1, 4, 6, 8, 7]print(heap_sort(list))
归并排序
自顶向下的递归实现：
$$T(n)=2T\left(\frac{n}{2}\right)+O(n)$$$$\Rightarrow T(n)=O(n\log n)$$def merge(list1, list2): res = [] n, m = len(list1), len(list2) i, j = 0, 0 while i < n and j < m: if list1[i] < list2[j]: res.append(list1[i]) i += 1 else: res.append(list2[j]) j += 1 res += list1[i:] res += list2[j:] return resdef merge_sort(list): n = len(list) if n <= 1: return list left = merge_sort(list[:n//2]) right = merge_sort(list[n//2:]) return merge(left, right)