C++排序算法完全指南
全面比较各种排序算法的时间复杂度、空间复杂度和稳定性，助你选择最适合的排序方法
排序算法概述
排序是计算机科学中的基本操作，有多种算法可以实现。不同的排序算法在时间复杂度、空间复杂度和稳定性等方面有不同的表现。选择合适的排序算法对于优化程序性能至关重要。
时间复杂度
时间复杂度是衡量算法执行效率的指标，表示算法的执行时间与输入数据规模之间的增长关系。通常用大O符号表示。
空间复杂度
空间复杂度是衡量算法执行过程中所需额外存储空间的指标，表示算法的空间需求与输入数据规模之间的增长关系。
稳定性
排序算法的稳定性是指在排序过程中，相等元素的相对顺序是否保持不变。稳定的排序算法能够保持相等元素的原始顺序。
排序算法综合比较
以下是常见排序算法的综合比较，包括时间复杂度、空间复杂度和稳定性等指标。
| 排序算法 | 最优时间复杂度 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 排序方式 | 适用场景 |
|---|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | In-place | 小规模数据排序 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 不稳定 | In-place | 小规模数据排序 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 稳定 | In-place | 小规模或基本有序数据排序 |
| 希尔排序 | O(n log n) | O(n(log n)²) | O(n²) | O(1) | 不稳定 | In-place | 中等规模数据排序 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 稳定 | Out-place | 大规模数据排序，需要稳定性 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 不稳定 | In-place | 大规模数据排序 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 不稳定 | In-place | 大规模数据排序，需要稳定空间 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(n + k) | 稳定 | Out-place | 数据范围小且密集的整数排序 |
| 桶排序 | O(n + k) | O(n + k) | O(n²) | O(n + k) | 稳定 | Out-place | 数据均匀分布的排序 |
| 基数排序 | O(nk) | O(nk) | O(nk) | O(n + k) | 稳定 | Out-place | 整数或字符串排序 |
表格说明
- n 表示数据规模，k 表示数据范围
- In-place 表示原地排序，不需要额外空间
- Out-place 表示需要额外空间
- 稳定性 表示排序后相等元素的相对顺序是否保持不变
详细比较
以下是各种排序算法的详细比较和分析。
1 冒泡排序 (Bubble Sort)
算法描述
冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
算法步骤
- 比较相邻的元素。如果第一个比第二个大，就把它们交换。
- 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤，除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
优点
- 实现简单
- 空间复杂度低
- 稳定排序
缺点
- 时间复杂度高
- 效率低下
2 选择排序 (Selection Sort)
算法描述
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
算法步骤
- 在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 重复第二步，直到所有元素均排序完毕。
优点
- 实现简单
- 空间复杂度低
- 比较次数固定，适用于交换成本较高的场景
缺点
- 时间复杂度高
- 不稳定排序
3 插入排序 (Insertion Sort)
算法描述
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
算法步骤
- 从第一个元素开始，该元素可以认为已经被排序
- 取出下一个元素，在已经排序的元素序列中从后向前扫描
- 如果该元素（已排序）大于新元素，将该元素移到下一位置
- 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
- 将新元素插入到该位置后
- 重复步骤2~5
优点
- 实现简单
- 空间复杂度低
- 稳定排序
- 对于小规模数据或基本有序的数据效率较高
缺点
- 时间复杂度高
- 大规模数据效率低
4 快速排序 (Quick Sort)
算法描述
快速排序使用分治法（Divide and conquer）策略来把一个串行（list）分为两个子串行（sub-lists）。
算法步骤
- 从数列中挑出一个元素，称为"基准"（pivot）
- 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
- 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
优点
- 平均时间复杂度低
- 空间复杂度低
- 缓存友好
- 适合大规模数据排序
缺点
- 最坏情况下时间复杂度高
- 不稳定排序
- 实现不当可能导致栈溢出
5 归并排序 (Merge Sort)
算法描述
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
- 重复步骤3直到某一指针到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
优点
- 时间复杂度稳定
- 稳定排序
- 适合大规模数据排序
- 可并行化
缺点
- 空间复杂度高
- 需要额外内存
6 堆排序 (Heap Sort)
算法描述
堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。
算法步骤
- 将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区
- 将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn)，且满足R[1,2...n-1]≤R[n]
- 由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成
优点
- 时间复杂度稳定
- 空间复杂度低
- 适合大规模数据排序
- 最坏情况下性能好
缺点
- 不稳定排序
- 常数因子较大
- 缓存不友好
7 计数排序 (Counting Sort)
算法描述
计数排序是一种非比较型整数排序算法，其原理是将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法步骤
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C[i]项，每放一个元素就将C[i]减去1
优点
- 时间复杂度低
- 稳定排序
- 适合数据范围小且密集的整数排序
缺点
- 空间复杂度高
- 只适用于整数排序
- 数据范围大时效率低
8 桶排序 (Bucket Sort)
算法描述
桶排序是将数组分到有限数量的桶子里。每个桶子再个别排序（有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排序）。桶排序是鸽巢排序的一种归纳结果。
算法步骤
- 设置一个定量的数组当作空桶
- 遍历输入数据，并且把数据一个一个放到对应的桶里去
- 对每个不是空的桶进行排序
- 从不是空的桶里把排好序的数据拼接起来
优点
- 时间复杂度低
- 稳定排序
- 适合数据均匀分布的排序
缺点
- 空间复杂度高
- 数据分布不均匀时效率低
- 需要额外内存
9 基数排序 (Radix Sort)
算法描述
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
算法步骤
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零
- 从最低位开始，依次进行一次排序
- 这样从最低位排序一直到最高位排序完成以后，数列就变成一个有序序列
优点
- 时间复杂度低
- 稳定排序
- 适合整数或字符串排序
缺点
- 空间复杂度高
- 只适用于可分割位数的类型
- 需要额外内存
代码实现
以下是各种排序算法的C++实现代码。
冒泡排序
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
for (int j = 0; j < n-i-1; j++) {
if (arr[j] > arr[j+1]) {
// 交换arr[j]和arr[j+1]
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}
选择排序
void selectionSort(int arr[], int n) {
int min_idx;
for (int i = 0; i < n-1; i++) {
// 找到未排序部分的最小元素
min_idx = i;
for (int j = i+1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;
// 交换找到的最小元素和第一个元素
if (min_idx != i) {
int temp = arr[min_idx];
arr[min_idx] = arr[i];
arr[i] = temp;
}
}
}
插入排序
void insertionSort(int arr[], int n) {
int key, j;
for (int i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
// 将arr[0..i-1]中大于key的元素后移
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j - 1;
}
arr[j+1] = key;
}
}
快速排序
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high-1; j++) {
if (arr[j] <= pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return (i + 1);
}
void quickSort(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);
}
}
归并排序
void merge(int arr[], int l, int m, int r) {
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (int i = 0; i < n1; i++)
L[i] = arr[l + i];
for (int j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];
int i = 0, j = 0, k = l;
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(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
}
}
堆排序
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
void heapSort(int arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i = n - 1; i > 0; i--) {
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
}
}
计数排序
void countingSort(int arr[], int n) {
int max_val = arr[0];
for (int i = 1; i < n; i++)
if (arr[i] > max_val)
max_val = arr[i];
int count[max_val + 1] = {0};
for (int i = 0; i < n; i++)
count[arr[i]]++;
for (int i = 1; i <= max_val; i++)
count[i] += count[i - 1];
int output[n];
for (int i = n - 1; i >= 0; i--) {
output[count[arr[i]] - 1] = arr[i];
count[arr[i]]--;
}
for (int i = 0; i < n; i++)
arr[i] = output[i];
}
排序算法选择建议
根据不同的应用场景，选择合适的排序算法至关重要。以下是一些选择建议。
选择排序算法的考虑因素
- 数据规模：小规模数据可以使用简单算法，大规模数据需要高效算法
- 数据特性：数据是否接近有序、数据范围等
- 稳定性要求：是否需要保持相等元素的相对顺序
- 空间限制：是否有内存限制，是否允许额外空间
- 时间复杂度：平均情况和最坏情况下的性能
- 实现复杂度：算法实现的难易程度
推荐使用场景
小规模数据
插入排序、选择排序、冒泡排序
大规模数据
快速排序、归并排序、堆排序
稳定性要求
归并排序、插入排序、冒泡排序、计数排序、桶排序、基数排序
空间限制
快速排序、堆排序、插入排序、选择排序、冒泡排序