C++ 排序算法全解析：从基础到实战-拓冰建站

1. 引言

排序是计算机科学中最基础、最核心的算法之一，也是 C++ 程序员必须掌握的基本功。无论是处理用户数据、优化搜索效率，还是作为更复杂算法（如图算法、动态规划）的预处理步骤，排序都扮演着至关重要的角色。

C++ 标准库（STL）提供了强大而灵活的排序工具，同时我们也可以手动实现各种经典排序算法来深入理解其原理。本文将系统介绍 C++ 中的各种排序方式，包括：

STL 内置排序函数（std::sort、std::stable_sort等）
基础排序算法（冒泡、选择、插入排序）
高效排序算法（快速排序、归并排序、堆排序）
特殊场景排序（计数排序、基数排序）
自定义数据结构的排序方法

2. STL 内置排序函数

C++ 标准库在<algorithm>头文件中提供了多种排序函数，这是最常用、最高效的排序方式。

2.1 std::sort

std::sort是使用最广泛的排序函数，通常采用快速排序的变体（IntroSort），在平均情况下具有 O(n log n) 的时间复杂度。

#include <iostream> #include <vector> #include <algorithm> int main() { std::vector<int> nums = {5, 2, 8, 1, 9, 3}; // 默认升序排序 std::sort(nums.begin(), nums.end()); // 输出结果：1 2 3 5 8 9 for (int num : nums) { std::cout << num << " "; } std::cout << std::endl; // 降序排序 std::sort(nums.begin(), nums.end(), std::greater<int>()); // 输出结果：9 8 5 3 2 1 for (int num : nums) { std::cout << num << " "; } return 0; }

2.2 std::stable_sort

std::stable_sort保证相等元素的相对顺序不变（稳定排序），通常采用归并排序实现。

#include <algorithm> #include <vector> #include <string> struct Student { std::string name; int score; }; int main() { std::vector<Student> students = { {"Alice", 85}, {"Bob", 85}, {"Charlie", 90}, {"David", 80} }; // 按分数排序，相同分数保持原有顺序 std::stable_sort(students.begin(), students.end(), [](const Student& a, const Student& b) { return a.score < b.score; }); // Alice 和 Bob 都是85分，他们的相对顺序保持不变 return 0; }

2.3 std::partial_sort

std::partial_sort只对序列的前 k 个元素进行排序，其余元素不保证顺序。

#include <algorithm> #include <vector> #include <iostream> int main() { std::vector<int> nums = {9, 3, 6, 1, 7, 4, 2, 8, 5}; // 只排序前5个最小的元素 std::partial_sort(nums.begin(), nums.begin() + 5, nums.end()); // 输出：1 2 3 4 5 9 7 6 8 for (int num : nums) { std::cout << num << " "; } return 0; }

3. 基础排序算法

理解基础排序算法有助于掌握排序的核心思想，虽然效率不高，但在小数据量或特殊场景下仍有价值。

3.1 冒泡排序（Bubble Sort）

冒泡排序通过重复遍历数组，比较相邻元素并交换位置，将最大（或最小）元素"冒泡"到末尾。

#include <iostream> #include <vector> void bubbleSort(std::vector<int>& arr) { int n = arr.size(); for (int i = 0; i < n - 1; i++) { bool swapped = false; for (int j = 0; j < n - i - 1; j++) { if (arr[j] > arr[j + 1]) { std::swap(arr[j], arr[j + 1]); swapped = true; } } // 如果本轮没有交换，说明已经有序 if (!swapped) break; } } int main() { std::vector<int> nums = {64, 34, 25, 12, 22, 11, 90}; bubbleSort(nums); // 输出：11 12 22 25 34 64 90 for (int num : nums) { std::cout << num << " "; } return 0; }

时间复杂度：O(n²)，最好情况 O(n)（已排序）
空间复杂度：O(1)
稳定性：稳定

3.2 选择排序（Selection Sort）

每次从未排序部分选择最小（或最大）元素，放到已排序部分的末尾。

void selectionSort(std::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; } } std::swap(arr[i], arr[minIdx]); } }

时间复杂度：O(n²)
空间复杂度：O(1)
稳定性：不稳定

3.3 插入排序（Insertion Sort）

将数组分为已排序和未排序两部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。

void insertionSort(std::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²)，最好情况 O(n)（已排序）
空间复杂度：O(1)
稳定性：稳定

4. 高效排序算法

这些算法在实际应用中更为常见，具有更好的时间复杂度。

4.1 快速排序（Quick Sort）

采用分治策略，选择一个基准元素，将数组分为两部分，递归排序。

int partition(std::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++; std::swap(arr[i], arr[j]); } } std::swap(arr[i + 1], arr[high]); return i + 1; } void quickSort(std::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 main() { std::vector<int> nums = {10, 7, 8, 9, 1, 5}; quickSort(nums, 0, nums.size() - 1); return 0; }

时间复杂度：平均 O(n log n)，最坏 O(n²)
空间复杂度：O(log n)（递归栈）
稳定性：不稳定

4.2 归并排序（Merge Sort）

采用分治策略，将数组递归分成两半，分别排序后合并。

void merge(std::vector<int>& arr, int left, int mid, int right) { int n1 = mid - left + 1; int n2 = right - mid; std::vector<int> L(n1), R(n2); for (int i = 0; i < n1; i++) L[i] = arr[left + i]; for (int j = 0; j < n2; j++) R[j] = arr[mid + 1 + j]; int i = 0, j = 0, k = left; while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } while (i < n1) { arr[k] = L[i]; i++; k++; } while (j < n2) { arr[k] = R[j]; j++; k++; } } void mergeSort(std::vector<int>& arr, int left, int right) { if (left < right) { int mid = left + (right - left) / 2; mergeSort(arr, left, mid); mergeSort(arr, mid + 1, right); merge(arr, left, mid, right); } }

时间复杂度：O(n log n)
空间复杂度：O(n)
稳定性：稳定

4.3 堆排序（Heap Sort）

利用堆数据结构进行排序，首先构建最大堆，然后反复取出堆顶元素。

void heapify(std::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) { std::swap(arr[i], arr[largest]); heapify(arr, n, largest); } } void heapSort(std::vector<int>& arr) { int n = arr.size(); // 构建最大堆 for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); // 逐个提取元素 for (int i = n - 1; i > 0; i--) { std::swap(arr[0], arr[i]); heapify(arr, i, 0); } }

时间复杂度：O(n log n)
空间复杂度：O(1)
稳定性：不稳定

5. 特殊场景排序算法

这些算法在特定条件下（如数据范围有限）可以达到线性时间复杂度。

5.1 计数排序（Counting Sort）

适用于数据范围较小的整数排序。

void countingSort(std::vector<int>& arr) { if (arr.empty()) return; // 找到最大值 int maxVal = *std::max_element(arr.begin(), arr.end()); int minVal = *std::min_element(arr.begin(), arr.end()); int range = maxVal - minVal + 1; std::vector<int> count(range, 0); std::vector<int> output(arr.size()); // 统计每个元素出现的次数 for (int num : arr) { count[num - minVal]++; } // 计算累积计数 for (int i = 1; i < range; i++) { count[i] += count[i - 1]; } // 构建输出数组 for (int i = arr.size() - 1; i >= 0; i--) { output[count[arr[i] - minVal] - 1] = arr[i]; count[arr[i] - minVal]--; } // 复制回原数组 arr = output; }

时间复杂度：O(n + k)，k 为数据范围
空间复杂度：O(n + k)
稳定性：稳定

5.2 基数排序（Radix Sort）

按位进行排序，从最低位到最高位。

void countingSortForRadix(std::vector<int>& arr, int exp) { int n = arr.size(); std::vector<int> output(n); int count[10] = {0}; // 统计当前位的出现次数 for (int i = 0; i < n; i++) { count[(arr[i] / exp) % 10]++; } // 计算累积计数 for (int i = 1; i < 10; i++) { count[i] += count[i - 1]; } // 构建输出数组 for (int i = n - 1; i >= 0; i--) { output[count[(arr[i] / exp) % 10] - 1] = arr[i]; count[(arr[i] / exp) % 10]--; } // 复制回原数组 arr = output; } void radixSort(std::vector<int>& arr) { if (arr.empty()) return; // 找到最大值 int maxVal = *std::max_element(arr.begin(), arr.end()); // 从最低位到最高位进行计数排序 for (int exp = 1; maxVal / exp > 0; exp *= 10) { countingSortForRadix(arr, exp); } }

时间复杂度：O(d * (n + k))，d 为最大位数
空间复杂度：O(n + k)
稳定性：稳定

6. 自定义数据结构的排序

在实际开发中，经常需要对自定义类型进行排序。

6.1 重载比较运算符

struct Person { std::string name; int age; double salary; // 重载小于运算符 bool operator<(const Person& other) const { // 先按年龄排序，年龄相同按薪资排序 if (age != other.age) { return age < other.age; } return salary < other.salary; } }; int main() { std::vector<Person> people = { {"Alice", 25, 50000}, {"Bob", 30, 60000}, {"Charlie", 25, 45000}, {"David", 30, 55000} }; std::sort(people.begin(), people.end()); return 0; }