冒泡排序与插入排序
编写这两种平方级排序算法，理解它们为何是 O(n²)，并认识插入排序胜过归并排序的那种情况。
冒泡排序与插入排序 是 CoddyKit 上的免费 DSA Interview Prep 课时。 这是第 1 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 DSA Interview Prep 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 DSA Interview Prep 课程共包含 4 节课。
为什么要学习 O(n²) 排序
冒泡排序和插入排序在最坏情况下的复杂度为 O(n²)，因此不适合处理大型输入。然而，每一次严肃的算法面试都希望您能够实现并分析它们。它们能够教授比较、交换、稳定排序和最佳情况行为等基本概念，而这些概念同样适用于更高级的算法。面试官会用它们来测试您是否能够从第一性原理出发，理解循环不变量和渐进记号。
# When O(n^2) is acceptable:
# n <= 1000: 10^6 ops, runs in milliseconds
# nearly-sorted data: insertion sort beats merge sort
# constant factor so small (simple ops) that overhead matters
import time
def time_sort(sort_fn, data):
import copy
arr = copy.copy(data)
t = time.perf_counter()
sort_fn(arr)
return time.perf_counter() - t
print('Small n: quadratic sorts are fine')冒泡排序：将最大值冒泡到末尾
冒泡排序会反复扫描数组，并交换顺序错误的相邻元素。每次完整遍历后，未排序部分中最大的元素都会“冒泡”到末尾的最终位置。经过 n-1 次遍历后，整个数组就完成排序。它的名称来源于较大元素像气泡一样向上浮动的过程。它是最容易描述的排序算法，但在实际应用中很少使用。
def bubble_sort(arr):
n = len(arr)
for i in range(n - 1): # n-1 passes
for j in range(n - 1 - i): # inner loop shrinks
if arr[j] > arr[j+1]: # out of order
arr[j], arr[j+1] = arr[j+1], arr[j] # swap
return arr
arr = [64, 34, 25, 12, 22, 11, 90]
bubble_sort(arr)
print(arr) # [11, 12, 22, 25, 34, 64, 90]带提前退出的冒泡排序
优化版冒泡排序使用 swapped 标志：如果一次完整的内层遍历没有发生任何交换，就说明数组已经有序，可以提前退出。这使得对于已经有序的输入，最佳情况达到O(n)——这是冒泡排序唯一真正的优势。如果没有这个标志，它总会执行 O(n²) 次比较。询问如何改进冒泡排序时，面试官通常会检查您是否实现了提前退出优化。
def bubble_sort_optimised(arr):
n = len(arr)
for i in range(n - 1):
swapped = False
for j in range(n - 1 - i):
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swapped = True
if not swapped: # already sorted!
print(f'Sorted after pass {i+1}')
break
arr1 = [1, 2, 3, 4, 5] # already sorted
bubble_sort_optimised(arr1) # exits after 1 pass冒泡排序复杂度分析
冒泡排序的外层循环执行 n-1 次。每次遍历中，内层循环执行 n-1-i 次：(n-1) + (n-2) + ... + 1 = n(n-1)/2 ≈ n²/2 次比较。因此，平均情况和最坏情况的复杂度都是O(n²)。使用提前退出标志后，对于有序输入，最佳情况会降至O(n)。空间复杂度为 O(1)——只有交换操作需要一个临时变量。冒泡排序是稳定的：由于只交换严格更大的元素，相等元素会保持原有的相对顺序。
def bubble_sort_counted(arr):
n = len(arr)
swaps = comparisons = 0
for i in range(n-1):
for j in range(n-1-i):
comparisons += 1
if arr[j] > arr[j+1]:
arr[j], arr[j+1] = arr[j+1], arr[j]
swaps += 1
return comparisons, swaps
arr = [5, 4, 3, 2, 1] # worst case: reversed
c, s = bubble_sort_counted(arr)
print(f'Comparisons: {c}, Swaps: {s}') # 10, 10 for n=5插入排序：整理一手有序的牌
插入排序模拟整理一手牌的过程：拿起下一张牌（元素），将它插入左侧已排序牌组中的正确位置。其不变量是 arr[0:i] 始终保持有序。对于每个新元素，请将较大的元素向右移动，为它腾出空间。这种原地且稳定的算法最坏情况下的复杂度为 O(n²)，但对于近乎有序的数据，最佳情况下可达到 O(n)。
def insertion_sort(arr):
for i in range(1, len(arr)): # start from second element
key = arr[i] # element to insert
j = i - 1
# Shift larger elements to the right
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]
j -= 1
arr[j+1] = key # insert in correct position
return arr
arr = [12, 11, 13, 5, 6]
insertion_sort(arr)
print(arr) # [5, 6, 11, 12, 13]插入排序逐步演示
请跟踪插入排序处理 [3, 1, 4, 2] 的过程：i=1、key=1，将 3 向右移动 → [1, 3, 4, 2]。i=2、key=4，无需移动，数组不变。i=3、key=2，依次将 4 和 3 向右移动 → [1, 2, 3, 4]。每个元素都会与其左侧的元素比较，直到找到正确的位置。内层 while 循环通过赋值完成移动（比交换更快，因为每次移动只需一次赋值，而一次交换需要三次赋值）。
def insertion_sort_trace(arr):
for i in range(1, len(arr)):
key = arr[i]
j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j] # shift right (1 assignment)
j -= 1
arr[j+1] = key
print(f'After inserting {key}: {arr}')
insertion_sort_trace([3, 1, 4, 2])
# After inserting 1: [1, 3, 4, 2]
# After inserting 4: [1, 3, 4, 2] (no change)
# After inserting 2: [1, 2, 3, 4]在近乎有序的数据上使用插入排序
插入排序的关键优势是 O(n + 逆序对数量) 的复杂度。逆序对是满足 i < j 但 arr[i] > arr[j] 的一对元素。对于只有少量逆序对的近乎有序数组，插入排序非常快——由于算法简单且访问模式对缓存友好，它在实际应用中有时比归并排序更快。Python 的 Timsort 正是出于这个原因，在较小的子数组上使用插入排序。
# Nearly sorted: only 1 inversion
arr1 = [1, 2, 4, 3, 5] # 4>3 is the only inversion
def count_ops(arr):
arr = arr[:]
ops = 0
for i in range(1, len(arr)):
key = arr[i]; j = i - 1
while j >= 0 and arr[j] > key:
arr[j+1] = arr[j]; j -= 1; ops += 1
arr[j+1] = key
return ops
print(count_ops([1,2,4,3,5])) # 1 op (nearly sorted)
print(count_ops([5,4,3,2,1])) # 10 ops (reversed = worst case)排序的稳定性
如果相等元素在排序后仍保持原有的相对顺序，那么该排序算法就是稳定的。冒泡排序和插入排序都是稳定的——它们从不交换相等元素。当您依次按照多个键排序时，稳定性非常重要：先按照次要键进行稳定排序，再按照主要键进行稳定排序，这样可以在主要键相等时保持次要键的顺序。归并排序同样稳定；堆排序和快速排序通常不稳定。
# Stable sort preserves order of equal elements
students = [
('Alice', 85),
('Bob', 92),
('Carol', 85),
('Dave', 78),
]
# Sort by score ascending (stable: Alice before Carol for same score)
students.sort(key=lambda x: x[1])
for s in students:
print(s)
# ('Dave',78) ('Alice',85) ('Carol',85) ('Bob',92)
# Alice still comes before Carol => stable将插入排序视为二分查找
插入排序的内层循环既要查找正确位置，又要移动元素。您可以使用二分查找，以 O(log i) 次比较找到位置，但移动仍然需要 O(i) 时间，因此整体复杂度仍为 O(n²)。这种优化会减少比较次数（对于成本较高的比较函数很有用），但不会减少总操作次数。这种“二分插入排序”会出现在 Timsort 的小块处理中。
import bisect
def binary_insertion_sort(arr):
for i in range(1, len(arr)):
key = arr[i]
# Find insertion point in O(log i)
pos = bisect.bisect_left(arr, key, 0, i)
# Shift elements to make room: still O(i)
arr[pos+1:i+1] = arr[pos:i]
arr[pos] = key
return arr
print(binary_insertion_sort([5, 2, 4, 6, 1, 3]))
# [1, 2, 3, 4, 5, 6]冒泡排序与插入排序：如何选择
在面试中，请自信地这样比较：插入排序严格优于冒泡排序——两者最坏情况下都是 O(n²)，空间复杂度都是 O(1)，但插入排序的写入次数更少（逆序对数量为 k 时为 O(n+k)，而冒泡排序为 O(n²)），更符合缓存访问特性，并且是处理较小 n 的实际选择（Timsort 使用它）。冒泡排序唯一真正的优势是教学上的简单易懂。在生产环境中，请始终使用语言内置的 sort。
# Summary: when to use quadratic sorts
# Use insertion_sort when:
# - n <= 20 (small enough that O(n^2) is fine)
# - data is nearly sorted (few inversions => fast)
# - you need stable sort with O(1) space
# - implementing a hybrid (like Timsort)
# NEVER use bubble_sort in production code
# Python's built-in sort: O(n log n), stable, extremely fast
arr = [5, 2, 8, 1, 9]
print(sorted(arr)) # [1, 2, 5, 8, 9]
arr.sort()
print(arr) # [1, 2, 5, 8, 9]将逆序对计数作为度量
数组中的逆序对数量等于满足 i < j 但 arr[i] > arr[j] 的元素对数量。插入排序执行的移动次数恰好等于逆序对数量，这是一个很有用的认识。要高效地统计逆序对（O(n log n)），需要修改版归并排序。在排序相关讨论中，面试官有时会进一步询问：“您的算法对逆序对有多敏感？”
# Count inversions: naive O(n^2)
def count_inversions_naive(arr):
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] > arr[j]:
count += 1
return count
print(count_inversions_naive([3, 1, 2])) # 2: (3,1) and (3,2)
print(count_inversions_naive([1, 2, 3])) # 0: already sorted
print(count_inversions_naive([3, 2, 1])) # 3: all pairs inverted快速检查
请检验您对本课中数据结构与算法——编程面试准备相关概念的理解。
课程回顾
本课中，您学习了：冒泡排序执行 n-1 次遍历，每次将当前最大值冒泡到最终位置，最坏情况下为 O(n²)，使用提前退出标志时最佳情况下为 O(n)，插入排序将元素向右移动，把当前 key 插入正确的有序位置，复杂度为 O(n + 逆序对数量)，因此最适合近乎有序的数据，以及两种算法都稳定、空间复杂度为 O(1)、最坏情况下为 O(n²)，但在所有实际场景中都应严格优先选择插入排序而不是冒泡排序。接下来我们将从头实现归并排序。
常见问题解答
「冒泡排序与插入排序」课时是免费的吗？
是的 — 「冒泡排序与插入排序」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 DSA Interview Prep 课程的其余内容，请升级到 CoddyKit PRO。 DSA Interview Prep 课程共包含 4 节课。
「冒泡排序与插入排序」这节课中我会学到什么？
编写这两种平方级排序算法，理解它们为何是 O(n²)，并认识插入排序胜过归并排序的那种情况。 你通过在浏览器中直接运行的动手代码来练习 DSA Interview Prep，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 DSA Interview Prep 需要有经验吗？
无需任何先前经验。CoddyKit 上的 DSA Interview Prep 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 1 节课，共 4 节。
「冒泡排序与插入排序」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 DSA Interview Prep 课中编写并运行代码吗？
能。每节 DSA Interview Prep 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。