不爱吃饭的蓝胖子要开始整活了！！！

大家好，我是蓝胖子！好久不见，倍感思念！今天带来的是--C++排序算法~~

希望你能看到最后，有惊喜哈！

--------------------------------------------------------------------------------------

标签： C++、排序算法、数据结构、算法入门、面试必备
适合人群： 有 C++ 基础，想系统掌握排序算法的同学

---

前言

排序，是程序员日常工作中接触最频繁的操作之一。从数据库的 ORDER BY，到搜索引擎的结果排名，背后都离不开排序算法的身影。

本文将带你系统梳理 8 大经典排序算法，每一种都包含：

• 📊 图解演示过程
• 💻 C++ 完整代码
• ⏱ 时间/空间复杂度分析
• 🎯 适用场景总结

废话不多说，开始！

---

排序算法总览

算法	平均时间复杂度	最坏时间复杂度	空间复杂度	稳定性
冒泡排序	O(n²)	O(n²)	O(1)	✅ 稳定
选择排序	O(n²)	O(n²)	O(1)	❌ 不稳定
插入排序	O(n²)	O(n²)	O(1)	✅ 稳定
希尔排序	O(n log n)	O(n²)	O(1)	❌ 不稳定
归并排序	O(n log n)	O(n log n)	O(n)	✅ 稳定
快速排序	O(n log n)	O(n²)	O(log n)	❌ 不稳定
堆排序	O(n log n)	O(n log n)	O(1)	❌ 不稳定
计数排序	O(n + k)	O(n + k)	O(k)	✅ 稳定

---

一、冒泡排序（Bubble Sort）

原理图解

每轮遍历把最大的元素"冒泡"到末尾，就像气泡浮到水面一样。

初始：  [5, 3, 8, 1, 2]

第1轮：
  5>3 → 交换 → [3, 5, 8, 1, 2]
  5<8 → 不换 → [3, 5, 8, 1, 2]
  8>1 → 交换 → [3, 5, 1, 8, 2]
  8>2 → 交换 → [3, 5, 1, 2, 8]  ← 8 就位 ✅

第2轮：
  3<5 → 不换 → [3, 5, 1, 2, 8]
  5>1 → 交换 → [3, 1, 5, 2, 8]
  5>2 → 交换 → [3, 1, 2, 5, 8]  ← 5 就位 ✅

...以此类推

C++ 代码

#include <iostream>
#include <vector>
using namespace std;

void bubbleSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        bool swapped = false;  // 优化：若本轮没有交换，说明已有序，提前退出
        for (int j = 0; j < n - 1 - i; j++) {
            if (arr[j] > arr[j + 1]) {
                swap(arr[j], arr[j + 1]);
                swapped = true;
            }
        }
        if (!swapped) break;
    }
}

int main() {
    vector<int> arr = {5, 3, 8, 1, 2};
    bubbleSort(arr);
    for (int x : arr) cout << x << " ";  // 1 2 3 5 8
    return 0;
}

特点总结

• ✅ 实现最简单，适合入门理解
• ✅ 数据基本有序时，加 swapped 优化后接近 O(n)
• ❌ 数据量大时性能差，不推荐实际使用

---

二、选择排序（Selection Sort）

原理图解

每轮从未排序部分找到最小值，放到已排序部分的末尾。

初始：  [5, 3, 8, 1, 2]
         ↑ 从这里找最小值

第1轮：最小值 = 1（索引3），与索引0交换
       [1, 3, 8, 5, 2]  ← 1 就位 ✅

第2轮：最小值 = 2（索引4），与索引1交换
       [1, 2, 8, 5, 3]  ← 2 就位 ✅

第3轮：最小值 = 3（索引4），与索引2交换
       [1, 2, 3, 5, 8]  ← 3 就位 ✅
...

C++ 代码

void selectionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 0; i < n - 1; i++) {
        int minIdx = i;
        for (int j = i + 1; j < n; j++) {
            if (arr[j] < arr[minIdx]) {
                minIdx = j;
            }
        }
        if (minIdx != i) swap(arr[i], arr[minIdx]);
    }
}

特点总结

• ✅ 交换次数少，只有 O(n) 次，适合交换代价大的场景
• ❌ 比较次数始终是 O(n²)，不受初始顺序影响
• ❌ 不稳定：[5a, 5b, 1] 第一轮会把 1 和 5a 交换，5a 和 5b 相对顺序改变

---

三、插入排序（Insertion Sort）

原理图解

就像整理扑克牌：每次取一张新牌，插入到已排好的牌堆中正确位置。

初始：  [5, 3, 8, 1, 2]

i=1: 取出 3，与 5 比较，3<5 → 5 右移，3 插入
     [3, 5, 8, 1, 2]

i=2: 取出 8，8>5 → 不动
     [3, 5, 8, 1, 2]

i=3: 取出 1，1<8→移，1<5→移，1<3→移，1 插入头部
     [1, 3, 5, 8, 2]

i=4: 取出 2，2<8→移，2<5→移，2<3→移，2>1→停，2 插入
     [1, 2, 3, 5, 8]  ✅

C++ 代码

void insertionSort(vector<int>& arr) {
    int n = arr.size();
    for (int i = 1; i < n; i++) {
        int key = arr[i];
        int j = i - 1;
        // 将比 key 大的元素向右移动
        while (j >= 0 && arr[j] > key) {
            arr[j + 1] = arr[j];
            j--;
        }
        arr[j + 1] = key;
    }
}

特点总结

• ✅ 数据基本有序时接近 O(n)，实际表现很好
• ✅ 稳定，原地排序
• ✅ 小数据量下比快排快（常见优化：元素数量 < 16 时用插入排序）

---

四、希尔排序（Shell Sort）

原理图解

插入排序的改进版：先对间距较大的元素进行插入排序，让数据"宏观有序"，再缩小间距，最终变为普通插入排序。

初始：  [8, 3, 1, 5, 2, 7, 4, 6]，gap = 4

gap=4：对 (8,2), (3,7), (1,4), (5,6) 分别插入排序
       [2, 3, 1, 5, 8, 7, 4, 6]
       → [2, 3, 1, 5, 8, 7, 4, 6]

gap=2：对间距2的子序列插入排序
       ...

gap=1：普通插入排序（此时已接近有序，很快）

C++ 代码

void shellSort(vector<int>& arr) {
    int n = arr.size();
    // 使用 Knuth 序列：1, 4, 13, 40, 121, ...
    int gap = 1;
    while (gap < n / 3) gap = gap * 3 + 1;

    while (gap >= 1) {
        for (int i = gap; i < n; i++) {
            int key = arr[i];
            int j = i - gap;
            while (j >= 0 && arr[j] > key) {
                arr[j + gap] = arr[j];
                j -= gap;
            }
            arr[j + gap] = key;
        }
        gap /= 3;
    }
}

特点总结

• ✅ 比插入排序快得多，实际性能接近 O(n^1.3)
• ✅ 原地排序，空间复杂度 O(1)
• ❌ 不稳定，时间复杂度分析复杂（取决于 gap 序列选择）

---

五、归并排序（Merge Sort）

原理图解

分治思想：把数组不断二分，再将有序的两半合并。

[5, 3, 8, 1, 2, 7, 4, 6]

分：
  [5, 3, 8, 1]    [2, 7, 4, 6]
  [5,3] [8,1]     [2,7] [4,6]
  [5][3] [8][1]   [2][7] [4][6]

合（有序合并）：
  [3,5] [1,8]     [2,7] [4,6]
  [1,3,5,8]       [2,4,6,7]
  [1,2,3,4,5,6,7,8]  ✅

C++ 代码

void merge(vector<int>& arr, int left, int mid, int right) {
    vector<int> temp(right - left + 1);
    int i = left, j = mid + 1, k = 0;

    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j])  // <= 保证稳定性
            temp[k++] = arr[i++];
        else
            temp[k++] = arr[j++];
    }
    while (i <= mid)  temp[k++] = arr[i++];
    while (j <= right) temp[k++] = arr[j++];

    for (int x = 0; x < k; x++)
        arr[left + x] = temp[x];
}

void mergeSort(vector<int>& arr, int left, int right) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
}

// 调用方式：mergeSort(arr, 0, arr.size() - 1);

特点总结

• ✅ 稳定，且时间复杂度恒为 O(n log n)
• ✅ 适合链表排序（不需要随机访问）
• ❌ 需要 O(n) 额外空间，内存开销较大

---

六、快速排序（Quick Sort）⭐ 最常用

原理图解

选一个基准值（pivot），把比它小的放左边，比它大的放右边，然后递归处理两侧。

初始：[5, 3, 8, 1, 2, 7, 4, 6]，选 pivot = 5

分区后：[3, 1, 2, 4 | 5 | 8, 7, 6]
                      ↑ pivot 就位 ✅

左侧 [3,1,2,4] 递归，右侧 [8,7,6] 递归...

最终：[1, 2, 3, 4, 5, 6, 7, 8]  ✅

C++ 代码（三种写法）

写法一：经典 Lomuto 分区

int partition(vector<int>& arr, int low, int high) {
    int pivot = arr[high];  // 选最后一个元素作为基准
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] <= pivot) {
            i++;
            swap(arr[i], arr[j]);
        }
    }
    swap(arr[i + 1], arr[high]);
    return i + 1;
}

void quickSort(vector<int>& arr, int low, int high) {
    if (low < high) {
        int pi = partition(arr, low, high);
        quickSort(arr, low, pi - 1);
        quickSort(arr, pi + 1, high);
    }
}

写法二：随机化快排（推荐，避免最坏情况）

int partitionRandom(vector<int>& arr, int low, int high) {
    // 随机选择 pivot，避免有序数组退化为 O(n²)
    int randIdx = low + rand() % (high - low + 1);
    swap(arr[randIdx], arr[high]);
    return partition(arr, low, high);
}

写法三：三路快排（处理大量重复元素）

void quickSort3Way(vector<int>& arr, int low, int high) {
    if (low >= high) return;
    int pivot = arr[low];
    int lt = low, gt = high, i = low + 1;
    // lt: <pivot 的右边界; gt: >pivot 的左边界; i: 当前处理位置
    while (i <= gt) {
        if      (arr[i] < pivot) swap(arr[lt++], arr[i++]);
        else if (arr[i] > pivot) swap(arr[i], arr[gt--]);
        else                     i++;
    }
    // arr[low..lt-1] < pivot = arr[lt..gt] < arr[gt+1..high]
    quickSort3Way(arr, low, lt - 1);
    quickSort3Way(arr, gt + 1, high);
}

特点总结

• ✅ 实际性能最好，常数系数小，缓存友好
• ✅ 原地排序，空间复杂度 O(log n)
• ❌ 不稳定
• ❌ 最坏 O(n²)（有序数组 + 固定选末尾为 pivot），用随机化可规避

💡 小知识： C++ STL 的 std::sort 使用的是 Introsort（内省排序）= 快排 + 堆排序 + 插入排序的组合，兼顾了各自的优点。

---

七、堆排序（Heap Sort）

原理图解

利用二叉堆的特性：最大堆的堆顶始终是最大值，反复取出堆顶即可得到有序序列。

初始：[5, 3, 8, 1, 2]

建大根堆：[8, 3, 5, 1, 2]
           8
          / \
         3   5
        / \
       1   2

步骤1：堆顶 8 与末尾 2 交换 → [2, 3, 5, 1, | 8]，堆大小-1，重新堆化
步骤2：堆顶 5 与末尾 1 交换 → [1, 3, 2, | 5, 8]，堆大小-1，重新堆化
...
最终：[1, 2, 3, 5, 8]  ✅

C++ 代码

// 对以 i 为根的子树进行堆化（下沉操作）
void heapify(vector<int>& arr, int n, int i) {
    int largest = i;
    int left  = 2 * i + 1;
    int right = 2 * i + 2;

    if (left  < n && arr[left]  > arr[largest]) largest = left;
    if (right < n && arr[right] > arr[largest]) largest = right;

    if (largest != i) {
        swap(arr[i], arr[largest]);
        heapify(arr, n, largest);  // 递归修复
    }
}

void heapSort(vector<int>& arr) {
    int n = arr.size();
    // 1. 建大根堆（从最后一个非叶节点开始）
    for (int i = n / 2 - 1; i >= 0; i--)
        heapify(arr, n, i);

    // 2. 逐一取出堆顶（最大值），放到末尾
    for (int i = n - 1; i > 0; i--) {
        swap(arr[0], arr[i]);
        heapify(arr, i, 0);
    }
}

特点总结

• ✅ 时间复杂度恒为 O(n log n)，不受数据分布影响
• ✅ 原地排序，空间 O(1)
• ❌ 不稳定
• ❌ 缓存不友好（频繁跳跃访问内存），实际比快排慢

---

八、计数排序（Counting Sort）

原理图解

非比较类排序：统计每个值出现的次数，直接"写"回结果，不需要比较！

输入：[4, 2, 2, 8, 3, 3, 1]

计数数组 count（索引代表值）：
index: 0  1  2  3  4  5  6  7  8
count: 0  1  2  2  1  0  0  0  1

按计数还原：1, 2, 2, 3, 3, 4, 8  ✅

C++ 代码

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());
    int range  = maxVal - minVal + 1;

    vector<int> count(range, 0);
    for (int x : arr) count[x - minVal]++;

    int idx = 0;
    for (int i = 0; i < range; i++)
        while (count[i]-- > 0)
            arr[idx++] = i + minVal;
}

特点总结

• ✅ 时间复杂度 O(n + k)，当 k（值域范围）较小时极快
• ✅ 稳定
• ❌ 只适用于整数，且值域不能太大（否则 count 数组占内存过多）
• 典型场景：年龄排序、成绩排序、字母排序

---

九、完整测试代码

把所有排序算法放在一起，统一测试：

#include <iostream>
#include <vector>
#include <algorithm>
#include <cstdlib>
#include <ctime>
using namespace std;

// ... （将上面各算法函数粘贴至此）

void printArr(const string& name, vector<int> arr) {
    cout << name << ": ";
    for (int x : arr) cout << x << " ";
    cout << endl;
}

int main() {
    srand(time(0));
    vector<int> original = {5, 3, 8, 1, 2, 7, 4, 6};

    vector<int> a1 = original; bubbleSort(a1);    printArr("冒泡排序", a1);
    vector<int> a2 = original; selectionSort(a2); printArr("选择排序", a2);
    vector<int> a3 = original; insertionSort(a3); printArr("插入排序", a3);
    vector<int> a4 = original; shellSort(a4);     printArr("希尔排序", a4);
    vector<int> a5 = original; mergeSort(a5, 0, a5.size()-1); printArr("归并排序", a5);
    vector<int> a6 = original; quickSort(a6, 0, a6.size()-1); printArr("快速排序", a6);
    vector<int> a7 = original; heapSort(a7);      printArr("堆排序  ", a7);
    vector<int> a8 = original; countingSort(a8);  printArr("计数排序", a8);

    return 0;
}

运行结果（全部相同）：

冒泡排序: 1 2 3 4 5 6 7 8
选择排序: 1 2 3 4 5 6 7 8
插入排序: 1 2 3 4 5 6 7 8
希尔排序: 1 2 3 4 5 6 7 8
归并排序: 1 2 3 4 5 6 7 8
快速排序: 1 2 3 4 5 6 7 8
堆排序  : 1 2 3 4 5 6 7 8
计数排序: 1 2 3 4 5 6 7 8

---

十、如何选择排序算法？

数据量很小（< 20）？
    → 插入排序（简单，常数小）

需要稳定排序？
    → 归并排序（稳定，O(n log n)）

整数且值域小？
    → 计数排序（O(n)，最快）

通用场景（大多数时候）？
    → 快速排序（最快的实践者）

不能用额外空间，且不怕不稳定？
    → 堆排序（保证 O(n log n)，O(1) 空间）

---

总结

算法	核心思想	记忆口诀
冒泡	相邻比较，大的往后沉	大的冒泡到末尾
选择	每轮找最小，放到前面	选最小，放前面
插入	取牌插入有序区	整理扑克牌
希尔	大间距插入排序	跳着插入
归并	分治+有序合并	分而治之
快排	基准分左右，递归搞定	找基准，分两边
堆排	大根堆不断取顶	堆顶是最大值
计数	统计次数，直接写回	数数就能排

排序算法是算法学习的基础，掌握它们不仅能应对面试，更能深化对分治、递归、数据结构的理解。

如果这篇文章对你有帮助，欢迎点赞 👍 + 收藏 ⭐！有问题欢迎评论区交流～

本文花费了蓝胖子的大量心血，也请大家尊重原创，不要转载，谢谢！！！