C 排序算法（长文解析）

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

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

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

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

前言

在编程世界中，排序算法是解决数据组织问题的核心工具之一。无论是处理用户数据、优化搜索效率，还是实现高性能计算，排序算法都扮演着不可或缺的角色。在 C 语言中，由于其底层操作和高效执行的特点，掌握排序算法的实现原理和优化技巧，能够帮助开发者在实际项目中显著提升代码的性能。本文将从基础概念出发，逐步解析 C 排序算法的核心思想，并通过具体案例和代码示例，帮助读者深入理解不同算法的实现逻辑和适用场景。

排序算法的基础概念

什么是排序算法？

排序算法是指将一组数据按照特定规则（如升序或降序）重新排列的算法。例如，将一叠杂乱无章的书籍按作者姓名的字母顺序排列，或根据成绩对学生进行排名，这些场景均需要排序算法的支撑。

排序算法的分类

排序算法可以按以下维度进行分类：

1. 按数据移动方式：交换类（如冒泡排序）、选择类（如选择排序）、插入类（如插入排序）等。
2. 按时间复杂度：线性时间（如基数排序）、线性对数时间（如快速排序）、平方时间（如冒泡排序）。
3. 按稳定性：稳定排序（保留相等元素的原始顺序）与非稳定排序。

稳定性的重要性

假设有一组学生数据，其中包含成绩和姓名。若按成绩排序后，需要保持同成绩学生的姓名顺序不变，则必须使用稳定排序算法。例如，归并排序是稳定的，而快速排序则可能打乱原有顺序。

C 语言中常见的排序算法详解

1. 冒泡排序（Bubble Sort）

原理：通过重复遍历数组，比较相邻元素并交换顺序，使较大的元素像“气泡”一样逐渐“浮”到数组末尾。

代码示例：

void bubble_sort(int arr[], int n) {  
    int i, j, temp;  
    for (i = 0; i < n-1; i++) {  
        for (j = 0; j < n-i-1; j++) {  
            if (arr[j] > arr[j+1]) {  
                temp = arr[j];  
                arr[j] = arr[j+1];  
                arr[j+1] = temp;  
            }  
        }  
    }  
}  

时间复杂度：O(n²)，适用于小规模数据。

2. 选择排序（Selection Sort）

原理：每次从未排序的部分中选择最小元素，与未排序部分的起始位置交换。

代码示例：

void selection_sort(int arr[], int n) {  
    int i, j, min_idx, temp;  
    for (i = 0; i < n-1; i++) {  
        min_idx = i;  
        for (j = i+1; j < n; j++)  
            if (arr[j] < arr[min_idx])  
                min_idx = j;  
        temp = arr[min_idx];  
        arr[min_idx] = arr[i];  
        arr[i] = temp;  
    }  
}  

时间复杂度：O(n²)，但交换次数少于冒泡排序。

3. 插入排序（Insertion Sort）

原理：将未排序的数据逐个插入到已排序序列的合适位置，类似打扑克牌时整理手中的牌。

代码示例：

void insertion_sort(int arr[], int n) {  
    int i, key, j;  
    for (i = 1; i < n; i++) {  
        key = arr[i];  
        j = i - 1;  
        while (j >= 0 && arr[j] > key) {  
            arr[j+1] = arr[j];  
            j = j-1;  
        }  
        arr[j+1] = key;  
    }  
}  

时间复杂度：O(n²)，但对“部分有序”的数据表现较好。

4. 快速排序（Quick Sort）

原理：通过分治思想，选择一个“基准值”，将数组分为两部分，左边小于基准值、右边大于基准值，递归排序子数组。

代码示例：

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);  
}  

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

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

时间复杂度：平均 O(n log n)，但最坏情况下为 O(n²)。

5. 归并排序（Merge Sort）

原理：将数组不断拆分为两半，分别排序后再合并。合并时通过比较两个有序子数组的元素，生成新的有序序列。

代码示例：

void merge(int arr[], int l, int m, int r) {  
    int i, j, k;  
    int n1 = m - l + 1;  
    int n2 = r - m;  
    int L[n1], R[n2];  
    for (i = 0; i < n1; i++)  
        L[i] = arr[l + i];  
    for (j = 0; j < n2; j++)  
        R[j] = arr[m + 1 + j];  
    i = 0; j = 0; k = l;  
    while (i < n1 && j < n2) {  
        if (L[i] <= R[j]) {  
            arr[k] = L[i];  
            i++;  
        }  
        else {  
            arr[k] = R[j];  
            j++;  
        }  
        k++;  
    }  
    while (i < n1) {  
        arr[k] = L[i];  
        i++; k++;  
    }  
    while (j < n2) {  
        arr[k] = R[j];  
        j++; k++;  
    }  
}  

void merge_sort(int arr[], int l, int r) {  
    if (l < r) {  
        int m = l + (r - l)/2;  
        merge_sort(arr, l, m);  
        merge_sort(arr, m+1, r);  
        merge(arr, l, m, r);  
    }  
}  

时间复杂度：O(n log n)，稳定但需要额外空间。

排序算法的性能分析与选择

以下表格总结了常见排序算法的关键指标：

选择建议：

• 若内存充足且需稳定性，优先选择归并排序。
• 若数据规模较大，且允许非稳定性排序，快速排序是更优选择。
• 对小规模数据或教学场景，插入排序或冒泡排序更易理解。

实际案例：学生成绩排序

假设有一个学生结构体数组，需按成绩从高到低排序，并保持同分学生的姓名顺序：

#include <stdio.h>  
#include <string.h>  

typedef struct {  
    char name[50];  
    int score;  
} Student;  

// 归并排序的合并函数（针对结构体）  
void merge_students(Student arr[], int l, int m, int r) {  
    int n1 = m - l + 1;  
    int n2 = r - m;  
    Student L[n1], R[n2];  
    for (int i = 0; i < n1; i++)  
        L[i] = arr[l + i];  
    for (int j = 0; j < n2; j++)  
        R[j] = arr[m + 1 + j];  
    int i = 0, j = 0, k = l;  
    while (i < n1 && j < n2) {  
        if (L[i].score >= R[j].score) {  
            arr[k] = L[i];  
            i++;  
        } else {  
            arr[k] = R[j];  
            j++;  
        }  
        k++;  
    }  
    while (i < n1) {  
        arr[k] = L[i];  
        i++; k++;  
    }  
    while (j < n2) {  
        arr[k] = R[j];  
        j++; k++;  
    }  
}  

// 归并排序主函数  
void merge_sort_students(Student arr[], int l, int r) {  
    if (l < r) {  
        int m = l + (r - l)/2;  
        merge_sort_students(arr, l, m);  
        merge_sort_students(arr, m+1, r);  
        merge_students(arr, l, m, r);  
    }  
}  

int main() {  
    Student students[] = {  
        {"Alice", 85},  
        {"Bob", 92},  
        {"Charlie", 85},  
        {"Diana", 90}  
    };  
    int n = sizeof(students)/sizeof(students[0]);  
    merge_sort_students(students, 0, n-1);  
    printf("Sorted by score (descending):\n");  
    for (int i = 0; i < n; i++)  
        printf("%s: %d\n", students[i].name, students[i].score);  
    return 0;  
}  

输出：

Bob: 92  
Diana: 90  
Alice: 85  
Charlie: 85  

此案例展示了如何通过归并排序实现稳定排序，并保持同分学生的原始顺序。

结论

C 排序算法是开发者必须掌握的基础技能，它不仅体现了算法设计的智慧，更是优化代码性能的关键。从冒泡排序到快速排序，每种算法都有其独特的应用场景和优缺点。在实际开发中，选择合适的排序算法需综合考虑数据规模、内存限制和稳定性需求。通过深入理解这些算法的实现原理，并结合代码实践，开发者能够更高效地解决现实问题，并为后续学习更复杂的算法奠定坚实基础。

掌握 C 排序算法不仅能提升编程能力，更能培养逻辑思维和问题分解能力，这对任何一名开发者而言都是不可或缺的成长路径。