核心基础知识点
这些是理解任何排序算法的基石。
（图片来源网络，侵删）
数组
- 定义: 一组相同类型的数据元素的集合,在内存中连续存放。
- 索引: 每个元素都有一个从0开始的整数索引，用于访问。
arr[0]访问第一个元素。 - 特点: 随机访问速度快（O(1)），但在中间插入或删除元素慢（O(n)），因为需要移动大量元素,排序主要在数组上进行。
指针
- 定义: 存储内存地址的变量。
- 与数组的关系: 在C语言中，数组名会“退化”为其首元素的指针，可以使用指针来遍历和操作数组元素,有时比数组索引更高效。
- 示例:
int arr[] = {10, 20, 30}; int *p = arr; // p指向arr[0] printf("%d", *p); // 输出10 p++; // p现在指向arr[1] printf("%d", *p); // 输出20
循环
for循环: 最常用于排序算法，因为它明确知道需要执行的迭代次数（外层循环控制轮数，内层循环控制比较次数）。while循环: 适用于某些需要特定条件才能退出的排序逻辑。
比较与交换
- 比较: 使用关系运算符（
>,<,>=,<=, , ）来决定两个元素的相对顺序。 - 交换: 交换两个变量的值，最经典的方法是使用一个临时变量。
// 交换 a 和 b 的值 int temp = a; a = b; b = temp;
在C++中，可以使用
std::swap,但在纯C中需要自己实现。
排序算法本身
这是排序操作的核心,不同的算法有不同的时间复杂度和空间复杂度。
简单排序算法 (通常用于教学或小规模数据)
| 算法名称 | 平均时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 特点 |
|---|---|---|---|---|
| 冒泡排序 | 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) | 实践中最快的通用排序算法之一，采用分治策略，通过一个“基准”（pivot）将数组分为两部分，然后递归排序。 |
| 归并排序 | 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(k) | 适用于整数且范围不大，通过统计每个整数出现的次数，然后回写到数组中。 |
| 基数排序 | O(d*(n + k)) | O(d*(n + k)) | O(n + k) | 适用于整数或字符串，按“位”或“字符”进行排序，通常使用计数排序作为子过程。 |
函数与模块化
为了代码的清晰和复用,排序逻辑通常封装在函数中。
- 函数定义:
void bubble_sort(int arr[], int n)，arr[]是待排序的数组，n是数组长度。 - 函数原型: 在头文件中声明,以便其他文件可以调用。
- 参数传递: 数组作为参数传递时，传递的是其首地址（指针）,所以函数内部对数组的修改会直接影响原数组。
比较函数
当排序自定义结构体或需要降序排列时,需要自定义比较逻辑。
（图片来源网络，侵删）
-
qsort函数: C标准库<stdlib.h>提供的快速排序函数,非常通用。void qsort(void *base, size_t nmemb, size_t size, int (*compar)(const void *, const void *));
base: 数组首地址。nmemb: 数组元素个数。size: 每个元素的大小（字节）。- `compar关键**！这是一个指向比较函数的指针,你需要自己实现这个比较函数。
-
比较函数的实现:
-
对于基本数据类型（如
int）：int compare_int(const void *a, const void *b) { int arg1 = *(const int*)a; int arg2 = *(const int*)b; return (arg1 > arg2) - (arg1 < arg2); // 返回差值，标准写法 // 或者更直观的： // if (arg1 > arg2) return 1; // if (arg1 < arg2) return -1; // return 0; } -
对于结构体：
（图片来源网络，侵删）struct Student { char name[50]; int score; }; // 按分数降序排列 int compare_student_by_score(const void *a, const void *b) { const struct Student *s1 = (const struct Student *)a; const struct Student *s2 = (const struct Student *)b; // 降序：如果s1的分数小于s2，返回正数 return s2->score - s1->score; }
-
内存管理
- 栈 vs. 堆:
- 栈: 用于局部变量（如函数内的数组），大小有限，自动分配和释放，排序小数组时,栈上的数组足够用。
- 堆: 用于动态内存分配（
malloc,calloc,free），当排序的数据量非常大，超过栈的大小时,必须在堆上分配内存。
- 动态内存分配:
int *large_array = (int*)malloc(n * sizeof(int)); if (large_array == NULL) { // 处理内存分配失败 } // ... 使用 large_array ... free(large_array); // 记得释放！
算法复杂度分析
这是评价排序算法好坏的关键。
- 时间复杂度:
- O(1): 常数时间。
- O(log n): 对数时间,如二分查找。
- O(n): 线性时间。
- O(n log n): 线性对数时间,高效排序算法的标志。
- O(n²): 平方时间,简单排序算法的标志。
- 空间复杂度: 算法运行所需额外空间的量度。
- 稳定性: 如果两个元素值相等，排序后它们的相对位置不变，则该排序算法是稳定的，归并排序和插入排序是稳定的,而快速排序和堆排序通常是不稳定的。
总结与学习路径
- 打好基础: 确保你完全理解 数组、指针、循环 这三大块。
- 从简单开始: 动手实现 冒泡排序、选择排序、插入排序,这能帮助你理解排序的基本思想。
- 掌握核心: 学习并实现 快速排序 和 归并排序,这是面试和实际开发中最重要的两个算法。
- 学会使用工具: 熟悉C标准库的
qsort函数，并学会如何为它编写 比较函数。 - 理解分析: 学习 时间复杂度和空间复杂度 的概念,并能分析你实现的算法。
- 进阶探索: 了解 堆排序 和 非比较排序（如计数排序）,以应对更特殊的需求。
通过以上知识点的学习和实践,你就能全面掌握C语言中的排序技术。
