C语言排序算法知识点汇总
排序算法是编程中最基础也是最重要的知识之一。简单来说，排序就是把一堆数据按照特定顺序（比如从小到大）重新排列的过程。
在实际编程中，我们会遇到各种排序场景：对考试成绩排序、对商品价格排序、对用户注册时间排序等等。选择合适的排序算法可以大大提高程序效率。
本文将详细介绍C语言中常用的7种排序算法，通俗易懂地解释它们的原理、特点和使用场景，并提供相应的C代码实现。
常见排序算法详解
● 冒泡排序 (Bubble Sort)
基本原理
像冒泡一样，大的元素慢慢”浮”到数组顶端
时间复杂度
最好：O(n) 平均：O(n²) 最坏：O(n²)
空间复杂度
O(1)
稳定性
稳定
大白话解释
想象水中的气泡，大的气泡会慢慢浮到水面。冒泡排序就是反复比较相邻的两个数字，如果顺序不对就交换它们。这样每轮比较后，最大的数字就会”冒泡”到最后面。
适用场景
适用于小规模数据排序或基本有序的数据。优点是简单易懂，缺点是效率较低。
C语言实现
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)
稳定性
不稳定
大白话解释
就像排队时每次找出最矮的人排到最前面。选择排序每次从未排序部分找到最小值，然后交换到未排序部分的起始位置。
适用场景
适用于小数据量且交换次数少的情况（比冒泡排序交换次数少）。
C语言实现
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;
}
}
● 插入排序 (Insertion Sort)
基本原理
像整理扑克牌，把新元素插入到已排序部分的正确位置
时间复杂度
最好：O(n) 平均：O(n²) 最坏：O(n²)
空间复杂度
O(1)
稳定性
稳定
大白话解释
就像打扑克牌时整理牌的过程。每次取一张新牌，把它插入到手中已排序牌的正确位置上。
适用场景
对小规模或基本有序的数据效率很高。在实际应用中，对小数组排序时比快速排序更快。
C语言实现
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i – 1;
// 将比key大的元素后移
while (j >= 0 && arr[j] > key) {
arr[j+1] = arr[j];
j = j – 1;
}
arr[j+1] = key;
}
}
● 快速排序 (Quick Sort)
基本原理
“分治”思想：选一个基准值，小的放左边，大的放右边
时间复杂度
最好：O(n log n) 平均：O(n log n) 最坏：O(n²)
空间复杂度
O(log n)
稳定性
不稳定
大白话解释
快速排序就像班级里选班长：先选一个基准同学（比如学号），比这个学号小的站左边，比这个学号大的站右边。然后对左右两边分别重复这个过程。
适用场景
适用于大规模数据排序，是实践中速度最快的通用排序算法。C语言标准库中的qsort函数就是快速排序。
C语言实现
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++;
// 交换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²) | O(1) | 稳定 | 小数据量、教学使用 |
| 选择排序 | O(n²) | O(1) | 不稳定 | 小数据量且交换代价高 |
| 插入排序 | O(n²) | O(1) | 稳定 | 小数据量或基本有序 |
| 希尔排序 | O(n log n) | O(1) | 不稳定 | 中等规模数据 |
| 归并排序 | O(n log n) | O(n) | 稳定 | 大数据量、稳定排序 |
| 快速排序 | O(n log n) | O(log n) | 不稳定 | 大数据量、通用排序 |
| 堆排序 | O(n log n) | O(1) | 不稳定 | 大数据量、内存受限 |
📌 重要提示：
1. 小规模数据（如n≤50）：插入排序通常是最佳选择
2. 中等规模数据：希尔排序表现良好
3. 大规模数据：快速排序是最佳选择（平均性能最好）
4. 需要稳定排序：归并排序是最佳选择
5. 在实际应用中，C语言的qsort()和C++的sort()都是基于快速排序实现的