---

前言

在C++数据结构的学习中，排序是入门级核心知识点，而初阶排序算法（冒泡、选择、插入）则是构建排序思维的基石。这类算法时间复杂度多为O(n²)，逻辑简单、易于理解和手写，是初学者入门排序的首选，也是笔试面试中“基础编程题”的高频考点（常要求手写核心代码）。

本文专为C++初学者打造，聚焦3种核心初阶排序算法（冒泡排序、选择排序、插入排序），延续“原理通俗化、步骤拆解化、代码可运行、考点精准化”的风格，全程使用C++语法实现（适配数组与vector，贴合初学者练习场景），重点突破“算法逻辑理解、手写代码、基础特性辨析”，帮你从“零基础”快速上手初阶排序，为后续学习O(n log n)进阶排序打下坚实基础。

在正式开始前，先明确2个初阶排序的核心前提（避免混淆，衔接后续学习）：

• 初阶排序的核心特点：逻辑简单、代码量少、易于手写，无需复杂的数据结构支撑，仅通过“比较”和“交换”操作实现排序；

• 适用场景：数据量较小（百级、千级以内），对排序效率要求不高的场景，比如小型数组排序、面试基础编程题；

• C++学习重点：掌握算法核心逻辑、能手写C++代码（适配数组和vector）、理解时间/空间复杂度、区分各算法的优劣。

话不多说，从最基础的冒泡排序开始，逐个拆解，手把手教你吃透每一种初阶排序的逻辑与代码实现～

---

一、冒泡排序（Bubble Sort）—— 最易理解的入门排序

冒泡排序是最基础、最易上手的排序算法，核心逻辑是“相邻元素两两比较，将较大（或较小）的元素逐步‘冒泡’到数组末尾”，就像水中的气泡逐渐上浮，因此得名。其逻辑简单，适合作为排序入门的第一个算法，C++初学者必掌握。

1. 核心原理（通俗化理解）

核心逻辑：遍历数组，每次比较相邻的两个元素，如果前一个元素大于后一个元素（升序排序），则交换两者位置；重复此过程，直到整个数组有序。

关键特点：每一轮遍历都会将“未排序区间”的最大值（升序）“冒泡”到未排序区间的末尾，逐步缩小未排序区间，直到未排序区间长度为1，排序完成。

C++初学者补充：冒泡排序的核心是“双重循环”——外层循环控制排序轮次，内层循环控制每一轮的相邻元素比较与交换；可通过“设置标志位”优化，避免数组已有序时的无效循环（面试加分项）。

2. 分步拆解（升序为例，数组[8,9,1,7,2,3,5,4,6,0]）

1. 第1轮（未排序区间[0,9]）：遍历相邻元素，两两比较交换，将最大值9冒泡到末尾；             - 比较8和9：8<9，不交换；                                                                                                     - 比较9和1：9>1，交换 → [8,1,9,7,2,3,5,4,6,0]；                                                                   - 持续比较交换，最终9移动到索引9（末尾），数组变为[8,1,7,2,3,5,4,6,0,9]；                     - 本轮结束，未排序区间缩小为[0,8]，有序区间[9]；

2. 第2轮（未排序区间[0,8]）：重复上述操作，将未排序区间的最大值8冒泡到末尾；                - 遍历比较交换后，8移动到索引8，数组变为[1,7,2,3,5,4,6,0,8,9]；                                        - 未排序区间缩小为[0,7]，有序区间[8,9]；

3. 重复上述轮次，直到第9轮（未排序区间[0,1]），比较交换后，数组变为[0,1,2,3,4,5,6,7,8,9]，排序完成。

补充：冒泡排序的轮次 = 数组长度 - 1，每一轮的比较次数会逐轮减少（因为有序区间在扩大）。

3. C++代码实现（初学者版+优化版，适配数组/vector）

// C++ 冒泡排序（初学者版，简单易记，适配数组+vector）
#include <iostream>
#include <vector>
using namespace std;

// 适配数组的冒泡排序（升序）
void bubbleSort(int arr[], int n) {
    // 外层循环：控制排序轮次，共n-1轮
    for (int i = 0; i < n - 1; i++) {
        // 内层循环：遍历未排序区间，两两比较交换
        for (int j = 0; j < n - 1 - i; j++) {
            // 前一个元素大于后一个元素，交换（升序）
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]); // C++内置swap函数，简化代码
            }
        }
    }
}

// 适配vector的冒泡排序（C++实际练习更常用）
void bubbleSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 0; i < n - 1; i++) {
        // 优化：设置标志位，判断数组是否已有序，避免无效循环
        bool isSorted = true;
        for (int j = 0; j < n - 1 - i; j++) {
            if (vec[j] > vec[j + 1]) {
                swap(vec[j], vec[j + 1]);
                isSorted = false; // 发生交换，说明数组未有序
            }
        }
        if (isSorted) break; // 未发生交换，数组已有序，直接退出循环
    }
}

// 测试代码（初学者可直接复制运行，验证结果）
int main() {
    // 数组测试
    int arr[] = {8,9,1,7,2,3,5,4,6,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    bubbleSort(arr, n);
    cout << "数组冒泡排序结果：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // vector测试
    vector<int> vec = {8,9,1,7,2,3,5,4,6,0};
    bubbleSort(vec);
    cout << "vector冒泡排序结果：";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

4. 初学者必记（考点+特性）

• 时间复杂度：平均O(n²)，最坏O(n²)（数组逆序时），最好O(n)（数组已有序，优化版）；

• 空间复杂度：O(1)，原地排序（无额外空间消耗，仅需少量临时变量）；

• 稳定性：稳定（相邻元素交换时，相等元素不会改变相对位置）；

• C++初学者重点：① 手写冒泡排序核心代码（双重循环+相邻交换）；② 掌握标志位优化的逻辑（面试基础加分）；③ 理解“轮次”与“比较次数”的关系。

---

二、选择排序（Selection Sort）—— 减少交换次数的基础排序

选择排序是对冒泡排序的简单优化，核心逻辑是“每一轮找到未排序区间的最小值（升序），将其与未排序区间的第一个元素交换”，相比冒泡排序，减少了交换次数，效率略高，逻辑同样简单，适合初学者理解“选择”的排序思维。

1. 核心原理（通俗化理解）

核心逻辑：将数组分为“有序区间”和“未排序区间”，初始时有序区间为空，未排序区间为整个数组；每一轮从“未排序区间”中找到最小值（升序），将其与未排序区间的第一个元素交换，此时有序区间扩大一位，未排序区间缩小一位；重复此过程，直到未排序区间为空。

与冒泡排序的区别：冒泡排序是“相邻交换”，每轮可能交换多次；选择排序是“找到最小值后，只交换一次”，减少了交换操作，在数据量较小时，效率更优。

C++初学者补充：选择排序的核心是“找最小值+交换”，同样需要双重循环，外层控制轮次，内层负责找到未排序区间的最小值索引。

2. 分步拆解（升序为例，数组[8,9,1,7,2,3,5,4,6,0]）

1. 第1轮（有序区间空，未排序区间[0,9]）：找到未排序区间的最小值0，与未排序区间第一个元素8交换；                                                                                                                              - 未排序区间最小值为0（索引9），交换8和0 → [0,9,1,7,2,3,5,4,6,8]；                                  - 有序区间变为[0]，未排序区间缩小为[1,9]；

2. 第2轮（未排序区间[1,9]）：找到未排序区间的最小值1，与未排序区间第一个元素9交换；   - 最小值1（索引2），交换9和1 → [0,1,9,7,2,3,5,4,6,8]；                                                       - 有序区间变为[0,1]，未排序区间缩小为[2,9]；

3. 重复上述轮次，每一轮找到未排序区间的最小值，与区间第一个元素交换，直到第9轮，有序区间覆盖整个数组 → [0,1,2,3,4,5,6,7,8,9]，排序完成。

3. C++代码实现（初学者版，适配数组/vector）

// C++ 选择排序（初学者版，简单易记，适配数组+vector）
#include <iostream>
#include <vector>
using namespace std;

// 适配数组的选择排序（升序）
void selectionSort(int arr[], int n) {
    // 外层循环：控制有序区间的扩大，共n-1轮
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i; // 假设未排序区间第一个元素是最小值，记录其索引
        // 内层循环：遍历未排序区间，找到最小值的索引
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j; // 更新最小值索引
            }
        }
        // 将最小值与未排序区间第一个元素交换
        if (minIndex != i) { // 避免自身交换（优化，可选）
            swap(arr[i], arr[minIndex]);
        }
    }
}

// 适配vector的选择排序
void selectionSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 0; i < n - 1; i++) {
        int minIndex = i;
        // 遍历未排序区间，寻找最小值索引
        for (int j = i + 1; j < n; j++) {
            if (vec[j] < vec[minIndex]) {
                minIndex = j;
            }
        }
        // 交换最小值与未排序区间第一个元素
        if (minIndex != i) {
            swap(vec[i], vec[minIndex]);
        }
    }
}

// 测试代码
int main() {
    // 数组测试
    int arr[] = {8,9,1,7,2,3,5,4,6,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    selectionSort(arr, n);
    cout << "数组选择排序结果：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // vector测试
    vector<int> vec = {8,9,1,7,2,3,5,4,6,0};
    selectionSort(vec);
    cout << "vector选择排序结果：";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

4. 初学者必记（考点+特性）

• 时间复杂度：平均O(n²)，最坏O(n²)，最好O(n²)（无论数组是否有序，都要遍历找最小值，无法优化）；

• 空间复杂度：O(1)，原地排序；

• 稳定性：不稳定（交换最小值与区间第一个元素时，可能改变相等元素的相对位置）；

• C++初学者重点：① 手写选择排序核心代码（找最小值索引+交换）；② 区分选择排序与冒泡排序的区别（交换次数不同）；③ 理解“有序区间”与“未排序区间”的划分。

---

三、插入排序（Insertion Sort）—— 接近实际应用的初阶排序

插入排序是初阶排序中最接近实际应用的算法，核心逻辑类似于“整理扑克牌”——将未排序的元素，逐个插入到已排序区间的合适位置，使已排序区间始终有序。其效率在数据接近有序时极高，是初阶排序中实用性较强的一种，也是后续学习希尔排序（进阶）的基础。

1. 核心原理（通俗化理解）

核心逻辑：将数组分为“有序区间”和“未排序区间”，初始时有序区间只有数组的第一个元素，未排序区间从第二个元素开始；每一轮从“未排序区间”中取出第一个元素，将其插入到“有序区间”的合适位置（大于该元素的元素后移），使有序区间扩大一位；重复此过程，直到未排序区间为空。

关键特点：插入排序的效率与数组的有序程度正相关——数组越接近有序，插入时移动的元素越少，效率越高；当数组完全有序时，效率接近O(n)。

C++初学者补充：插入排序的核心是“取出元素+寻找插入位置+元素后移”，内层循环负责寻找插入位置并移动元素，逻辑比冒泡、选择排序稍复杂，但实用性更强。

2. 分步拆解（升序为例，数组[8,9,1,7,2,3,5,4,6,0]）

1. 第1轮（有序区间[8]，未排序区间[9,1,7,2,3,5,4,6,0]）：取出未排序区间第一个元素9，插入有序区间； - 9>8，直接插入到8后面，有序区间变为[8,9]，未排序区间缩小为[1,7,2,3,5,4,6,0]；

2. 第2轮（未排序区间[1,7,...]）：取出元素1，插入有序区间[8,9]； - 1<8，将8、9依次后移，插入1到最前面，有序区间变为[1,8,9]，未排序区间缩小为[7,2,3,5,4,6,0]；

3. 第3轮（未排序区间[7,...]）：取出元素7，插入有序区间[1,8,9]； - 7>1且7<8，将8、9后移，插入7到1后面，有序区间变为[1,7,8,9]；

4. 重复上述轮次，逐个将未排序区间的元素插入到有序区间的合适位置，最终有序区间覆盖整个数组 → [0,1,2,3,4,5,6,7,8,9]，排序完成。

3. C++代码实现（初学者版，适配数组/vector）

// C++ 插入排序（初学者版，简单易记，适配数组+vector）
#include <iostream>
#include <vector>
using namespace std;

// 适配数组的插入排序（升序）
void insertionSort(int arr[], int n) {
    // 外层循环：控制未排序区间，从第二个元素开始（索引1）
    for (int i = 1; i < n; i++) {
        int temp = arr[i]; // 暂存未排序区间的第一个元素，避免被后移元素覆盖
        int j = i - 1; // 有序区间的最后一个元素索引
        // 内层循环：寻找插入位置，将大于temp的元素后移
        while (j >= 0 && arr[j] > temp) {
            arr[j + 1] = arr[j]; // 元素后移
            j--; // 向前移动，继续寻找插入位置
        }
        arr[j + 1] = temp; // 将temp插入到合适位置
    }
}

// 适配vector的插入排序
void insertionSort(vector<int>& vec) {
    int n = vec.size();
    for (int i = 1; i < n; i++) {
        int temp = vec[i];
        int j = i - 1;
        // 寻找插入位置，元素后移
        while (j >= 0 && vec[j] > temp) {
            vec[j + 1] = vec[j];
            j--;
        }
        vec[j + 1] = temp; // 插入元素
    }
}

// 测试代码
int main() {
    // 数组测试
    int arr[] = {8,9,1,7,2,3,5,4,6,0};
    int n = sizeof(arr) / sizeof(arr[0]);
    insertionSort(arr, n);
    cout << "数组插入排序结果：";
    for (int i = 0; i < n; i++) {
        cout << arr[i] << " ";
    }
    cout << endl;

    // vector测试
    vector<int> vec = {8,9,1,7,2,3,5,4,6,0};
    insertionSort(vec);
    cout << "vector插入排序结果：";
    for (int num : vec) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

4. 初学者必记（考点+特性）

• 时间复杂度：平均O(n²)，最坏O(n²)（数组逆序时），最好O(n)（数组已有序时）；

• 空间复杂度：O(1)，原地排序；

• 稳定性：稳定（插入时，相等元素会插入到原有相等元素的后面，不改变相对位置）；

• C++初学者重点：① 手写插入排序核心代码（暂存元素+元素后移+插入）；② 理解插入排序的适用场景（数据接近有序时）；③ 记住插入排序是后续希尔排序的基础。

---

四、C++初阶排序算法对比（初学者必背）

初学者容易混淆三种初阶排序的特性，整理成表格，一目了然，方便记忆和区分，也是面试中基础提问的重点：

排序算法	时间复杂度（平均）	空间复杂度	稳定性	核心特点（初学者易懂）	适用场景
冒泡排序	O(n²)	O(1)	稳定	相邻元素两两交换，逻辑最简单，交换次数多	初学者入门、数据量极小（百级以内）
选择排序	O(n²)	O(1)	不稳定	找最小值再交换，交换次数少，效率略高于冒泡	数据量小、对交换次数敏感的场景
插入排序	O(n²)	O(1)	稳定	插入到有序区间，数据接近有序时效率极高	数据接近有序、小型数据排序（实际应用较广）

---

五、C++初学者避坑指南（初阶排序必看）

初学者在手写初阶排序代码时，容易踩以下4个坑，提前避开，练习更高效，面试更稳妥：

• 坑1：冒泡排序忘记优化标志位——数组已有序时，仍会执行所有轮次，浪费时间，记住添加标志位判断是否已有序；

• 坑2：选择排序找最小值时，直接交换元素而非记录索引——会导致多次无效交换，正确做法是先找到最小值索引，再交换一次；

• 坑3：插入排序忘记暂存元素——直接移动元素会覆盖未排序区间的第一个元素，必须先暂存该元素，再进行后移操作；

• 坑4：循环边界写错（最常见）——比如冒泡排序内层循环写成j < n，选择排序外层循环写成i < n，插入排序while循环j没有>=0判断，导致数组越界，牢记各算法的循环边界。

---

六、C++初阶排序学习总结与建议

C++初阶排序的学习，核心是“理解逻辑、勤练手写、区分特性”，不用追求高效，重点是打好基础，为后续进阶排序（希尔、快排等）铺路，记住以下3个学习重点：

1. 先理解，再手写：不要死记代码，先搞懂每种算法的核心逻辑（比如冒泡是“相邻交换”，选择是“找最小值交换”，插入是“插入有序区间”），再动手写代码，每天练1遍，直到能脱稿写出；

2. 多对比，多思考：对比三种算法的交换次数、稳定性、适用场景，思考“为什么插入排序在实际中更常用”“什么时候选择冒泡/选择排序”，培养排序选型思维；

3. 练基础，避坑点：重点练习循环边界、元素暂存、标志位优化等细节，避免常见错误，确保代码能直接运行，这是面试基础编程题的核心要求。

初阶排序是C++数据结构排序的入门基础，看似简单，但能帮你建立“比较-交换-排序”的核心思维，掌握好这三种算法，后续学习进阶排序时，能更快理解“优化逻辑”（比如希尔排序是插入排序的进阶，快排是选择排序的延伸）。

小练习：用C++手写插入排序，对数组[5,3,8,4,2,7,1,6]进行升序排序，试试能不能写出完整代码？欢迎在评论区交流你的思路～