从基础到进阶：常见排序算法的C语言实现与深度解析

引言

排序算法是计算机科学中最基础且重要的算法之一，广泛应用于数据库查询、日志处理、数据统计等场景。理解不同排序算法的核心思想、时间复杂度及适用场景，不仅能帮助我们写出更高效的代码，还能在实际工程中根据需求选择最优方案。

本文将以C语言实现为切入点，深入解析插入排序、希尔排序、归并排序、快速排序（双向优化）、堆排序五大经典算法，结合代码逐行分析其底层逻辑，并通过测试用例验证正确性。文末附完整可运行源码。

一、插入排序：从“摸牌”到有序

1.1 算法思想

插入排序的核心思想是将未排序元素逐个插入到已排序序列的正确位置，类似于整理扑克牌的过程：初始时左手为空（已排序序列），每次从桌面（未排序序列）取一张牌，插入左手已有牌中的正确位置。

1.2 代码实现与解析

插入排序代码如下（已修正注释格式）：

void insertion_sort(int arr[], int len) {
    for (int i = 1; i < len; i++) {         // 从第2个元素开始（索引1）
        if (arr[i] < arr[i - 1]) {          // 若当前元素小于前一个（需插入）
            for (int j = i - 1; j >= 0; j--) { // 从i-1向前遍历已排序序列
                if (arr[i] < arr[j]) {        // 找到插入位置（arr[j] > arr[i]）
                    SWAP(arr, i, j);          // 交换i和j位置的元素
                    i = j;                    // 继续向前检查（i更新为j）
                } else {
                    break;                    // 找到正确位置，退出循环
                }
            }
        }
        print_arr(arr, len);                  // 打印每轮排序结果
    }
}

关键细节：

外层循环：i从1开始，代表当前待插入的元素位置（已排序序列长度为i）。
内层循环：j从i-1向前遍历，比较arr[i]与arr[j]，若arr[i]更小则交换，直到找到合适位置。
优化点：通过“向后移动”而非“逐个交换”减少赋值次数（示例代码中实际用了交换，可进一步优化为移动后插入）。

1.3 复杂度分析

时间复杂度：最好情况（已排序）O(n)，最坏情况（逆序）O(n²)。
空间复杂度：O(1)（原地排序）。
稳定性：稳定（相等元素的相对顺序不变）。

二、希尔排序：插入排序的“分组优化”

2.1 算法思想

希尔排序是插入排序的改进版，通过将数组分成多个子序列（间隔为gap），对每个子序列进行插入排序，逐步缩小gap直至为1（此时退化为普通插入排序）。由于初始gap较大，可大幅减少逆序对，提升效率。

2.2 代码实现与解析

void shell_sort(int arr[], int n) {
    int gap = n >> 1;  // 初始间隔为数组长度的一半（n/2）
    while (gap > 0) {  // 间隔递减至0时结束
        for (int i = gap; i < n; i += gap) {  // 遍历每个子序列的起始位置
            if (arr[i] < arr[i - gap]) {       // 若当前元素小于同子序列前一个元素
                for (int j = i - gap; j >= 0; j -= gap) {  // 向前遍历子序列
                    if (arr[i] < arr[j]) {     // 找到插入位置
                        SWAP(arr, i, j);       // 交换元素
                        i = j;                 // 继续向前检查
                    } else {
                        break;                 // 找到正确位置，退出循环
                    }
                }
            }
        }
        print_arr(arr, n);  // 打印每轮排序结果
        gap = gap >> 1;     // 间隔减半（n/4, n/8...）
    }
}

关键细节：

间隔序列：示例中使用gap = n/2 → n/4 → ... → 1，这是最经典的间隔序列，但存在优化空间（如Hibbard序列）。
子序列划分：每个子序列由间隔gap的元素组成（如gap=2时，子序列为arr[0], arr[2], arr[4]...和arr[1], arr[3], arr[5]...）。

2.3 复杂度分析

时间复杂度：取决于间隔序列，经典序列下平均O(n¹·³)，最坏O(n²)。
空间复杂度：O(1)（原地排序）。
稳定性：不稳定（不同子序列的元素可能交换顺序）。

三、归并排序：分治思想的典范

3.1 算法思想

归并排序基于**分治（Divide and Conquer）**策略，核心步骤为：

分割（Divide）：将数组递归划分为两半，直到子数组长度为1（天然有序）。
合并（Merge）：合并两个有序子数组为一个有序数组，通过临时数组暂存结果，避免覆盖原数据。

3.2 代码实现与解析

用户提供的归并排序代码（含临时数组优化）：

// 合并两个有序子数组 [left, mid] 和 [mid+1, right]
void merge(int arr[], int left, int mid, int right, int *tmp) {
    int i = left, j = mid + 1, k = left;  // 左子数组、右子数组、临时数组指针
    // 合并左右子数组到临时数组（直到其中一个遍历完毕）
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];  // 左更小，优先放入
        else tmp[k++] = arr[j++];                   // 右更小，优先放入
    }
    // 处理左子数组剩余元素
    while (i <= mid) tmp[k++] = arr[i++];
    // 处理右子数组剩余元素
    while (j <= right) tmp[k++] = arr[j++];
    // 临时数组内容复制回原数组
    for (i = left; i <= right; i++) arr[i] = tmp[i];
}

// 分治递归函数
void divide_merge(int arr[], int left, int right, int *tmp) {
    if (left >= right) return;  // 递归终止（子数组长度≤1）
    int mid = left + (right - left) / 2;  // 计算中点（防溢出）
    divide_merge(arr, left, mid, tmp);      // 排序左半部分
    divide_merge(arr, mid + 1, right, tmp); // 排序右半部分
    merge(arr, left, mid, right, tmp);      // 合并左右有序子数组
}

// 归并排序入口函数
void merge_sort(int arr[], int len) {
    int *tmp = (int *)calloc(len, sizeof(int));  // 分配临时数组
    if (!tmp) { printf("Memory allocation failed!
"); return; }
    divide_merge(arr, 0, len - 1, tmp);  // 分治排序
    free(tmp);                           // 释放临时数组
    print_arr(arr, len);                 // 输出最终结果
}

关键细节：

临时数组：用于暂存合并结果，避免直接覆盖原数组导致数据丢失。
中点计算：mid = left + (right - left)/2 避免left + right可能溢出。
稳定性：合并时若左右元素相等（arr[i] <= arr[j]），优先选择左子数组元素，保证稳定性。

3.3 复杂度分析

时间复杂度：始终O(n log n)（分割O(log n)层，每层合并O(n)）。
空间复杂度：O(n)（需要额外临时数组）。
稳定性：稳定（相等元素顺序不变）。

四、快速排序：分治的“高效王者”

4.1 算法思想

快速排序同样基于分治策略，核心步骤为：

选择基准（Pivot）：从数组中选取一个元素作为基准值。
分区（Partition）：将数组分为两部分，左边元素≤基准，右边元素≥基准。
递归排序：对左右子数组递归执行上述步骤。

4.2 代码实现与解析（单向分区 vs 双向分区）

4.2.1 单向分区（Lomuto分区）

void quick_sort_one_way(int arr[], int low, int high) {
    if (low >= high) return;  // 递归终止
    int pivot = arr[high];    // 选择最后一个元素作为基准
    int i = low - 1;          // 记录小于基准的右边界
    // 遍历数组，将小于基准的元素移到左边
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            SWAP(arr, i, j);  // 交换i和j位置元素
        }
    }
    // 将基准放到正确位置（i+1）
    SWAP(arr, i + 1, high);
    // 递归排序左右子数组
    quick_sort_one_way(arr, low, i);      // 左半部分（≤基准）
    quick_sort_one_way(arr, i + 2, high); // 右半部分（≥基准）
}

关键细节：

基准选择：示例选择最后一个元素，可能导致最坏情况（如已排序数组）时间复杂度退化为O(n²)。
分区逻辑：通过i记录小于基准的右边界，遍历结束后将基准交换到i+1位置，此时左边全≤基准，右边全≥基准。

4.2.2 双向分区（Hoare分区，优化版）

void quick_sort_two_way(int arr[], int low, int high) {
    if (low >= high) return;
    int pivot = arr[(low + high) / 2];  // 选择中间元素作为基准（防极端情况）
    int left = low - 1, right = high + 1; // 左右指针（初始在边界外）
    while (1) {
        // 左指针右移，找≥基准的元素
        do { left++; } while (arr[left] < pivot);
        // 右指针左移，找≤基准的元素
        do { right--; } while (arr[right] > pivot);
        // 指针相遇或交叉，结束分区
        if (left >= right) break;
        SWAP(arr, left, right);  // 交换左右元素
    }
    // 递归排序左右子数组（right为分区点）
    quick_sort_two_way(arr, low, right);
    quick_sort_two_way(arr, right + 1, high);
}

优化点：

基准选择：中间元素避免已排序数组的最坏情况。
双向扫描：左右指针同时移动，减少不必要的比较，提升效率。

4.3 复杂度分析

时间复杂度：平均O(n log n)，最坏O(n²)（可通过随机选择基准避免）。
空间复杂度：O(log n)（递归栈空间）。
稳定性：不稳定（分区时可能交换相等元素顺序）。

五、堆排序：利用堆结构的原地排序

5.1 算法思想

堆排序基于**堆（Heap）**数据结构（本文为大根堆），核心步骤为：

构建堆：将数组转换为大根堆（父节点≥子节点）。
交换堆顶：将堆顶元素（最大值）与堆尾元素交换，堆大小减1。
调整堆：对新的堆顶元素进行“堆化（Heapify）”，恢复大根堆性质。
重复步骤2-3：直到堆大小为1，此时数组完全有序。

5.2 代码实现与解析

// 堆化函数（大根堆）
void heapify(int arr[], int root, int tree_size) {
    while (1) {
        int left = 2 * root + 1;   // 左子节点索引
        int right = 2 * root + 2;  // 右子节点索引
        int largest = root;        // 记录最大节点索引（初始为根）

        // 比较左子节点（若存在且更大）
        if (left < tree_size && arr[left] > arr[largest]) {
            largest = left;
        }
        // 比较右子节点（若存在且更大）
        if (right < tree_size && arr[right] > arr[largest]) {
            largest = right;
        }
        // 若最大节点不是根，交换并继续堆化
        if (largest != root) {
            SWAP(arr, root, largest);
            root = largest;  // 继续检查子树
        } else {
            break;  // 已满足大根堆性质，退出循环
        }
    }
}

void heap_sort(int arr[], int len) {
    // 步骤1：构建大根堆（从最后一个非叶子节点开始）
    for (int i = len / 2 - 1; i >= 0; i--) {
        heapify(arr, i, len);
    }
    // 步骤2：交换堆顶与堆尾，调整堆
    for (int i = len - 1; i > 0; i--) {
        SWAP(arr, 0, i);        // 交换堆顶（最大值）与堆尾
        heapify(arr, 0, i);     // 调整堆（大小减1）
    }
    print_arr(arr, len);  // 输出排序结果
}

关键细节：

堆的构建：从最后一个非叶子节点（索引len/2 - 1）开始向前遍历，确保每个子树都是大根堆。
堆化过程：通过循环比较根与子节点，将最大值“下沉”到正确位置，保证堆性质。

5.3 复杂度分析

时间复杂度：始终O(n log n)（构建堆O(n)，调整堆O(n log n)）。
空间复杂度：O(1)（原地排序）。
稳定性：不稳定（堆调整可能破坏相等元素顺序）。

六、测试验证与结果对比

6.1 测试用例

使用主函数测试各排序算法（修正后主函数）：

int main(void) {
    int arr_insert[] = {1, 21, 45, 231, 99, 2, 18, 7, 4, 9};
    int len = sizeof(arr_insert) / sizeof(arr_insert[0]);
    printf("插入排序前: ");
    print_arr(arr_insert, len);
    insertion_sort(arr_insert, len);
    printf("插入排序后: ");
    print_arr(arr_insert, len);

    // 类似地添加希尔、归并、快速、堆排序的测试代码...
    return 0;
}

6.2 预期输出

插入排序每轮输出逐步接近有序，最终结果为[1, 2, 4, 7, 9, 18, 21, 45, 99, 231]。其他排序算法最终均应输出有序数组。

七、总结与选择建议

算法	时间复杂度（平均）	时间复杂度（最坏）	空间复杂度	稳定性	适用场景
插入排序	O(n)	O(n²)	O(1)	稳定	小规模/基本有序数据
希尔排序	O(n¹·³)	O(n²)	O(1)	不稳定	中等规模数据（优于插入排序）
归并排序	O(n log n)	O(n log n)	O(n)	稳定	大规模数据/需稳定性
快速排序	O(n log n)	O(n²)	O(log n)	不稳定	大规模数据（内存敏感）
堆排序	O(n log n)	O(n log n)	O(1)	不稳定	大规模数据（内存严格受限）

个人建议：

日常开发中，优先使用语言标准库的排序函数（如C的qsort），其内部已优化。
学习排序算法的核心是理解其思想（如分治、堆性质），而非死记硬背代码。
面试中常考快速排序的分区逻辑、归并排序的空间优化，需重点掌握。

源码附录（完整可运行）

sort.h

#ifndef SORT_H
#define SORT_H

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

#define ARR_SIZE(arr) (sizeof(arr) / sizeof(arr[0]))
#define SWAP(a, b) do { typeof(a) _temp = (a); (a) = (b); (b) = _temp; } while(0)

void print_arr(int arr[], int len);
void insertion_sort(int arr[], int len);
void shell_sort(int arr[], int n);
void merge_sort(int arr[], int len);
void quick_sort_one_way(int arr[], int low, int high);
void quick_sort_two_way(int arr[], int low, int high);
void heap_sort(int arr[], int len);

#endif // SORT_H

sort.c

#include "sort.h"

// 打印数组
void print_arr(int arr[], int len) {
    for (int i = 0; i < len; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

// 插入排序
void insertion_sort(int arr[], int len) {
    for (int i = 1; i < len; i++) {
        if (arr[i] < arr[i - 1]) {
            for (int j = i - 1; j >= 0; j--) {
                if (arr[i] < arr[j]) {
                    SWAP(arr[i], arr[j]);
                    i = j;  // 继续向前检查
                } else {
                    break;  // 找到正确位置
                }
            }
        }
        print_arr(arr, len);
    }
}

// 希尔排序
void shell_sort(int arr[], int n) {
    int gap = n >> 1;
    while (gap > 0) {
        for (int i = gap; i < n; i += gap) {
            if (arr[i] < arr[i - gap]) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[i] < arr[j]) {
                        SWAP(arr[i], arr[j]);
                        i = j;
                    } else {
                        break;
                    }
                }
            }
        }
        print_arr(arr, n);
        gap >>= 1;
    }
}

// 合并两个有序子数组
void merge(int arr[], int left, int mid, int right, int *tmp) {
    int i = left, j = mid + 1, k = left;
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) tmp[k++] = arr[i++];
        else tmp[k++] = arr[j++];
    }
    while (i <= mid) tmp[k++] = arr[i++];
    while (j <= right) tmp[k++] = arr[j++];
    for (i = left; i <= right; i++) arr[i] = tmp[i];
}

// 分治递归函数
void divide_merge(int arr[], int left, int right, int *tmp) {
    if (left >= right) return;
    int mid = left + (right - left) / 2;
    divide_merge(arr, left, mid, tmp);
    divide_merge(arr, mid + 1, right, tmp);
    merge(arr, left, mid, right, tmp);
}

// 归并排序入口
void merge_sort(int arr[], int len) {
    int *tmp = (int *)calloc(len, sizeof(int));
    if (!tmp) {
        printf("Memory allocation failed!
");
        return;
    }
    divide_merge(arr, 0, len - 1, tmp);
    free(tmp);
    print_arr(arr, len);
}

// 单向分区快速排序
void quick_sort_one_way(int arr[], int low, int high) {
    if (low >= high) return;
    int pivot = arr[high];
    int i = low - 1;
    for (int j = low; j < high; j++) {
        if (arr[j] < pivot) {
            i++;
            SWAP(arr[i], arr[j]);
        }
    }
    SWAP(arr[i + 1], arr[high]);
    quick_sort_one_way(arr, low, i);
    quick_sort_one_way(arr, i + 2, high);
}

// 双向分区快速排序
void quick_sort_two_way(int arr[], int low, int high) {
    if (low >= high) return;
    int pivot = arr[(low + high) / 2];
    int left = low - 1, right = high + 1;
    while (1) {
        do { left++; } while (arr[left] < pivot);
        do { right--; } while (arr[right] > pivot);
        if (left >= right) break;
        SWAP(arr[left], arr[right]);
    }
    quick_sort_two_way(arr, low, right);
    quick_sort_two_way(arr, right + 1, high);
}

// 大根堆调整
void heapify(int arr[], int root, int tree_size) {
    while (1) {
        int left = 2 * root + 1, right = 2 * root + 2;
        int largest = root;
        if (left < tree_size && arr[left] > arr[largest]) largest = left;
        if (right < tree_size && arr[right] > arr[largest]) largest = right;
        if (largest != root) {
            SWAP(arr[root], arr[largest]);
            root = largest;
        } else break;
    }
}

// 堆排序入口
void heap_sort(int arr[], int len) {
    for (int i = len / 2 - 1; i >= 0; i--) heapify(arr, i, len);
    for (int i = len - 1; i > 0; i--) {
        SWAP(arr[0], arr[i]);
        heapify(arr, 0, i);
    }
    print_arr(arr, len);
}

int main(void) {
    int arr_insert[] = {1, 21, 45, 231, 99, 2, 18, 7, 4, 9};
    int len = ARR_SIZE(arr_insert);
    printf("=== 插入排序 ===
原数组: ");
    print_arr(arr_insert, len);
    insertion_sort(arr_insert, len);
    printf("最终结果: ");
    print_arr(arr_insert, len);

    // 可添加其他排序的测试代码...
    return 0;
}

注：实际使用时，需将sort.h和sort.c编译链接后运行。