核心思想 1、将序列按固定步长分组，组内进行插入排序 2、缩小步长，重复步骤一，直到步长小于等于1 def shell_sort(lst): n = len(lst) gap = n // 2 while gap >= 1: for i in range(gap, n): for j in range(i, 0, -gap): if lst[j] < lst[j - gap]: lst[j], lst[j - gap] = lst[j - gap], lst[j] else: break gap = gap // 2 时间复杂度： 最优：$O(n)$ 最坏：$O(n^2)$ 平均：$O(n^{1.3})$ 空间复杂度： $O(1)$ 稳定性： 不稳定
核心思想 1、随机选择一个元素作为基准（一般选择第一个或最后一个元素），将序列按照基准切分成两份，大于基准的在后面，小于基准的在前面。 2、递归对切分的序列进行步骤1，直到序列不可分 def quick_sort(lst, head, tail): if head >= tail: return p = lst[head] start = head end = tail while start < end: while start < end and lst[end] >= p: end -= 1 lst[start] = lst[end] while start < end and lst[start] <= p: start += 1 lst[end] = lst[start] lst[end] = p quick_sort(lst, head, start - 1) quick_sort(lst, start + 1, tail) 时间复杂度： 最优：$O(n\log_2n)$ 最坏：$O(n^2)$ 平均：$O(n\log_2n)$...
核心思想 1、定义一个已排序序列（初始一般指定第一个元素），将已排序序列后一个元素与已排序序列中每个元素从后往前比较，如果未排序元素小则交换，否则说明已经到正确位置，终止循环。 2、已排序序列范围向后增加1，重复步骤2，直到已排序序列长度等于原序列长度 def insert_sort(lst): """定义一个已排序序列，将剩余未排序序列依次插入到已排序序列""" n = len(lst) for i in range(1, n): for j in range(i, 0, -1): if lst[j] < lst[j-1]: lst[j], lst[j-1] = lst[j-1], lst[j] else: break 时间复杂度： 最优：$O(n)$ 最坏：$O(n^2)$ 平均：$O(n^2)$ 空间复杂度： $O(1)$ 稳定性： 稳定
核心思想 1、遍历序列找到最小元素并记录，将最小元素与队列首元素交换 2、序列范围向前缩小1，重复步骤1 def select_sort(lst): n = len(lst) for i in range(n - 1): min_idx = i for j in range(i + 1, n): if lst[j] < lst[min_idx]: min_idx = j lst[min_idx], lst[i] = lst[i], lst[min_idx] 时间复杂度： 最优：$O(n^2)$ 最坏：$O(n^2)$ 平均：$O(n^2)$ 空间复杂度： $O(1)$ 稳定性： 不稳定
核心思想 1、依次比较相邻元素，后面的比前面的小则交换元素，序列最后一个元素为最大元素 2、遍历长度缩小1，重复步骤一 3、如果一次循环中未发生元素交换，则序列已有序，可提前结束循环。 def bubble_sort(lst): n = len(lst) for j in range(1, n - 1): count = 0 for i in range(n - j): if lst[i] > lst[i+1]: lst[i], lst[i+1] = lst[i+1], lst[i] count += 1 if count == 0: break 时间复杂度： 最优：$O(n)$ 最坏：$O(n^2)$ 平均：$O(n^2)$ 空间复杂度： $O(1)$ 稳定性： 稳定