Python实现插入排序和选择排序详解

不晚

发布时间：2026-10-13| 5人浏览过

原创

本文详细介绍Python中插入排序和选择排序的实现原理与代码。插入排序通过将元素插入有序区间构建有序序列，而选择排序则在未排序区间寻找最小值并交换。两者时间复杂度均为O(n2)，适合小规模数据排序，代码包含完整实现及逻辑解析。

接下来，我们将深入探讨两种基础的排序算法。

插入排序算法解析

如示意图所示，插入排序的核心逻辑在于维护一个有序区间，并将新元素插入到该区间的合适位置。

具体操作步骤如下：

初始状态下，有序区间仅包含数组的第一个元素，其余部分视为未排序区间。

未排序区间的第一个元素（图中绿色标记）将被取出，并在有序区间内寻找其正确插入位置。

查找过程从有序区间的末尾向前扫描：若待插入元素大于当前比较元素，则确定插入位置为当前元素之后；若小于，则将当前元素向后移动一位以腾出空间。此过程持续进行，直到找到合适位置或遍历完有序区间。

对应的Python实现代码如下：


def insertion_sort(a):
 length = len(a)
 if length <=1:
  return 
 for i in range(1,length):
  j = i-1
  value = a[i]
  while j >=0:
   if a[j]<value:
    a[j+1] = value
    break
   else:
    a[j+1] = a[j]
    if j == 0:
     a[j] = value 
   j -=1
  print(a)

关于时间复杂度，算法需遍历整个数组，外层循环执行n次，故为O(n)。每次遍历涉及插入操作，平均情况下需移动一半元素，总体时间复杂度为O(n2)。

选择排序算法解析

选择排序与插入排序类似，均将数组划分为有序和未排序两个区间。不同之处在于，选择排序并非插入新元素，而是在未排序区间中筛选出最小元素，并将其交换至有序区间的末尾。

其Python实现代码如下：


def selection_sort(a):
 length = len(a)
 if length <=1:
  return
 for i in range(0,length-1):
  min_value = a[i]
  min_index = i
  j = i+1
  while j<length:
   if a[j] < min_value:
    min_value = a[j]
    min_index = j
   j += 1
  a[i],a[min_index] = a[min_index],a[i]

时间复杂度分析：假设数组长度为n，算法需执行n次最小值查找。每次查找需遍历未排序区间，复杂度为O(n)。因此，总时间复杂度为O(n2)。