def radix_sort(lst, max_value): radix = 0 while max_value: buckets = [[] for _ in range(10)] for i in lst: buckets[(i // (10 ** radix)) % 10].append(i) print(buckets) cur = 0 for i in range(10): for j in buckets[i]: lst[cur] = j cur += 1 max_value //= 10 radix += 1 时间复杂度： 最优：$O(n×k)$ 最坏：$O(n×k)$ 平均：$O(n×k)$ 空间复杂度： $O(n + k)$ 稳定性： 稳定
设置固定数量的空桶； 把数据放到对应的桶中； 对每个不为空的桶中数据进行排序； 拼接不为空的桶中数据，得到结果。 def bucket_sort(lst): max_value = lst[0] min_value = lst[0] for m in lst: if m > max_value: max_value = m if m < min_value: min_value = m # 1. 创建桶（注意：一个桶就是一个列表） bucket_num = (max_value - min_value) // 3 + 1 buckets = [[] for _ in range(bucket_num)] # 2. 将数据分桶 并在桶内并排序 for k in lst: # 遍历列表中所有的数 i = k // 3 # i 表示 放到几号桶里 buckets[i].append(k) # 将数添加到桶里边 # 桶内排序 这里是插入排序 for j in range(len(buckets[i]) - 1, 0, -1): if buckets[i][j] < buckets[i][j - 1]: buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j] else: break prev_length = 0 for i in range(bucket_num): cur_length = len(buckets[i]) for j in range(cur_length): lst[i * prev_length + j] = buckets[i][j] prev_length = cur_length 时间复杂度：...
前言 计数排序，桶排序，和基数排序都需要额外的数据结构来辅助排序 def count_sort(lst, min_value, max_value): # 获取所需桶的数量 bucket_num = max_value - min_value + 1 # 构建初始桶 bucket = [0] * bucket_num # 统计元素数量，并存储在桶的对应位置 for i in lst: bucket[i - min_value] += 1 cur = 0 # 将桶中元素依次放回原数组，覆盖原数组元素 for j in range(bucket_num): for _ in range(bucket[j]): lst[cur] = j cur += 1 时间复杂度： 最优：$O(n+k)$ 最坏：$O(n+k)$ 平均：$O(n+k)$ 空间复杂度： $O(k)$ 稳定性： 稳定 额外提供一种稳定的计数排序Python实现 def count_sort(lst, min_value, max_value): # 获取所需桶的数量 bucket_num = max_value - min_value + 1 # 构建初始桶 bucket = [0] * bucket_num # 统计元素数量，并存储在桶的对应位置 for i in lst: bucket[i - min_value] += 1 for j in range(1, bucket_num): bucket[j] += bucket[j-1] result = [None] * len(lst) for k in range(len(lst) - 1, -1, -1): t = lst[k] - min_value bucket[t] -= 1 result[bucket[t]] = lst[k] return result
前言 堆排序是利用堆的数据结构完成排序的一种算法，堆可以理解为将它所有元素按照一个完全二叉树的顺序存储在数组中。 堆分为最大堆和最小堆，所有元素都小于它根节点的为最大堆。 因为元素都在数组中，所以元素$k_n$的左右子节点分别为$k_{2n+1}$和$k_{2n+2}$ 核心思想 1、构建最大堆（从树的的最后一个非叶子节点元素到第一个元素，比较它和它左右子节点的值叶子节点小则交换位置） 2、步骤一完成后序列已满足最大堆，交换堆顶和堆尾元素，堆长度向后减少1，重复步骤一，直到堆没有叶子节点 3、如果一次循环中未发生元素交换，则序列已有序，可提前结束循环。 def heap_sort(lst): length = len(lst) while length > 1: for root in range(length // 2, -1, -1): left = 2 * root + 1 right = 2 * root + 2 if left < length and lst[left] > lst[root]: lst[root], lst[left] = lst[left], lst[root] if right < length and lst[right] > lst[root]: lst[root], lst[right] = lst[right], lst[root] length -= 1 lst[0], lst[length] = lst[length], lst[0] 时间复杂度：...
核心思想 1、递归分解序列至不可分 2、合并序列，合并的同时对序列排序 def merge_sort(lst): """ 递归分解序列至不可分，再递归合并，合并的同时对序列排序， 使用两个指针分别遍历两个子序列，将元素按大小依次加入新的序列 """ n = len(lst) if n <= 1: return mid = n // 2 left = lst[:mid] right = lst[mid:] merge_sort(left) merge_sort(right) left_idx = 0 right_idx = 0 lst[:] = [] while left_idx < len(left) and right_idx < len(right): if left[left_idx] <= right[right_idx]: lst.append(left[left_idx]) left_idx += 1 else: lst.append(right[right_idx]) right_idx += 1 lst += left[left_idx:] lst += right[right_idx:] 时间复杂度： 最优：$O(n\log_2n)$ 最坏：$O(n\log_2n)$ 平均：$O(n\log_2n)$...