本文是排序系列第 2 篇，聚焦三种 O(n^2) 基线算法：冒泡、选择、插入。它们简单、易实现，是理解更高阶排序（希尔、快排、归并）的踏脚石，同时在小规模或几乎有序的数据上依然有价值。

目标读者

刷题与教学：需要掌握基础排序、写作专题的人。
工程师：在小规模、嵌入式或对代码尺寸敏感的场景需要轻量排序的人。
学习者：希望通过这三种算法理解稳定性、原地性与复杂度来源。

背景/动机

痛点：
- 经常有人忽视 O(n^2) 排序，但它们是理解“交换/选择/插入”三种思路的起点。
- 在小数组或几乎有序数据上，复杂度公式不代表实际性能，插入排序常优于快排。
- 需要一篇把三者放在同一框架下对比稳定性、交换次数与工程场景。

A — Algorithm（题目与算法）

主题：比较冒泡排序（交换驱动）、选择排序（最小值选择）、插入排序（局部有序插入），并给出基础示例。

示例数组：[5, 2, 4, 6, 1]

冒泡：邻接交换，把最大值“冒”到末尾；重复 n 轮。
选择：每轮选最小值，与当前位置交换；交换次数 ≤ n 次。
插入：维护前缀有序，将当前元素向前插入合适位置；对几乎有序数组高效。

直观输出（插入排序前两轮）：

轮 1：|5| 2 4 6 1 → 2 5 4 6 1
轮 2：2 |5| 4 6 1 → 2 4 5 6 1

C — Concepts（核心思想）

算法	思路	稳定	原地	比较次数(均)	交换/移动
冒泡	相邻交换	是	是	O(n^2)	O(n^2) 交换多
选择	每轮选最小做交换	否	是	O(n^2)	O(n) 级交换少
插入	维护前缀有序插入	是	是	O(n^2)	O(n^2) 移动，近乎有序时 O(n)

适用类别

冒泡：教学、稳定性要求、数组很小。
选择：交换成本高（如大对象拷贝），但比较可接受的场景。
插入：小数组、近乎有序、作为 TimSort/希尔排序的子过程。

E — Engineering（工程应用）

场景 1：嵌入式固件小数组排序（C）

背景：微控制器上排序最多几十个整数，内存紧张。为何：代码短、原地、无额外内存；选择排序交换次数少。

// 选择排序，原地 O(1) 空间
void selection_sort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_i = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[min_i]) min_i = j;
        if (min_i != i) {
            int tmp = a[i]; a[i] = a[min_i]; a[min_i] = tmp;
        }
    }
}

场景 2：几乎有序的小列表（Python）

背景：UI 列表每次仅有少量元素插入，原数据基本有序。为何：插入排序在逆序距离小的情况下接近 O(n)。

def insertion_sort(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]
            j -= 1
        arr[j + 1] = key
    return arr

data = [1, 2, 3, 5, 4]
print(insertion_sort(data))

场景 3：教学可视化（JavaScript）

背景：在前端课堂演示“交换 vs 插入”的差异。为何：冒泡稳定、直观，便于可视化动画；JS 代码简短。

function bubbleSort(arr) {
  const a = [...arr];
  for (let i = 0; i < a.length; i++) {
    let swapped = false;
    for (let j = 0; j < a.length - i - 1; j++) {
      if (a[j] > a[j + 1]) {
        [a[j], a[j + 1]] = [a[j + 1], a[j]];
        swapped = true;
      }
    }
    if (!swapped) break; // 小优化
  }
  return a;
}
console.log(bubbleSort([5, 2, 4, 6, 1]));

场景 4：服务端小批量排序（Go）

背景：请求内携带的条目数 < 64，优先用插入排序减少常数。为何：Go 标准库 sort 包对小规模会切换到插入思路；演示最小实现。

package main

import "fmt"

func insertionSort(a []int) {
    for i := 1; i < len(a); i++ {
        key := a[i]
        j := i - 1
        for j >= 0 && a[j] > key {
            a[j+1] = a[j]
            j--
        }
        a[j+1] = key
    }
}

func main() {
    arr := []int{5, 2, 4, 6, 1}
    insertionSort(arr)
    fmt.Println(arr)
}

R — Reflection（反思与深入）

复杂度：三者最坏/平均时间都是 O(n^2)，空间 O(1)。
稳定性：冒泡、插入稳定；选择不稳定（最小值交换可能打乱相对顺序）。
常见替代：
- 小数组：插入排序优于冒泡/选择；也是 TimSort、Introsort 在小规模的 fallback。
- 大数组：切换到 O(n log n)（快排/归并/堆）或非比较排序。
为何保留它们：
- 教学价值：直观理解比较、交换、移动。
- 工程价值：小规模、近乎有序、代码尺寸要求、或作为混合排序子模块。

S — Summary（总结）

冒泡/选择/插入是“交换/选择/插入”三种基本思路的代表，便于教学和理解更复杂算法。
稳定性：冒泡、插入稳定；选择不稳定但交换次数少。
小数组或近乎有序时，插入排序的实际表现常胜过 O(n log n) 算法。
现代排序实现常组合：大规模用快排/堆/归并，小规模回退到插入排序。
选型先看规模与有序度，再看稳定性需求和交换成本。

实践指南 / 步骤

判断数据规模：若 n < 64 且近乎有序，优先插入排序。
需要稳定且可视化：用冒泡并加“提前退出”优化。
交换成本高：选择排序减少交换次数。
作为混合排序子过程：在快排/归并实现中为小分段切换到插入排序。

可运行示例（多语言基线实现）

Python — 插入排序

def insertion_sort(a):
    for i in range(1, len(a)):
        key = a[i]; j = i - 1
        while j >= 0 and a[j] > key:
            a[j+1] = a[j]; j -= 1
        a[j+1] = key
    return a

print(insertion_sort([5,2,4,6,1]))

C — 选择排序

void selection_sort(int *a, int n) {
    for (int i = 0; i < n - 1; ++i) {
        int min_i = i;
        for (int j = i + 1; j < n; ++j)
            if (a[j] < a[min_i]) min_i = j;
        if (min_i != i) { int t=a[i]; a[i]=a[min_i]; a[min_i]=t; }
    }
}

C++ — 冒泡排序

#include <bits/stdc++.h>
using namespace std;
void bubble(vector<int>& a){
    for(size_t i=0;i<a.size();++i){
        bool swapped=false;
        for(size_t j=0;j+1<a.size()-i;++j){
            if(a[j]>a[j+1]){swap(a[j],a[j+1]);swapped=true;}
        }
        if(!swapped) break;
    }
}
int main(){vector<int> a={5,2,4,6,1}; bubble(a); for(int x:a) cout<<x<<" ";}

Go — 插入排序

func insertion(a []int){
    for i:=1;i<len(a);i++{
        key:=a[i]; j:=i-1
        for j>=0 && a[j]>key { a[j+1]=a[j]; j-- }
        a[j+1]=key
    }
}

Rust — 插入排序

fn insertion_sort(a: &mut [i32]) {
    for i in 1..a.len() {
        let key = a[i];
        let mut j = i as i32 - 1;
        while j >= 0 && a[j as usize] > key {
            a[(j+1) as usize] = a[j as usize];
            j -= 1;
        }
        a[(j+1) as usize] = key;
    }
}

fn main(){
    let mut v = vec![5,2,4,6,1];
    insertion_sort(&mut v);
    println!("{:?}", v);
}

JavaScript — 冒泡排序

function bubbleSort(a){
  for(let i=0;i<a.length;i++){
    let swapped=false;
    for(let j=0;j<a.length-i-1;j++){
      if(a[j]>a[j+1]){[a[j],a[j+1]]=[a[j+1],a[j]];swapped=true;}
    }
    if(!swapped) break;
  }
  return a;
}
console.log(bubbleSort([5,2,4,6,1]));

解释与原理（取舍）

冒泡 vs 选择：冒泡稳定但交换多；选择交换少但不稳定。若交换成本极高选选择；需稳定选冒泡。
插入 vs 冒泡：插入整体比较/移动更少，几乎有序时可降到 O(n)。
小规模混合策略：现实库中常用“快排/堆排 + 小段插排”取得两全。

常见问题与注意事项

冒泡未加“提前退出”会在已排序数组上做满 O(n^2) 轮。
选择排序若元素为大结构体，交换成本高但次数少；如需稳定可增加索引数组代替直接交换。
插入排序在大数组上退化严重；但在块大小 ≤ 32 的场景常胜。

最佳实践与建议

写对比表：稳定性、交换/移动次数、常数开销，作为选型依据。
为小分段写一个插入排序函数，在自定义快排/归并中复用。
测试用例至少包含：已排序、逆序、重复多、近乎有序，观察提前退出效果。

小结 / 结论

O(n^2) 三件套是理解排序的基石，也是工程混合排序的底层部件。
近乎有序/小规模场景下，插入排序仍是高性价比选择。
稳定性需求选冒泡或插入；交换成本敏感可考虑选择或索引化的稳定选择。

参考与延伸阅读

《算法导论》插入/冒泡/选择排序章节
CPython Timsort 代码中的插排阈值实现
Intel/AMD 白皮书（讨论缓存友好度对小数组排序的影响）

元信息

阅读时长：约 14 分钟
SEO 关键词：冒泡排序、选择排序、插入排序、O(n^2) 排序、稳定性
元描述：排序专题第二篇，对比冒泡/选择/插入排序的原理、稳定性、工程场景与多语言实现，帮你确定小规模或近乎有序数据的最佳选择。

行动号召（CTA）

选一个小规模真实数据集（如日志样本 50 条），分别用三种排序计时对比。
在你的快排/归并实现中加入“≤ 32 切换插排”优化，测一测收益。
关注后续系列：希尔排序、归并、快排、堆、非比较、TimSort/Introsort 与选型实战。

目标读者#

背景/动机#

A — Algorithm（题目与算法）#

C — Concepts（核心思想）#

E — Engineering（工程应用）#

场景 1：嵌入式固件小数组排序（C）#

场景 2：几乎有序的小列表（Python）#

场景 3：教学可视化（JavaScript）#

场景 4：服务端小批量排序（Go）#

R — Reflection（反思与深入）#

S — Summary（总结）#

实践指南 / 步骤#

可运行示例（多语言基线实现）#

Python — 插入排序#

C — 选择排序#

C++ — 冒泡排序#

Go — 插入排序#

Rust — 插入排序#

JavaScript — 冒泡排序#

解释与原理（取舍）#

常见问题与注意事项#

最佳实践与建议#

小结 / 结论#

参考与延伸阅读#

元信息#

行动号召（CTA）#