排序（Sorting）是计算机科学中的基本操作之一，用于按照一定的规则对数据进行排序。C 语言提供了多种排序算法，每种算法在时间复杂度、空间复杂度和稳定性方面各有优劣。
📌 目录
1. 排序算法分类
排序算法可以按照是否稳定和时间复杂度进行分类：
| 分类 | 常见算法 | 时间复杂度（最坏情况） | 空间复杂度 | 稳定性 |
|---|---|---|---|---|
| 基础排序 | 冒泡排序、选择排序、插入排序 | O(n²) | O(1) | 冒泡、插入排序稳定，选择排序不稳定 |
| 高级排序 | 快速排序、归并排序、堆排序 | O(n log n) | O(log n)（快排、堆排）/ O(n)（归并） | 归并排序稳定，快速排序和堆排序不稳定 |
| 非比较排序 | 计数排序、基数排序 | O(n) | O(n) | 稳定 |
稳定性定义： 如果两个相等的元素在排序后相对位置保持不变，则该排序算法是稳定的，否则为不稳定。
2. 常见排序算法对比
| 算法 | 时间复杂度（最坏） | 空间复杂度 | 稳定性 | 适用场景 |
|---|---|---|---|---|
| 冒泡排序 | O(n²) | O(1) | ✅ 稳定 | 适合小规模数据 |
| 选择排序 | O(n²) | O(1) | ❌ 不稳定 | 适合小规模数据 |
| 插入排序 | O(n²) | O(1) | ✅ 稳定 | 适用于小规模或部分有序数据 |
| 快速排序 | O(n²) | O(log n) | ❌ 不稳定 | 适用于大规模数据，性能优秀 |
| 归并排序 | O(n log n) | O(n) | ✅ 稳定 | 适用于大规模数据，适合链表 |
| 堆排序 | O(n log n) | O(1) | ❌ 不稳定 | 适用于优先级队列等场景 |
| 计数排序 | O(n) | O(n) | ✅ 稳定 | 适用于整数排序，范围不能过大 |
| 基数排序 | O(nk) | O(n + k) | ✅ 稳定 | 适用于长整数或字符串排序 |
3. 基础排序算法
冒泡排序（Bubble Sort）
- 逐步交换相邻的元素，较大值向右移动。
- 时间复杂度： O(n²)
- 空间复杂度： O(1)
- 稳定性： ✅ 稳定
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;
}
}
}
}
选择排序（Selection Sort）
- 每次选取最小（或最大）值放到正确位置。
- 时间复杂度： O(n²)
- 空间复杂度： O(1)
- 稳定性： ❌ 不稳定
void selectionSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int minIndex = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
插入排序（Insertion Sort）
- 逐个将元素插入到有序数组中。
- 时间复杂度： O(n²)
- 空间复杂度： O(1)
- 稳定性： ✅ 稳定
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;
}
}
4. 高级排序算法
快速排序（Quick Sort）
- 选定基准值（Pivot），递归排序左右子数组。
- 时间复杂度： O(n log n)（最坏 O(n²)）
- 空间复杂度： O(log n)
- 稳定性： ❌ 不稳定
void quickSort(int arr[], int left, int right) {
if (left >= right) return;
int pivot = arr[left];
int i = left, j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) j--;
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) i++;
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
6. qsort() 函数（标准库排序）
C 标准库提供了 qsort()，可用于排序任意类型数组。
#include <stdio.h>
#include <stdlib.h>
int compare(const void *a, const void *b) {
return (*(int *)a - *(int *)b);
}
int main() {
int arr[] = {5, 2, 9, 1, 6};
int n = sizeof(arr) / sizeof(arr[0]);
qsort(arr, n, sizeof(int), compare);
for (int i = 0; i < n; i++)
printf("%d ", arr[i]);
return 0;
}
7. 参考资料
通过这些排序算法，你可以在不同的场景下选择最合适的方法，提升 C 语言编程效率！🚀
发表回复