Python常见排序算法详解：原理、复杂度与实现

白榆

发布时间：2026-10-14 | 4人浏览过

原创

本文深入解析Python中常见的五种排序算法，包括冒泡、选择、插入、堆排序及归并排序。详细阐述各算法的核心原理、时间复杂度（如O(n^2)与O(nlogn)）及空间复杂度，并提供完整的Python代码示例。通过对比不同算法的效率与适用场景，帮助开发者理解算法优劣并掌握实际编码技巧，适用于Python初学者及需要优化数据处理效率的工程师。

算法基础概念

在深入探讨具体算法之前，我们需要明确算法的基本概念。

算法（Algorithm）是对解题方案的准确且完整的描述，它由一系列清晰的指令组成，代表了用系统化方法解决特定问题的策略机制。简而言之，算法能够接收符合规范的输入，并在有限时间内产生预期的输出。若算法存在缺陷或不适用特定问题，则无法有效解决问题。不同的算法可能在时间、空间或执行效率上存在差异，因此通常通过空间复杂度与时间复杂度来衡量算法的优劣。

Python常见排序算法详解

在Python开发中，掌握常见算法对于提升程序性能至关重要。以下将介绍几种经典的排序算法及其在Python中的实现。

冒泡排序

效率：O(n^2)

原理：

比较相邻的两个元素，如果前一个元素大于后一个元素，则交换它们的位置；

对每一对相邻元素重复上述操作，从第一对开始直到最后一对。经过这一轮遍历，最大的元素会被“冒泡”到序列的末尾，这被视为完成了一趟排序；

针对剩余的所有元素重复上述步骤，但无需再处理最后一个已排好序的元素；

持续对剩余元素重复上述过程，直到没有相邻元素需要比较为止，此时数列即按从大到小（或根据交换逻辑调整为从小到大）的顺序排列完成。


def bubble_sort(data):
  """
  冒泡排序
  :param data: 
  :return: 
  """
  for i in range(len(data)-1): # 趟数
    for j in range(len(data)-i-1): # 遍历数据，依次交换
      if data[j]>data[j+1]: # 当较大数在前面
        data[j],data[j+1]=data[j+1],data[j] #交换两个数的位置
 
if __name__=='__main__':
  import random
  data_list=list(range(30))
  random.shuffle(data_list)
  print("pre:",data_list)
  bubble_sort(data_list)
  print("after:",data_list)
#结果：
#pre: [22, 11, 19, 16, 12, 18, 20, 28, 27, 4, 21, 10, 9, 7, 1, 6, 5, 29, 8, 0, 17, 26, 13, 14, 15, 24, 25, 23, 3, 2]
#after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

选择排序

效率：O(n^2)

原理：

每一轮从未排序的序列中选出最小（或最大）的元素，并将其与其他元素依次比较。若发现比当前选中元素更小的数，则交换位置。当所有元素比较完毕，最小的元素便被放置在序列的最左侧（这一过程称为一趟）；

重复上述步骤，直到所有待排序的数据元素全部排列完毕。

代码实现示例：


def select_sort(data):
  """
  选择排序
  :param data: 待排序的数据列表
  :return: 
  """
  for i in range(len(data)-1): #趟数
    min_index=i # 记录i趟开始最小的数的索引，我们从最左边开始
    for j in range(i+1,len(data)): # 每一次趟需要循环的次数
      if data[j] < data[min_index]: # 当数列中的某一个数比开始的数要小时候，更新最小值索引位置
        min_index=j
    data[i],data[min_index]=data[min_index],data[i] # 一趟走完，交换最小值的位置，第一趟最小
if __name__=='__main__':
  import random
  data_list=list(range(30))
  random.shuffle(data_list) # 打乱列表数据
  print("pre:",data_list)
  select_sort(data_list)
  print("after:",data_list)
#结果：
#pre: [20, 11, 22, 0, 18, 21, 14, 19, 7, 23, 27, 29, 24, 4, 17, 15, 5, 10, 26, 13, 25, 1, 8, 16, 3, 9, 2, 28, 12, 6]
#after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]

插入排序

效率：O(n^2)

原理：

以从小到大排序为例，假设元素0为已排序部分的第一个元素，插入排序从元素1开始，尝试将其插入到已排序序列的正确位置。

在插入过程中，需确定插入位置和试探位置。元素i的初始插入位置为i，试探位置为i-1。在插入元素i时，依次与i-1, i-2……等元素进行比较。如果被试探位置的元素比插入元素大，则被试探元素后移一位，同时插入元素的位置前移一位，直到被试探元素小于插入元素或插入元素位于序列首位。

重复上述步骤，直至完成所有元素的排序。

代码实现示例：


def insert_sort(data):
  """
  插入排序
  :param data: 待排序的数据列表
  :return: 
  """
  for i in range(1, len(data)): # 无序区域数据
    tmp = data[i] # 第i次插入的基准数
    for j in range(i, -1, -1):
      if tmp < data[j - 1]: # j为当前位置，试探j-1位置
        data[j] = data[j - 1] # 移动当前位置
      else: # 位置确定为j
        break
    data[j] = tmp # 将当前位置数还原
 
if __name__=='__main__':
  import random
  data_list=list(range(30))
  random.shuffle(data_list) # 打乱列表数据
  print("pre:",data_list)
  insert_sort(data_list)
  print("after:",data_list)
#结果：
#pre: [7, 17, 10, 16, 23, 24, 13, 11, 2, 5, 15, 29, 27, 18, 4, 19, 1, 9, 3, 21, 0, 14, 12, 25, 22, 28, 20, 6, 26, 8]
#after: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]