排序算法总结
排序算法是计算机科学中用于将数据按特定顺序（通常是升序或降序）排列的经典算法。它们在数据处理、搜索优化和算法设计中广泛应用。以下是一个简明实用的排序算法总结，涵盖常见算法的原理、时间复杂度、空间复杂度、稳定性、适用场景及示例代码（以 C++ 为例，概念适用于多种语言），适合初学者快速理解和参考。
1. 概述
- 排序目标：将一组数据（如数组）按升序或降序排列。
- 评价指标：
- 时间复杂度：算法运行时间。
- 空间复杂度：额外内存使用。
- 稳定性：相同值的元素在排序后是否保持相对顺序。
- 原地排序：是否仅使用常数额外空间。
- 分类：
- 比较排序：基于元素比较（如冒泡、快速排序）。
- 非比较排序：基于其他属性（如计数排序、基数排序）。
2. 常见排序算法
以下是常见的排序算法，按复杂度和使用场景分类。
2.1 基础排序算法
适合小规模数据或教学，复杂度较高。
- 冒泡排序（Bubble Sort）
- 原理：相邻元素两两比较，交换顺序错误的元素，每轮将最大/最小值“冒泡”到一端。
- 时间复杂度：
- 最好：O(n)（已排序）。
- 平均/最坏：O(n²)。
- 空间复杂度：O(1)（原地排序）。
- 稳定性：稳定。
- 适用场景：小数据集、教育用途。
- 代码：
cpp 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; // 优化：已排序则退出 } }
- 选择排序（Selection Sort）
- 原理：每次从未排序部分选出最小/最大值，放到已排序部分。
- 时间复杂度：
- 最好/平均/最坏：O(n²)。
- 空间复杂度：O(1)（原地排序）。
- 稳定性：不稳定。
- 适用场景：小数据集，交换次数需最小化。
- 代码：
cpp 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]); } }
- 插入排序（Insertion Sort）
- 原理：将元素逐个插入到已排序部分，类似整理扑克牌。
- 时间复杂度：
- 最好：O(n)（近乎排序）。
- 平均/最坏：O(n²)。
- 空间复杂度：O(1)（原地排序）。
- 稳定性：稳定。
- 适用场景：小数据集、近乎排序的数据。
- 代码：
cpp void insertionSort(vector<int>& arr) { int n = arr.size(); for (int i = 1; i < n; i++) { int key = arr[i]; int j = i - 1; while (j >= 0 && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }
2.2 高效排序算法
适合中大型数据集，性能更优。
- 快速排序（Quick Sort）
- 原理：选择 pivot（基准），将数组分为小于和大于 pivot 的两部分，递归排序。
- 时间复杂度：
- 最好/平均：O(n log n)。
- 最坏：O(n²)（极少发生，如已排序数组且选第一个元素为 pivot）。
- 空间复杂度：O(log n)（递归栈）。
- 稳定性：不稳定。
- 适用场景：通用排序，性能优异。
- 代码：
cpp void quickSort(vector<int>& arr, int low, int high) { if (low < 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]); int pi = i + 1; quickSort(arr, low, pi - 1); quickSort(arr, pi + 1, high); } }
- 归并排序（Merge Sort）
- 原理：分治法，将数组递归分成两半，排序后合并。
- 时间复杂度：
- 最好/平均/最坏：O(n log n)。
- 空间复杂度：O(n)（合并时的辅助数组）。
- 稳定性：稳定。
- 适用场景：需要稳定排序、链表排序。
- 代码：
cpp void merge(vector<int>& arr, int l, int m, int r) { vector<int> temp(r - l + 1); int i = l, j = m + 1, k = 0; while (i <= m && j <= r) { if (arr[i] <= arr[j]) temp[k++] = arr[i++]; else temp[k++] = arr[j++]; } while (i <= m) temp[k++] = arr[i++]; while (j <= r) temp[k++] = arr[j++]; for (i = l, k = 0; i <= r; i++, k++) arr[i] = temp[k]; } void mergeSort(vector<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); } }
- 堆排序（Heap Sort）
- 原理：构建最大/最小堆，逐个提取根节点到排序位置。
- 时间复杂度：
- 最好/平均/最坏：O(n log n)。
- 空间复杂度：O(1)（原地排序）。
- 稳定性：不稳定。
- 适用场景：需要固定空间、数据量较大。
- 代码：
cpp void heapify(vector<int>& arr, int n, int i) { int largest = i; int left = 2 * i + 1, 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(); for (int i = n / 2 - 1; i >= 0; i--) heapify(arr, n, i); for (int i = n - 1; i > 0; i--) { swap(arr[0], arr[i]); heapify(arr, i, 0); } }
2.3 非比较排序
适合特定数据类型，效率高但限制多。
- 计数排序（Counting Sort）
- 原理：统计每个值的出现次数，直接构造排序结果。
- 时间复杂度：O(n + k)（k 为值范围）。
- 空间复杂度：O(k)。
- 稳定性：稳定。
- 适用场景：整数数据，范围较小。
- 代码：
cpp void countingSort(vector<int>& arr) { int maxVal = *max_element(arr.begin(), arr.end()); vector<int> count(maxVal + 1, 0), output(arr.size()); for (int x : arr) count[x]++; for (int i = 1; i <= maxVal; i++) count[i] += count[i - 1]; for (int i = arr.size() - 1; i >= 0; i--) { output[count[arr[i]] - 1] = arr[i]; count[arr[i]]--; } arr = output; }
- 基数排序（Radix Sort）
- 原理：按位（个位、十位等）排序，基于计数排序。
- 时间复杂度：O(d(n + k))（d 为最大位数，k 为基数）。
- 空间复杂度：O(n + k)。
- 稳定性：稳定。
- 适用场景：非负整数、大数据集。
- 代码（略，基于计数排序实现，按位处理）。
3. 算法比较
| 算法 | 最好时间 | 平均时间 | 最坏时间 | 空间复杂度 | 稳定性 | 原地排序 |
|---|---|---|---|---|---|---|
| 冒泡排序 | O(n) | O(n²) | O(n²) | O(1) | 是 | 是 |
| 选择排序 | O(n²) | O(n²) | O(n²) | O(1) | 否 | 是 |
| 插入排序 | O(n) | O(n²) | O(n²) | O(1) | 是 | 是 |
| 快速排序 | O(n log n) | O(n log n) | O(n²) | O(log n) | 否 | 是 |
| 归并排序 | O(n log n) | O(n log n) | O(n log n) | O(n) | 是 | 否 |
| 堆排序 | O(n log n) | O(n log n) | O(n log n) | O(1) | 否 | 是 |
| 计数排序 | O(n + k) | O(n + k) | O(n + k) | O(k) | 是 | 否 |
| 基数排序 | O(d(n + k)) | O(d(n + k)) | O(d(n + k)) | O(n + k) | 是 | 否 |
4. 适用场景
- 小数据集（n < 100）：冒泡排序、插入排序（简单，代码量少）。
- 近乎排序：插入排序（接近 O(n)）。
- 通用场景：快速排序（平均性能优秀）。
- 稳定排序：归并排序、计数排序、基数排序。
- 固定空间：堆排序、选择排序（O(1) 空间）。
- 特定数据：计数排序、基数排序（整数、范围有限）。
- 大数据：归并排序（稳定，适合外部排序）、基数排序。
5. 使用示例
#include <vector>
#include <iostream>
using namespace std;
// 以快速排序为例
void quickSort(vector<int>& arr, int low, int high) {
if (low < 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]);
int pi = i + 1;
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
int main() {
vector<int> arr = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr, 0, arr.size() - 1);
for (int x : arr) cout << x << " ";
cout << endl; // 输出: 11 12 22 25 34 64 90
return 0;
}6. 注意事项
- 稳定性：需要保持相同元素顺序时，选择归并排序或计数排序。
- 空间限制：内存受限时，选择堆排序或快速排序。
- 数据特性：
- 整数范围小：计数排序或基数排序。
- 近乎排序：插入排序。
- 性能优化：
- 快速排序：选择随机 pivot 或三数取中减少最坏情况。
- 插入排序：用于小数组优化快速排序（混合算法）。
- 语言内置排序：
- C++：
std::sort（混合快速排序和插入排序，O(n log n)）。 - Java：
Arrays.sort（双轴快速排序）。 - Python：
sorted()或list.sort()（Timsort）。 - 并发排序：大数据场景可考虑并行归并排序。
7. 总结
- 基础排序：冒泡、选择、插入排序，适合小数据或教学。
- 高效排序：快速、归并、堆排序，适合中大型数据。
- 非比较排序：计数、基数排序，适合特定数据类型。
- 选择依据：
- 数据规模：小数据用简单算法，大数据用快速/归并排序。
- 稳定性：归并、计数、基数排序。
- 空间：堆排序、快速排序（原地）。
- 推荐实践：
- 优先使用语言内置排序（如
std::sort）。 - 特殊场景选择特定算法（如计数排序）。
- 测试最坏情况，确保性能稳定。
如果你需要更详细的某算法实现（其他语言如 Java、Python）、性能分析或特定场景的代码示例，请告诉我！