C 练习实例37 – 排序（一文讲透）

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战(已更新的所有项目都能学习) / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

• 新开坑项目:《Spring AI 项目实战》 正在持续爆肝中，基于 Spring AI + Spring Boot 3.x + JDK 21...， 点击查看 ;
• 《从零手撸：仿小红书（微服务架构）》 已完结，基于 Spring Cloud Alibaba + Spring Boot 3.x + JDK 17...，点击查看项目介绍 ;演示链接： http://116.62.199.48:7070 ;
• 《从零手撸：前后端分离博客项目（全栈开发）》 2 期已完结，演示链接： http://116.62.199.48/ ;

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言

排序是编程中一个核心且高频的需求。无论是处理数据、优化算法效率，还是解决实际问题，排序算法都是开发者必须掌握的基础技能之一。在经典的《C 语言练习实例》中，实例37要求编写一个排序程序，通过这一案例，我们可以系统地学习排序算法的原理、实现方法以及优化技巧。本文将从零开始，逐步拆解这一实例，帮助读者理解排序逻辑，并掌握如何在 C 语言中实现排序功能。

排序基础：概念与常见算法

什么是排序？

排序（Sorting）是指将一组数据按照特定规则（如升序或降序）重新排列的过程。例如，整理一叠杂乱的书籍，可以按书名字母顺序或出版年份进行排序。在计算机领域，排序算法通过一系列规则比较和交换数据元素的位置，最终得到有序的序列。

常见排序算法分类

排序算法根据实现原理和性能特点可分为多种类型，常见的包括：

• 冒泡排序：通过重复交换相邻元素，将较大元素“冒泡”到数组末尾。
• 选择排序：每次从未排序部分选择最小元素，放到已排序序列的末尾。
• 插入排序：类似整理扑克牌，将新元素插入到已排序序列的合适位置。
• 快速排序：通过分治策略递归分割数组，效率较高但实现较复杂。
• 归并排序：将数组拆分为小片段排序后再合并，稳定性较好但占用额外空间。

实例37解析：目标与实现思路

实例37的具体要求

假设实例37的目标是：输入一组整数，使用排序算法将它们按升序排列，并输出结果。例如，输入 5 3 8 1 9，输出 1 3 5 8 9。

算法选择与实现逻辑

对于初学者，冒泡排序是理想的入门算法，因为它逻辑直观且容易实现。其核心思想是：

1. 依次比较相邻元素，如果顺序错误则交换它们的位置。
2. 每一轮遍历会将未排序部分的最大值“冒泡”到末尾。
3. 重复这一过程，直到整个数组有序。

代码示例：冒泡排序的实现

步骤1：输入与初始化

首先，需要读取用户输入的整数，并存储到数组中。例如：

#include <stdio.h>  
#define MAX_SIZE 100  

int main() {  
    int arr[MAX_SIZE], n, i;  
    printf("Enter number of elements (max %d): ", MAX_SIZE);  
    scanf("%d", &n);  

    printf("Enter elements:\n");  
    for (i = 0; i < n; i++) {  
        scanf("%d", &arr[i]);  
    }  

    // 排序逻辑将在此处添加  

    printf("Sorted array in ascending order:\n");  
    for (i = 0; i < n; i++) {  
        printf("%d ", arr[i]);  
    }  
    return 0;  
}

步骤2：实现冒泡排序算法

在上述代码中，插入冒泡排序的逻辑：

// 冒泡排序实现  
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;  
        }  
    }  
}

完整代码整合

将排序逻辑与输入输出结合，即可完成实例37的实现。

算法优化与扩展

优化冒泡排序：提前终止遍历

在标准冒泡排序中，即使数组提前有序，算法仍会执行所有循环。通过添加一个标志变量，可以在一轮遍历中检测到无交换操作时提前终止：

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]) {  
            swap(&arr[j], &arr[j+1]);  
            swapped = 1;  
        }  
    }  
    if (swapped == 0) break;  
}  

尝试其他算法：快速排序的实现

对于更高效的排序需求，可以引入快速排序。其核心是选择一个基准值（pivot），将数组分为两部分：

• 小于基准值的元素放在左边
• 大于基准值的元素放在右边

递归地对子数组重复这一过程。例如：

void quick_sort(int arr[], int low, int high) {  
    if (low < high) {  
        int pivot = partition(arr, low, high);  
        quick_sort(arr, low, pivot - 1);  
        quick_sort(arr, pivot + 1, high);  
    }  
}  

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++;  
            swap(&arr[i], &arr[j]);  
        }  
    }  
    swap(&arr[i+1], &arr[high]);  
    return (i + 1);  
}

常见问题与解决方法

问题1：交换元素时出错

现象：排序结果混乱，元素未正确交换。
原因：未正确使用临时变量，或指针操作有误。
解决：确保交换逻辑完整，例如：

void swap(int* a, int* b) {  
    int temp = *a;  
    *a = *b;  
    *b = temp;  
}  

问题2：内存越界

现象：程序崩溃或输出异常值。
原因：数组索引超出范围（如 n 超过 MAX_SIZE）。
解决：在输入时验证 n 的合法性，并设置合理的最大值限制。

排序算法的性能分析

时间复杂度比较

如何选择排序算法？

• 小数据量：冒泡排序或插入排序更简单直接。
• 大数据量：优先选择快速排序或归并排序。
• 稳定性要求：归并排序或插入排序更适合需要保持相同元素相对顺序的场景。

结论：从实例37到进阶

通过练习实例37，我们不仅掌握了排序算法的实现，还理解了不同算法的优缺点。排序不仅是技术问题，更是对逻辑思维的训练：通过分解问题（如分治策略）、优化细节（如提前终止遍历），开发者能逐步提升代码的效率与可读性。

建议读者在掌握基础算法后，尝试以下进阶实践：

1. 实现其他排序算法（如选择排序、插入排序）。
2. 测试不同算法在不同数据规模下的性能差异。
3. 将排序函数封装为通用工具，供其他程序调用。

通过持续练习与优化，排序这一看似基础的技能，将成为解决复杂问题的基石。