1. 引言排序是计算机科学中最基础、最核心的算法之一也是 C 程序员必须掌握的基本功。无论是处理用户数据、优化搜索效率还是作为更复杂算法如图算法、动态规划的预处理步骤排序都扮演着至关重要的角色。C 标准库STL提供了强大而灵活的排序工具同时我们也可以手动实现各种经典排序算法来深入理解其原理。本文将系统介绍 C 中的各种排序方式包括STL 内置排序函数std::sort、std::stable_sort等基础排序算法冒泡、选择、插入排序高效排序算法快速排序、归并排序、堆排序特殊场景排序计数排序、基数排序自定义数据结构的排序方法2. STL 内置排序函数C 标准库在algorithm头文件中提供了多种排序函数这是最常用、最高效的排序方式。2.1 std::sortstd::sort是使用最广泛的排序函数通常采用快速排序的变体IntroSort在平均情况下具有 O(n log n) 的时间复杂度。#include iostream #include vector #include algorithm int main() { std::vectorint 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::greaterint()); // 输出结果9 8 5 3 2 1 for (int num : nums) { std::cout num ; } return 0; }2.2 std::stable_sortstd::stable_sort保证相等元素的相对顺序不变稳定排序通常采用归并排序实现。#include algorithm #include vector #include string struct Student { std::string name; int score; }; int main() { std::vectorStudent 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_sortstd::partial_sort只对序列的前 k 个元素进行排序其余元素不保证顺序。#include algorithm #include vector #include iostream int main() { std::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint arr, int left, int mid, int right) { int n1 mid - left 1; int n2 right - mid; std::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint 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::vectorint count(range, 0); std::vectorint 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::vectorint arr, int exp) { int n arr.size(); std::vectorint 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::vectorint 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::vectorPerson people { {Alice, 25, 50000}, {Bob, 30, 60000}, {Charlie, 25, 45000}, {David, 30, 55000} }; std::sort(people.begin(), people.end()); return 0; }6.2 使用自定义比较函数bool compareBySalary(const Pers