C语言实战：从冒泡排序到数组去重的解题艺术
在编程学习的道路上，排序和去重是两个绕不开的基础课题。它们不仅是算法入门的敲门砖，更是解决实际问题的常见工具。今天，我们就以ZZULIOJ平台上的1122题为例，手把手带你用C语言实现这两个功能，同时深入理解背后的编程思维。
1. 问题分析与解题框架
面对任何编程题目，第一步永远是理解题意。这道题要求我们对一组可能包含重复元素的整数进行去重和排序处理。看似简单的需求，实际上包含了多个编程知识点：
- 输入处理：如何正确读取用户输入的数据
- 排序算法：如何对数据进行有序排列
- 去重逻辑：如何识别并去除重复元素
- 输出格式：如何按照要求格式化输出结果
让我们先构建一个清晰的解题框架：
- 读取输入的整数个数N
- 读取N个整数并存储在数组中
- 对数组进行排序（这里选择冒泡排序作为教学示例）
- 去除数组中重复的元素
- 输出处理后的结果
2. 冒泡排序的深入解析
冒泡排序是初学者最容易理解的排序算法之一。它的核心思想是通过相邻元素的比较和交换，将较大的元素逐步"冒泡"到数组的末尾。
2.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; } } } }关键点解析：
- 外层循环控制排序轮数
- 内层循环负责相邻元素的比较和交换
- 每轮排序后，最大的元素会"冒泡"到数组末尾
- 时间复杂度为O(n²)，适合小规模数据排序
2.2 冒泡排序的优化版本
基础冒泡排序即使在数组已经有序的情况下也会继续执行所有比较。我们可以通过添加标志位来优化：
void optimizedBubbleSort(int arr[], int n) { int swapped; for (int i = 0; i < n - 1; i++) { swapped = 0; 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; swapped = 1; } } // 如果没有发生交换，说明数组已经有序 if (swapped == 0) break; } }3. 数组去重的多种策略
排序完成后，我们需要去除数组中的重复元素。这里介绍几种常见的去重方法。
3.1 标记法去重
这是最直观的方法之一：将重复元素标记为特定值（如0），然后在输出时跳过这些标记值。
int removeDuplicates(int arr[], int n) { int uniqueCount = n; for (int i = 0; i < n - 1; i++) { if (arr[i] == arr[i + 1]) { arr[i] = 0; // 标记重复元素 uniqueCount--; } } return uniqueCount; }注意事项：
- 此方法会修改原始数组
- 需要先对数组进行排序
- 标记值的选择要确保不会与有效数据冲突
3.2 新建数组法
另一种思路是创建一个新数组，只保留不重复的元素：
int removeDuplicates(int src[], int dest[], int n) { if (n == 0) return 0; int uniqueCount = 1; dest[0] = src[0]; for (int i = 1; i < n; i++) { if (src[i] != src[i - 1]) { dest[uniqueCount++] = src[i]; } } return uniqueCount; }优点：
- 保留原始数组不变
- 逻辑更清晰直观
- 不需要特殊标记值
4. 完整解决方案与代码解析
现在，我们将所有部分组合起来，形成一个完整的解决方案。
4.1 完整代码实现
#include <stdio.h> void optimizedBubbleSort(int arr[], int n) { int swapped; for (int i = 0; i < n - 1; i++) { swapped = 0; 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; swapped = 1; } } if (!swapped) break; } } int removeDuplicates(int arr[], int n) { if (n == 0) return 0; int uniqueCount = 1; for (int i = 1; i < n; i++) { if (arr[i] != arr[i - 1]) { arr[uniqueCount++] = arr[i]; } } return uniqueCount; } int main() { int n; scanf("%d", &n); int numbers[1000]; for (int i = 0; i < n; i++) { scanf("%d", &numbers[i]); } optimizedBubbleSort(numbers, n); int uniqueCount = removeDuplicates(numbers, n); printf("%d\n", uniqueCount); for (int i = 0; i < uniqueCount; i++) { printf("%d ", numbers[i]); } return 0; }4.2 关键代码解析
输入处理部分：
int n; scanf("%d", &n); int numbers[1000]; for (int i = 0; i < n; i++) { scanf("%d", &numbers[i]); }- 首先读取整数个数n
- 然后循环读取n个整数存入数组
排序部分：
optimizedBubbleSort(numbers, n);- 调用优化后的冒泡排序函数
- 排序后数组变为升序排列
去重部分：
int uniqueCount = removeDuplicates(numbers, n);- 调用去重函数，返回不重复元素的数量
- 数组前uniqueCount个元素即为去重后的结果
输出部分：
printf("%d\n", uniqueCount); for (int i = 0; i < uniqueCount; i++) { printf("%d ", numbers[i]); }- 第一行输出不重复元素的数量
- 第二行输出排序去重后的数组元素
5. 进阶思考与扩展
掌握了基础解法后，我们可以思考如何进一步优化和改进这个解决方案。
5.1 更高效的排序算法
虽然冒泡排序易于理解，但其O(n²)的时间复杂度对于大规模数据并不高效。可以考虑：
- 快速排序：平均时间复杂度O(nlogn)
- 归并排序：稳定排序，同样O(nlogn)复杂度
- C标准库的qsort：内置的高效排序实现
#include <stdlib.h> int compare(const void *a, const void *b) { return (*(int*)a - *(int*)b); } // 使用示例 qsort(numbers, n, sizeof(int), compare);5.2 其他去重方法
除了我们已经介绍的方法，还可以考虑：
- 哈希表法：利用哈希表快速判断元素是否已存在
- 位图法：当数据范围有限时非常高效
- STL set（C++）：利用集合自动去重的特性
5.3 边界条件处理
一个健壮的程序应该处理好各种边界情况：
- 输入为空的情况（n=0）
- 所有元素都相同的情况
- 输入包含负数的情况
- 输入超出预期范围的情况
6. 调试技巧与常见问题
初学者在实现这类算法时经常会遇到一些问题，这里总结几个常见陷阱：
数组越界访问：
- 确保循环条件正确，特别是使用i+1访问时
- 示例错误：
for(i=0;i<=n;i++)（应该使用i<n）
去重逻辑错误：
- 未先排序直接去重会导致漏判非相邻重复元素
- 去重后忘记更新元素计数
输出格式问题：
- 最后一个数字后面不应该有空格
- 行末应该换行
调试建议：
- 使用小规模测试数据（如3-5个元素）逐步验证
- 打印中间结果检查排序和去重是否正确
- 使用在线判题系统提供的样例进行测试
7. 从解题到编程思维的培养
这道题目虽然简单，但体现了编程中的几个重要思维模式：
- 分治法：将复杂问题分解为排序、去重等子问题
- 空间-时间权衡：标记法节省空间但修改原数组，新建数组法则相反
- 算法选择：根据数据规模选择合适算法（冒泡适合教学，实际可能选qsort）
- 边界思维：考虑各种极端输入情况
在实际项目中，这种分解问题、选择合适工具、处理各种情况的思维方式同样适用。通过这样一道基础题目的深入剖析，我们不仅学会了具体的技术实现，更重要的是培养了解决问题的系统化思维。
