C 练习实例37 – 排序：从冒泡到快速，掌握数组排序的核心逻辑
在学习 C 语言的过程中，排序是一个绕不开的经典练习。它不仅是算法入门的“敲门砖”，更是理解循环、条件判断、数组操作与函数封装的综合实践。今天我们就来深入探讨 C 练习实例37 – 排序，通过几个经典排序算法的实现，带你一步步掌握排序的本质。
排序，就像是把杂乱无章的书本按书名顺序排列；在程序中，它就是将一组无序的数据，按照从小到大或从大到小的规则重新组织。无论是学生成绩、商品价格，还是用户注册时间，排序都无处不在。
接下来，我们将从最基础的冒泡排序开始，逐步深入到更高效的快速排序，每一步都配有完整的代码与逐行注释，确保你不仅能“看懂”，还能“写对”。
冒泡排序：最直观的“浮水”思想
冒泡排序的原理非常简单：每次比较相邻的两个元素，如果前一个比后一个大（升序排列），就交换它们的位置。这样，大的元素就像气泡一样，逐渐“浮”到数组的末尾。
这个过程重复进行，直到整个数组有序。
创建数组与初始化
我们先创建一个整型数组，并初始化一些无序数据，作为排序的输入。
#include <stdio.h>
int main() {
// 定义一个包含 8 个整数的数组
int arr[] = {64, 34, 25, 12, 22, 11, 90, 5};
// 计算数组长度
int n = sizeof(arr) / sizeof(arr[0]);
// 输出原始数组
printf("原始数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 冒泡排序的核心逻辑
for (int i = 0; i < n - 1; i++) {
// 每一轮外层循环，最大的元素会“冒泡”到末尾
for (int j = 0; j < n - i - 1; j++) {
// 如果前一个元素大于后一个元素，就交换
if (arr[j] > arr[j + 1]) {
// 临时变量 temp 用于交换两个数
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
// 输出排序后的数组
printf("排序后数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
代码注释说明：
sizeof(arr) / sizeof(arr[0])：计算数组元素个数，避免硬编码。- 外层循环
i控制排序轮数，每轮减少一次比较，因为最大值已归位。 - 内层循环
j从头到未排序部分的末尾，比较相邻元素。 - 交换操作使用临时变量
temp，这是 C 语言中交换两个变量的标准做法。
运行结果如下：
原始数组：64 34 25 12 22 11 90 5
排序后数组：5 11 12 22 25 34 64 90
冒泡排序虽然效率不高（时间复杂度 O(n²)），但它的逻辑清晰，非常适合初学者理解排序的基本思想。
选择排序：每一次都选“最小值”
选择排序的思路更像“挑班长”——从所有同学中选出最优秀的一个，放到第一位；再从剩下的中选出第二优秀，放到第二位……如此反复，直到全部排好。
选择排序的实现
#include <stdio.h>
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 选择排序主循环
for (int i = 0; i < n - 1; i++) {
// 假设当前位置 i 就是最小值的位置
int min_idx = i;
// 在未排序部分中寻找最小值的下标
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j; // 更新最小值的下标
}
}
// 如果最小值不在当前位置，则交换
if (min_idx != i) {
int temp = arr[i];
arr[i] = arr[min_idx];
arr[min_idx] = temp;
}
}
printf("排序后数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
关键点解释：
min_idx用于记录当前未排序部分中最小元素的索引。- 内层循环遍历
i+1到n-1，因为i之前的部分已经排好。 - 仅当
min_idx != i时才交换，避免无谓操作。
选择排序的时间复杂度同样是 O(n²)，但交换次数更少，通常比冒泡排序略快。
插入排序：像整理扑克牌一样排序
插入排序的思路，就像是你在打扑克牌时，每摸一张牌，就把它插到正确的位置。它适合小规模数据，或部分有序的数据。
插入排序的实现
#include <stdio.h>
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 插入排序核心逻辑
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]; // 将大于 key 的元素向右移动
j--;
}
// 插入 key 到正确位置
arr[j + 1] = key;
}
printf("排序后数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
逐行解读：
key = arr[i]：取出当前待插入的元素。j = i - 1：从已排序部分的末尾开始比较。while循环：将大于key的元素向右移动一位，腾出空间。- 最后
arr[j + 1] = key：把key插入到合适位置。
插入排序在数据接近有序时表现优异，时间复杂度可接近 O(n)，是许多高级排序算法的基础。
快速排序：分治思想的典范
快速排序是 C 练习实例37 – 排序中最具代表性的算法之一。它采用“分而治之”的策略：选一个基准值（pivot），将数组分为两部分——小于基准的放左边，大于基准的放右边，然后递归处理左右两部分。
快速排序的实现
#include <stdio.h>
// 快速排序的分区函数
int partition(int arr[], int low, int high) {
int pivot = arr[high]; // 选择最后一个元素作为基准
int i = low - 1; // 较小元素的索引
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 pivot_index = partition(arr, low, high);
// 递归排序基准左边部分
quickSort(arr, low, pivot_index - 1);
// 递归排序基准右边部分
quickSort(arr, pivot_index + 1, high);
}
}
int main() {
int arr[] = {64, 34, 25, 12, 22, 11, 90, 5};
int n = sizeof(arr) / sizeof(arr[0]);
printf("原始数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
// 调用快速排序
quickSort(arr, 0, n - 1);
printf("排序后数组：");
for (int i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
printf("\n");
return 0;
}
核心逻辑解析：
partition函数：将数组按基准值划分为两部分。low和high定义当前处理的子数组边界。- 递归调用
quickSort实现分治。
快速排序平均时间复杂度为 O(n log n)，是实际应用中最常用的排序算法之一。
总结：从 C 练习实例37 – 排序中收获什么？
通过今天的 C 练习实例37 – 排序，我们不仅实现了四种经典排序算法，更重要的是理解了算法设计的基本思想：
- 冒泡排序：直观，适合入门。
- 选择排序：每次选最小，减少交换。
- 插入排序：像整理扑克牌，适合小数据。
- 快速排序：分治思想，效率最高。
这些算法虽小，但背后蕴含着编程思维的精髓：如何用有限的代码，解决复杂的问题。
对于初学者，建议从冒泡排序开始，逐步理解循环与比较逻辑；中级开发者可深入研究快速排序的递归与分治机制，提升算法设计能力。
记住，排序不只是“让数字变有序”，更是锻炼你逻辑思维、代码组织与问题拆解能力的绝佳练习。
最后，当你能独立写出快速排序时，你就已经迈过了 C 语言学习中一个重要的门槛。继续加油，编程之路，越走越远。