一、排序算法分类
1. 按时间复杂度分类
O(n²)算法：冒泡排序、选择排序、插入排序
O(n log n)算法：快速排序、归并排序、堆排序
O(n)算法：计数排序、桶排序、基数排序（线性排序，有特定条件）
2. 按稳定性分类
稳定排序：冒泡、插入、归并、计数、桶、基数
不稳定排序：选择、快速、堆
3. 按空间复杂度分类
原地排序：冒泡、选择、插入、快速、堆
非原地排序：归并、计数、桶、基数
二、基础排序算法实现与解析
1. 冒泡排序（Bubble Sort）
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]) {
// 交换相邻元素
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}特点：
时间复杂度：最好O(n)（已排序），最差O(n²)
空间复杂度：O(1)
稳定排序
适合小规模数据或基本有序数据
2. 选择排序（Selection Sort）
void selectionSort(int arr[], int n) {
for (int i = 0; i < n-1; i++) {
int min_idx = i;
// 找到未排序部分的最小元素
for (int j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
}
}
// 将最小元素交换到已排序部分的末尾
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}特点：
时间复杂度：始终O(n²)
空间复杂度：O(1)
不稳定排序
交换次数少（最多n-1次）
3. 插入排序（Insertion Sort）
void insertionSort(int arr[], int n) {
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;
}
}特点：
时间复杂度：最好O(n)（已排序），最差O(n²)
空间复杂度：O(1)
稳定排序
适合小规模或基本有序数据
三、高效排序算法实现与解析
1. 快速排序（Quick Sort）
// 分区函数
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // i是小于基准的元素的边界
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
// 交换arr[i]和arr[j]
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);
}
}特点：
时间复杂度：平均O(n log n)，最差O(n²)（当数组已排序或逆序）
空间复杂度：O(log n)（递归调用栈）
不稳定排序
实际应用中通常是最快的排序算法
2. 归并排序（Merge Sort）
// 合并两个有序数组
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);
}
}特点：
时间复杂度：始终O(n log n)
空间复杂度：O(n)（需要额外空间）
稳定排序
适合链表排序和大规模数据
3. 堆排序（Heap Sort）
// 调整堆
void heapify(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) {
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
heapify(arr, i, 0);
}
}特点：
时间复杂度：始终O(n log n)
空间复杂度：O(1)
不稳定排序
适合优先级队列实现
四、线性时间排序算法
1. 计数排序（Counting Sort）
void countingSort(int arr[], int n) {
// 找出数组中的最大值
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 创建计数数组并初始化
int count[max+1];
for (int i = 0; i <= max; i++) {
count[i] = 0;
}
// 统计每个元素出现次数
for (int i = 0; i < n; i++) {
count[arr[i]]++;
}
// 修改计数数组为累计计数
for (int i = 1; i <= max; 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];
}
}特点：
时间复杂度：O(n+k)（k是数据范围）
空间复杂度：O(n+k)
稳定排序
仅适用于整数且范围不大的情况
2. 基数排序（Radix Sort）
// 获取数字的某一位
int getDigit(int num, int digit) {
int divisor = 1;
for (int i = 0; i < digit; i++) {
divisor *= 10;
}
return (num / divisor) % 10;
}
void radixSort(int arr[], int n) {
// 找出最大值确定位数
int max = arr[0];
for (int i = 1; i < n; i++) {
if (arr[i] > max) {
max = arr[i];
}
}
// 计算最大位数
int digits = 0;
while (max > 0) {
digits++;
max /= 10;
}
// 对每一位进行计数排序
for (int d = 0; d < digits; d++) {
int count[10] = {0};
int output[n];
// 统计当前位的数字出现次数
for (int i = 0; i < n; i++) {
count[getDigit(arr[i], d)]++;
}
// 计算累计计数
for (int i = 1; i < 10; i++) {
count[i] += count[i-1];
}
// 构建输出数组（从后向前保持稳定性）
for (int i = n-1; i >= 0; i--) {
int digit = getDigit(arr[i], d);
output[count[digit]-1] = arr[i];
count[digit]--;
}
// 拷贝回原数组
for (int i = 0; i < n; i++) {
arr[i] = output[i];
}
}
}特点：
时间复杂度：O(d*(n+k))（d是位数，k是基数）
空间复杂度：O(n+k)
稳定排序
适用于整数或字符串排序
五、排序算法比较与选择指南
| 算法 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|---|
| 冒泡 | O(n²) | O(n²) | O(1) | 稳定 | 小规模/基本有序 |
| 选择 | O(n²) | O(n²) | O(1) | 不稳定 | 交换成本高时 |
| 插入 | O(n²) | O(n²) | O(1) | 稳定 | 小规模/基本有序 |
| 快速 | O(n log n) | O(n²) | O(log n) | 不稳定 | 通用排序首选 |
| 归并 | O(n log n) | O(n log n) | O(n) | 稳定 | 链表排序/外部排序 |
| 堆 | O(n log n) | O(n log n) | O(1) | 不稳定 | 优先级队列实现 |
| 计数 | O(n+k) | O(n+k) | O(n+k) | 稳定 | 小范围整数 |
| 基数 | O(d*(n+k)) | O(d*(n+k)) | O(n+k) | 稳定 | 多关键字排序 |
小规模数据（n < 100）：插入排序通常表现最好
中等规模数据（100 < n < 10,000）：快速排序是首选
大规模数据（n > 10,000）：考虑归并排序或堆排序
特定条件（小范围整数）：计数排序或基数排序可能更优