排序
排序（Sorting）是将一组数据按照特定顺序重新排列的过程，是数据处理中最基础、也是研究最深入的算法问题之一。
排序算法全家福
排序算法全家福 — 时间复杂度与特征对比
基础排序（O(n²)）
冒泡排序、选择排序和插入排序实现简单，适合小规模数据或教学理解。
高级排序（O(n log n)）
快速排序、归并排序和堆排序在工程中应用最广。希尔排序则是对插入排序的改进。
实例
#include <stdio.h>
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* 冒泡排序 — O(n²)，稳定
每轮将最大元素"冒泡"到末尾 */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* 优化：提前终止 */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break; /* 已有序，提前结束 */
}
}
/* 快速排序分区函数 — O(n log n) 平均，不稳定
选基准 pivot，小于 pivot 放左边，大于放右边 */
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* 选最后一个元素为基准 */
int i = low - 1; /* i 指向小于 pivot 的区域的末尾 */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* 基准放到正确位置 */
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 printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = 7;
bubbleSort(arr1, n1);
printf("冒泡排序: "); printArray(arr1, n1);
/* 输出: 11 12 22 25 34 64 90 */
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr2, 0, 6);
printf("快速排序: "); printArray(arr2, 7);
/* 输出: 11 12 22 25 34 64 90 */
return 0;
}
void swap(int* a, int* b) { int t = *a; *a = *b; *b = t; }
/* 冒泡排序 — O(n²)，稳定
每轮将最大元素"冒泡"到末尾 */
void bubbleSort(int arr[], int n) {
for (int i = 0; i < n - 1; i++) {
int swapped = 0; /* 优化：提前终止 */
for (int j = 0; j < n - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
swap(&arr[j], &arr[j + 1]);
swapped = 1;
}
}
if (!swapped) break; /* 已有序，提前结束 */
}
}
/* 快速排序分区函数 — O(n log n) 平均，不稳定
选基准 pivot，小于 pivot 放左边，大于放右边 */
int partition(int arr[], int low, int high) {
int pivot = arr[high]; /* 选最后一个元素为基准 */
int i = low - 1; /* i 指向小于 pivot 的区域的末尾 */
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]); /* 基准放到正确位置 */
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 printArray(int arr[], int n) {
for (int i = 0; i < n; i++) printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr1[] = {64, 34, 25, 12, 22, 11, 90};
int n1 = 7;
bubbleSort(arr1, n1);
printf("冒泡排序: "); printArray(arr1, n1);
/* 输出: 11 12 22 25 34 64 90 */
int arr2[] = {64, 34, 25, 12, 22, 11, 90};
quickSort(arr2, 0, 6);
printf("快速排序: "); printArray(arr2, 7);
/* 输出: 11 12 22 25 34 64 90 */
return 0;
}
分治思想示意
三大 O(n log n) 排序算法 — 分治策略对比
快速排序 (分区)
选基准 pivot
小于基准→左侧，大于→右侧
递归排序左右子数组
不稳定 | 原地 | 最常用
归并排序 (合并)
递归二分至最小单元
合并两个有序子序列
需要额外数组 O(n)
稳定 | 需额外空间 | 外排序
堆排序 (堆化)
建最大堆 O(n)
堆顶(最大)放末尾
重新调整堆 O(log n)
不稳定 | 原地 O(1) | 空间最优
排序算法完整对比
| 算法 | 最好 | 平均 | 最坏 | 空间 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | 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 log n) | O(n^1.3) | O(n²) | O(1) | 不稳定 |
实际选型建议：通用场景首选快速排序；需要稳定性选归并排序；内存极度受限选堆排序；小规模或基本有序数据选插入排序。