Python实现经典排序算法详解与代码示例

巷口听风

发布时间：2026-10-15| 3人浏览过

原创

本文详细介绍Python中经典排序算法的实现，包括冒泡、选择、插入、希尔、归并、快速、堆、计数、桶及基数排序。每种算法均提供核心代码逻辑与复杂度分析，帮助开发者深入理解算法原理并应用于实际开发场景。

以下排序算法的最终结果均默认为升序排列。这些实现旨在简化表达，未涵盖所有边界情况，主要目的是展示算法的核心思想。

冒泡排序

在内层循环中，相邻元素会被依次比较。第一次内层循环结束后，最大元素会被移动到序列的最右侧；第二次循环后，次大元素会移动到最大元素的左侧。每次内层循环结束时，都会确保一个元素处于正确的位置。


def bubble_sort(arr):
  length = len(arr)
  for i in range(length):
    for j in range(length - i - 1):
      if arr[j] > arr[j + 1]:
        arr[j], arr[j + 1] = arr[j + 1], arr[j]
  return arr

选择排序

每次内层循环都会找出当前未排序部分的最小元素，并将其放置到正确位置。第一次内层循环结束后，最小元素会被交换到序列的起始位置；第二次循环后，第二小的元素会被交换到第二个位置。每次内层循环结束后，都会将一个元素放置在正确的顺序位置上。


def selection_sort(arr):
  length = len(arr)
  for i in range(length):
    min_index = i
    for j in range(i + 1, length):
      if arr[j] < arr[min_index]:
        min_index = j
    arr[i], arr[min_index] = arr[min_index], arr[i]
  return arr

插入排序

其思想类似于整理扑克牌。从第二个元素开始，假设第一个元素已排序。处理第二个元素时，如果它比第一个元素小，则将其插入到第一个元素之前，否则放在其后。此时前两个元素已有序，接着依次处理剩余元素，将其插入到已排序部分的适当位置。


def insertion_sort(arr):
  length = len(arr)
  for i in range(1, length):
    pre = i - 1
    current_value = arr[i]
    while pre >= 0 and arr[pre] > current_value:
      arr[pre + 1] = arr[pre]
      pre -= 1
    arr[pre+1] = current_value
  return arr

希尔排序

希尔排序是插入排序的改进版本。与插入排序每次只比较相邻元素不同，希尔排序从较大的步长开始进行比较和交换，随着步长的逐渐减小，最后步长减为1，此时算法退化为标准的插入排序，但整体效率更高。


def shell_sort(arr):
  length = len(arr)
  gap = length // 2
  while gap > 0:
    for i in range(gap, length):
      pre = i - gap
      current_value = arr[i]
      while pre >= 0 and arr[pre] > current_value:
        arr[pre + gap] = arr[pre]
        pre -= gap
      arr[pre + gap] = current_value
    gap = gap // 2
  return arr

归并排序

归并排序采用分治策略，先将序列的前半部分排好序，再将后半部分排好序，最后将这两部分合并以得到最终序列。具体实现是通过递归地将序列不断二分，分别对子序列排序后，再合并两个有序子序列。


def merge(left, right):
  result = []
  while len(left) > 0 and len(right) > 0:
    if left[0] < right[0]:
      result.append(left.pop(0))
    else:
      result.append(right.pop(0))
  if len(left) > 0:
    result.extend(left[:])
  if len(right) > 0:
    result.extend(right[:])
  return result


def merge_sort(arr):
  if len(arr) < 2:
    return arr
  middle = len(arr) // 2
  return merge(merge_sort(arr[:middle]), merge_sort(arr[middle:]))

快速排序

快速排序选取一个基准元素（pivot），将比基准小的元素移到其左侧，比基准大的元素移到其右侧。然后递归地对基准左侧和右侧的子序列进行同样的操作，直到所有元素都排序完成。


def partition(arr, left=None, right=None):
  pivot = left
  index = pivot + 1
  for i in range(index, right + 1):
    if arr[i] < arr[pivot]:
      arr[i], arr[index] = arr[index], arr[i]
      index += 1
  arr[pivot], arr[index - 1] = arr[index - 1], arr[pivot]
  return index - 1


def quick_sort(arr, left=None, right=None):
  left = 0 if left is None else left
  right = len(arr) - 1 if right is None else right
  if left < right:
    partition_index = partition(arr, left, right)
    quick_sort(arr, left, partition_index - 1)
    quick_sort(arr, partition_index + 1, right)
  return arr

堆排序

首先构建一个最大堆，其性质是父节点的值总是大于或等于其左右子节点的值。此时根节点为最大值，将其交换到序列的最右侧。接着将堆中最后一个叶节点移到根节点，这可能会破坏最大堆性质，因此需要调整：将其与左右子节点中较大的值交换，使该节点下沉。重复此过程直到符合最大堆性质，此时新的根节点即为剩余元素中的最大值，将其取出放入序列的正确位置，并继续处理剩余节点。


global length2


def heapify(arr, i):
  left = 2 * i + 1
  right = 2 * i + 2
  largest = i
  if left < length2 and arr[left] > arr[largest]:
    largest = left
  if right < length2 and arr[right] > arr[largest]:
    largest = right
  if largest != i:
    arr[i], arr[largest] = arr[largest], arr[i]
    heapify(arr, largest)


def build_max_heap(arr):
  for i in range(len(arr) // 2, -1, -1):
    heapify(arr, i)


def heap_sort(arr):
  global length2
  length2 = len(arr)
  build_max_heap(arr)
  for i in range(len(arr) - 1, 0, -1):
    arr[0], arr[i] = arr[i], arr[0]
    length2 -= 1
    heapify(arr, 0)
  return arr

计数排序

计数排序将序列中的元素根据其值映射到相应的桶（或索引）中，统计每个值出现的次数。之后按照桶的顺序依次取出元素即可。需要注意的是，计数排序不需要进行元素间的比较操作，适用于整数范围较小的场景。


def counting_sort(arr):
  max_value = max(arr)
  buckets = [0] * (max_value + 1)
  index = 0
  length = len(arr)
  for i in range(length):
    buckets[arr[i]] += 1
  for j in range(max_value + 1):
    while buckets[j] > 0:
      arr[index] = j
      index += 1
      buckets[j] -= 1
  return arr

桶排序

桶排序类似于计数排序，但构造了多个桶，每个桶容纳特定值域范围内的元素。将序列中的元素根据规则分配到各个桶中，然后对每个桶内的元素进行排序（通常使用插入排序），最后按照桶的顺序以及桶内元素的顺序合并得到最终序列。


def bucket_sort(arr):
  bucket_size = 5
  max_value = max(arr)
  min_value = min(arr)
  bucket_num = (max_value - min_value) // bucket_size + 1
  buckets = {i: [] for i in range(bucket_num)}
  for i in range(len(arr)):
    buckets[(arr[i] - min_value) // bucket_size].append(arr[i])
  result = []
  for i in range(bucket_num):
    insertion_sort(buckets[i])
    result.extend(buckets[i])
  return result

基数排序

基数排序根据元素值的特定数位进行排序，通常从最低位（个位）到最高位依次进行排序。每一轮排序使用稳定的排序算法（如计数排序）处理当前数位，经过多轮处理后得到最终有序序列。


def radix_sort(arr):
  max_value = max(arr)
  max_digit = len(str(max_value))
  dev = 1
  mod = 10
  result = arr[:]
  for i in range(max_digit):
    buckets = {i: [] for i in range(mod)}
    for k in range(len(result)):
      key = (result[k] % mod) // dev
      buckets[key].append(result[k])
    result = []
    for j in range(mod):
      result.extend(buckets[j])
    dev *= 10
    mod *= 10
  return result

上述代码放在到中