C++经典的数据结构与算法之经典算法思想：排序算法

排序算法：从基础到高效的演进

排序算法是计算机科学中最基础也最常用的算法类别，它将一组无序数据按照特定顺序（升序或降序）排列。不同的排序算法在时间复杂度、空间复杂度和稳定性上各有优劣，选择合适的排序算法对程序性能至关重要。本文将详细介绍C++中常用的经典排序算法，包括实现原理、代码实现和性能分析。

一、排序算法的分类与评价标准

分类：

• 比较类排序：通过比较元素大小决定顺序（如冒泡、插入、快排、归并）。
• 非比较类排序：不通过比较，利用数据特性排序（如计数、基数、桶排序）。

评价标准：

• 时间复杂度：最好、最坏、平均情况下的执行时间。
• 空间复杂度：算法所需额外空间。
• 稳定性：相等元素的相对顺序是否保持不变。
• 原地性：是否只需O(1)或O(log n)的额外空间。

二、基础排序算法（时间复杂度O(n²)）

1. 冒泡排序（Bubble Sort）

思想：重复遍历数组，每次比较相邻元素，若顺序错误则交换，使大元素"浮"到末端。

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 - i - 1; j++) {if (arr[j] > arr[j + 1]) {swap(arr[j], arr[j + 1]);swapped = true;}}if (!swapped) break; // 无交换说明已有序，提前退出}
}

特性：稳定，原地排序，最好情况O(n)（已排序），最坏O(n²)。

2. 选择排序（Selection Sort）

思想：每次从剩余元素中找到最小值，放到已排序部分的末尾。

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;}}swap(arr[i], arr[minIdx]); // 放到已排序部分末尾}
}

特性：不稳定（交换可能改变相等元素顺序），原地排序，时间复杂度始终O(n²)。

3. 插入排序（Insertion Sort）

思想：将元素逐个插入到已排序部分的合适位置，类似整理扑克牌。

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; // 插入key}
}

特性：稳定，原地排序，最好O(n)（已排序），最坏O(n²)，适合小规模或近乎有序的数据。

三、高效排序算法（时间复杂度O(n log n)）

1. 归并排序（Merge Sort）

思想：分治法，将数组递归分成两半，排序后合并为有序数组。

#include <vector>
using namespace std;// 合并两个有序子数组
void merge(vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组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(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);        // 合并}
}// 对外接口
void mergeSort(vector<int>& arr) {if (arr.empty()) return;mergeSort(arr, 0, arr.size() - 1);
}

特性：稳定，非原地排序（需O(n)额外空间），时间复杂度始终O(n log n)，适合大数据量排序。

2. 快速排序（Quick Sort）

思想：分治法，选择一个基准元素，将数组分为"小于基准"和"大于基准"两部分，递归排序。

#include <vector>
#include <random>
using namespace std;// 随机选择基准并分区
int partition(vector<int>& arr, int left, int right) {// 随机选择基准（避免最坏情况）int pivotIdx = left + rand() % (right - left + 1);swap(arr[pivotIdx], arr[right]);int pivot = arr[right];int i = left - 1; // 小于基准区域的边界for (int j = left; j < right; j++) {if (arr[j] <= pivot) { // 小于等于基准的元素移到左侧i++;swap(arr[i], arr[j]);}}swap(arr[i + 1], arr[right]); // 基准放到最终位置return i + 1; // 返回基准索引
}// 快速排序主函数
void quickSort(vector<int>& arr, int left, int right) {if (left < right) {int pivotPos = partition(arr, left, right); // 分区quickSort(arr, left, pivotPos - 1);         // 排序左半quickSort(arr, pivotPos + 1, right);        // 排序右半}
}// 对外接口
void quickSort(vector<int>& arr) {if (arr.empty()) return;srand(time(0)); // 初始化随机数种子quickSort(arr, 0, arr.size() - 1);
}

特性：不稳定，原地排序（需O(log n)递归栈空间），平均O(n log n)，最坏O(n²)（可通过随机基准避免），实际应用中最快的排序算法之一。

3. 堆排序（Heap Sort）

思想：利用最大堆（或最小堆）的特性，反复提取堆顶元素（最大值）并调整堆。

#include <vector>
using namespace std;// 最大堆下沉操作
void maxHeapify(vector<int>& arr, int size, int i) {int largest = i;int left = 2 * i + 1;int right = 2 * i + 2;if (left < size && arr[left] > arr[largest]) largest = left;if (right < size && arr[right] > arr[largest]) largest = right;if (largest != i) {swap(arr[i], arr[largest]);maxHeapify(arr, size, largest);}
}// 堆排序
void heapSort(vector<int>& arr) {int n = arr.size();// 构建最大堆for (int i = n / 2 - 1; i >= 0; i--) {maxHeapify(arr, n, i);}// 提取最大值并调整堆for (int i = n - 1; i > 0; i--) {swap(arr[0], arr[i]); // 根节点（最大值）移到末尾maxHeapify(arr, i, 0); // 调整剩余元素为最大堆}
}

特性：不稳定，原地排序，时间复杂度始终O(n log n)，适合内存受限场景。

四、非比较类排序算法

1. 计数排序（Counting Sort）

思想：适用于整数排序，通过统计每个元素的出现次数，直接计算元素的最终位置。

#include <vector>
#include <algorithm>
using namespace std;void countingSort(vector<int>& arr) {if (arr.empty()) return;// 找到最大值和最小值int minVal = *min_element(arr.begin(), arr.end());int maxVal = *max_element(arr.begin(), arr.end());int range = maxVal - minVal + 1;// 计数数组和结果数组vector<int> count(range, 0);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)，适合小范围整数排序。

五、排序算法对比与选择

算法	平均时间	最坏时间	空间复杂度	稳定性	原地性	适用场景
冒泡排序	O(n²)	O(n²)	O(1)	稳定	是	小规模数据
插入排序	O(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(n + k)	稳定	否	小范围整数（如年龄、分数）

选择建议：

• 小规模数据（n < 100）：插入排序或冒泡排序。
• 中等规模数据：快速排序（实际性能最优）。
• 大规模数据：归并排序（稳定）或堆排序（内存紧张）。
• 特殊场景：整数且范围小用计数排序，链表排序用归并排序。

六、C++标准库中的排序函数

C++标准库提供了std::sort和std::stable_sort：

• std::sort：通常基于快速排序的优化版本（如 introsort），不稳定，平均O(n log n)。
• std::stable_sort：通常基于归并排序，稳定，平均O(n log n)。

#include <algorithm>
#include <vector>
#include <iostream>int main() {vector<int> arr = {3, 1, 4, 1, 5, 9, 2, 6};// 快速排序（不稳定）sort(arr.begin(), arr.end());// 归并排序（稳定）stable_sort(arr.begin(), arr.end());for (int num : arr) {cout << num << " ";}return 0;
}

总结

排序算法是算法设计的基础，每种算法都有其适用场景。理解不同排序算法的原理和特性，不仅能帮助我们在实际开发中选择最优方案，更能培养算法设计的思维。从简单的冒泡排序到高效的快速排序，排序算法的演进体现了从直观到优化的思维过程，是学习算法分析与设计的绝佳案例。

在实际开发中，除非有特殊需求，否则应优先使用C++标准库的排序函数，它们经过高度优化，能适应大多数场景并提供出色的性能。