C 排序算法（实战指南）

C 排序算法入门：从冒泡到快速排序的实战解析

在学习编程的道路上，排序算法就像是一块试金石。它看似简单，实则蕴含着丰富的思维逻辑与性能权衡。对于初学者来说，掌握 C 排序算法不仅是理解程序控制流程的关键，更是提升代码效率和算法思维的重要一步。今天，我们就来一起走进 C 排序算法的世界，用通俗易懂的方式，从基础到进阶，一步步拆解几个经典算法的实现原理与应用场景。

我们不会一开始就堆砌复杂的公式或抽象理论，而是从最直观的冒泡排序开始，逐步过渡到更高效的快排与归并，让你在动手实践中真正理解“排序”背后的逻辑。

冒泡排序：像水泡一样逐层上升

想象一下，你把一桶水倒进一个透明的玻璃缸，里面漂浮着一些大小不一的气泡。小气泡会慢慢上升，大气泡则下沉。冒泡排序就是这个过程的代码模拟：它通过不断比较相邻的元素，把“大的”往后面推，就像气泡往上浮一样。

在 C 语言中，冒泡排序的实现非常直观。我们用一个双层循环来完成这个过程。

#include <stdio.h>

// 冒泡排序函数：对数组进行升序排列
void bubble_sort(int arr[], int n) {
    // 外层循环控制排序轮数，共 n-1 轮
    for (int i = 0; i < n - 1; i++) {
        // 标记本轮是否发生交换，用于优化
        int swapped = 0;

        // 内层循环负责相邻元素的比较与交换
        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;
                swapped = 1; // 标记发生了交换
            }
        }

        // 如果本轮没有交换，说明数组已经有序，可以提前结束
        if (swapped == 0) {
            break;
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    bubble_sort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码注释说明：

• n - 1 轮是因为空间复杂度的最小需求：n 个元素最多需要 n-1 轮才能确定顺序。
• swapped 变量是优化关键：如果某一轮没有交换，说明数组已有序，无需继续。
• 时间复杂度：最坏情况 O(n²)，最好情况 O(n)，空间复杂度 O(1)，是原地排序。

虽然冒泡排序效率不高，但它是理解排序思想的“入门第一课”。就像学骑自行车，先学会平衡，再追求速度。

选择排序：每次挑出最小的

如果说冒泡排序是“不断交换相邻元素”，那么选择排序更像是“每轮选出最小的，放到最前面”。

想象你在整理一排书，每次从剩下的书中找出最薄的一本，直接放到最左边。选择排序的思路就是如此：每一轮在未排序部分中找到最小值，然后与该轮的起始位置交换。

#include <stdio.h>

// 选择排序函数：升序排列
void selection_sort(int arr[], int n) {
    // 外层循环：控制当前要确定位置的元素
    for (int i = 0; i < n - 1; i++) {
        // 假设当前位置 i 就是未排序部分的最小值下标
        int min_idx = i;

        // 在未排序部分（i 到 n-1）中寻找真正的最小值
        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;
        }
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    selection_sort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码注释说明：

• 每次只交换一次，减少了冒泡排序中频繁的交换次数。
• 时间复杂度稳定在 O(n²)，无论最好或最坏情况。
• 空间复杂度仍是 O(1)，属于原地排序。

选择排序虽然效率不如高级算法，但它的逻辑清晰、实现简单，适合初学者理解“排序”的本质：每次确定一个元素的最终位置。

插入排序：像整理扑克牌一样自然

当你打完扑克牌后，会习惯性地从左到右一张张整理。你把每张新牌插入到已排序牌堆的正确位置——这正是插入排序的核心思想。

它适合小规模数据或部分有序的数据，比如你已经排好了一堆牌，只来了几张新牌。

#include <stdio.h>

// 插入排序函数
void insertion_sort(int arr[], int n) {
    // 从第二个元素开始（下标 1），因为第一个元素默认已排序
    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];
            j--;
        }

        // 把 key 插入到正确位置
        arr[j + 1] = key;
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    insertion_sort(arr, n);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码注释说明：

• key 是当前待插入的元素，保护它不被覆盖。
• while 循环将比 key 大的元素后移，为 key 留出空间。
• 最好情况 O(n)，最坏 O(n²)，但对小数组或近似有序数组表现极佳。

插入排序是 C 排序算法中“最生活化”的一种，它告诉我们：算法不必复杂，也能高效。

快速排序：分治思想的典范

如果说前面的算法是“逐步推进”，那么快速排序就是“分而治之”的高手。它通过一个“基准值”（pivot）将数组分成两部分：小于基准的放左边，大于基准的放右边。然后递归地对左右两部分继续排序。

这就像你在组织一场会议，先请一个人当“主持人”，让所有人按“是否比他高”站成两队，再让每队各自选出新主持人继续分组。

#include <stdio.h>

// 快速排序的分区函数：返回基准值的最终位置
int partition(int arr[], int low, int high) {
    int pivot = arr[high]; // 选择最后一个元素作为基准
    int i = low - 1;       // 小于基准的元素的边界

    // 遍历从 low 到 high-1 的元素
    for (int j = low; j < high; j++) {
        // 如果当前元素小于等于基准，就把它放到左边
        if (arr[j] <= pivot) {
            i++;
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    }

    // 将基准放到正确位置（i+1）
    int temp = arr[i + 1];
    arr[i + 1] = arr[high];
    arr[high] = temp;

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

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quick_sort(arr, 0, n - 1);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码注释说明：

• partition 函数是核心，负责划分区域。
• pivot 的选择影响性能，可以优化为“三数取中”。
• 平均时间复杂度 O(n log n)，最坏 O(n²)，但实际中表现极佳。
• 空间复杂度 O(log n)，由于递归调用栈。

快速排序是 C 排序算法中“效率之王”，也是面试高频题。掌握它，意味着你已经具备了应对中等规模数据排序的能力。

归并排序：稳定且高效，适合大数据

当数据量特别大，且要求排序“稳定”（相等元素顺序不变）时，归并排序是理想选择。它的核心思想是“分而治之 + 合并”。

想象你有一堆散乱的纸牌，你不断把它们分成两半，直到每堆只有一张，然后一层层合并，每次合并时都保持顺序。

#include <stdio.h>

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right) {
    int n1 = mid - left + 1; // 左子数组长度
    int n2 = right - mid;     // 右子数组长度

    // 创建临时数组
    int L[n1], R[n2];

    // 复制数据到临时数组
    for (int i = 0; i < n1; i++) {
        L[i] = arr[left + i];
    }
    for (int j = 0; j < n2; j++) {
        R[j] = arr[mid + 1 + j];
    }

    // 合并临时数组回原数组
    int i = 0, j = 0, k = left;

    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 left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;

        merge_sort(arr, left, mid);      // 递归排序左半部分
        merge_sort(arr, mid + 1, right); // 递归排序右半部分
        merge(arr, left, mid, right);    // 合并两部分
    }
}

int main() {
    int arr[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("排序前的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    merge_sort(arr, 0, n - 1);

    printf("排序后的数组：");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    return 0;
}

代码注释说明：

• merge 函数是关键，确保合并过程有序。
• 时间复杂度稳定在 O(n log n)，适合大数据。
• 空间复杂度 O(n)，因为需要临时数组。
• 是稳定排序算法，相等元素顺序不变。

归并排序虽然占内存较多，但它的稳定性与高效性使其在外部排序、大文件处理中广泛应用。

C 排序算法总结与学习建议

通过冒泡、选择、插入、快速、归并这五种经典 C 排序算法的学习，我们不仅掌握了代码实现，更重要的是理解了算法设计的思维方式：比较、交换、分治、递归。

每种算法都有其适用场景：

• 小数据集或教学：冒泡、选择、插入
• 通用高效：快速排序（最常用）
• 稳定性要求高：归并排序

在实际开发中，C 排序算法虽然不如标准库 qsort 那样方便，但理解其底层原理，能让你在性能调优、内存管理、算法设计中游刃有余。

最后提醒：不要死记代码，而是多问“为什么这样写？”“如果数据规模变大，会怎样？”——这才是学习 C 排序算法的真正意义。

当你能从“会写”走向“理解”，你就真正掌握了 C 排序算法的精髓。