选择排序、插入排序和冒泡排序

发表于 2025/11/04

作者 CrabPeelMyShell

8 分钟阅读

选择排序、插入排序和冒泡排序

首先我们需要认识一个概念 Inversions 指的是在一个 $n$ 个数的集合中 $a_0…a_{n-1}$ 满足：$j<k$ 但 $a_j>a_k$ 的有序元组 $(a_j,a_k)$ 对于一个未排序的数组，就可以看成是由多个 Inversions 组成的

1. 选择排序 (Selection Sort)

先考虑以下情况：有一个已排序的列表，其所有元素都小于未排序的列表，然后我们在未排序的列表中找到（Selection）最小的元素然后添加 (append) 到已排序的列表中，然后再从未排序的列表中移除。

选择排序的核心思想可以总结为： 每一轮在未排序的部分中，扫描并找到全局最小的元素，然后将其与未排序部分的第一个元素交换。（这是另一种理解方式，和前面提到的不同，但是本质都是一样的）

这里给出一种代码实现

  
template <typename Type>
void selection_sort( Type *const array, int const n ) {

  for ( int i = 0; i < n - 1; i++ ) { // 第一个到倒数第二个
    // 在未排序部分 array[i]...array[n-1] 中找到最小值
    int lowindex = i;
    
    for ( int j = n - 1; j > i; j-- ) { // 最后一个到未排序的第一个
      if ( array[j] < array[lowindex] ) {
        lowindex = j;
      }
    }
    // 将找到的最小值与未排序部分的开头交换
    Type temp = array[i];
    array[i] = array[lowindex];
    array[lowindex] = temp;
  }
}

现在对选择排序的时间复杂度进行分析：

（以下是来自 Gemini 的总结，辅助理解）

边界控制:
- 外层循环 i < n - 1：当只剩最后一个元素时，它自然有序，无需再循环，这是一个正确的优化。
- 内层循环 j > i：确保了查找范围是 i 之后的所有元素，并且与 lowindex = i 的初始化配合得很好。
核心问题澄清：与谁交换？
- 错误理解：与已排序部分的最后一个元素 (array[i-1]) 交换。
- 正确理解：与未排序部分的第一个元素 (array[i]) 交换。i 是本轮要被填充的“坑位”。
更精确的视角：三段论
- 在 i 轮循环中，数组可看作：
  1. array[0...i-1]: 已排序区
  2. array[i]: 当前坑位 (也是临时的最小值候选)
  3. array[i+1...n-1]: 搜索区 (在此寻找真正的最小值)

2. 插入排序 (Insertion Sort)

想象一下：现在有一个已经排序好的列表，如果我们想往里面插入一个元素，并始终保持这个列表sorted，那么就需要从后往前比较，找到正确的位置插入。

核心思想可以总结为： 像整理扑克牌一样，每次从未排序部分取第一个元素，然后在已排序部分中从后往前扫描，找到正确的位置并插入。

对于任何未排序的列表：开始时，将第一个元素视为一个大小为 1 的已排序列表。

这里给出一种代码实现

  
template <typename Type>
void insertion_sort( Type *const array, int const n ) {

  for ( int k = 1; k < n; ++k ) { // 将第一个元素视为一个大小为 1 的已排序列表
	// 在已排序的部分（k之前）给未排序的第一个（k）找地方插入
    for ( int j = k; j > 0; --j ) { 
    
      if ( array[j - 1] > array[j] ) { // 一个一个向前比较
        std::swap( array[j - 1], array[j] );
      } else {
        // 优化点：一旦无需交换，说明已找到位置
        break;
      }
    }
  }
}

Case	Run Time	Comments
Worst	$\Theta(n^2)$	Reverse sorted
Average	$O(d + n)$	Slow if $d = \omega(n)$
Best	$\Theta(n)$	Very few inversions: $d = O(n)$

时间复杂度	选择排序 (Selection Sort)	插入排序 (Insertion Sort)
最佳情况	`O(n²)` (数组已有序)	`O(n)` (数组已有序)
平均情况	`O(n²)`	`O(n²)`
最差情况	`O(n²)` (数组逆序)	`O(n²)` (数组逆序)

$d$ 是 Inversions 的数量；

（以下是来自 Gemini 的总结，辅助理解）

边界控制:
- 外层循环 k = 1：从第二个元素开始，因为单个元素 (array[0]) 默认已排序。
- 内层循环 j > 0：防止 array[j-1] 访问到负数索引，保证了比较的安全性。
break 优化:
- 这是插入排序的精髓。因为 array[0...k-1] 是有序的，所以当 array[j] 向前移动时，一旦遇到一个比它小的元素 array[j-1]，就意味着它已到达正确位置，无需再往前比较。
- 这个特性使得插入排序在处理近乎有序的数组时效率极高。

但是由于一个一个 swap 的性能开销非常大，因此采用赋值操作，本质是“挖空”，然后填补（IFNEC）。

  
template <typename Type>
void insertion( Type *const array, int const n ) {

  for ( int k = 1; k < n; ++k ) {
    Type tmp = array[k]; // 1. 保存元素，形成“空位”

    // 2. 移位过程
    for ( int j = k; j > 0; --j ) {
      if ( array[j - 1] > tmp ) {
        array[j] = array[j - 1]; // 将大元素右移
      } else {
        array[j] = tmp; // 3. 找到位置，插入
        break;
      }
    }

    // 4. 特殊情况处理：如果tmp是最小元素
    // 将 array[0] 右移后并没有填补第一个位置
    if ( array[0] > tmp ) {
      array[0] = tmp;
    }
  }
}

总结

选择排序 无论输入如何，性能都稳定在 O(n²)，它的唯一优势是交换次数少。
插入排序 性能更优，尤其在处理小规模或近乎有序的数据时表现出色，是更实用的简单排序算法。

数据结构, 课程笔记

数据结构排序算法

本文由作者按照 CC BY 4.0 进行授权

1. 选择排序 (Selection Sort)

2. 插入排序 (Insertion Sort)

总结

热门标签