纯C语言实现分治快速排序：两种经典算法源码解析

方法一：基础递归式快速排序

这段代码展示了一种直观的快速排序实现。它选取数组第一个元素作为基准（pivot），通过双向扫描将小于基准的元素移到左侧，大于基准的移到右侧，然后递归处理左右子区间。虽然逻辑清晰，但其中的数组移动方式并非最优的空位填补法，且存在潜在的递归边界判断冗余，适合作为理解递归思想的入门示例。

第1步：定义分区函数 fun

该函数接收数组指针及当前处理的起始索引 low 和结束索引 high。其核心目的是将数组在 [low, high] 范围内按基准值进行划分。

#include <stdio.h>

void fun(int array[], int low, int high) {
    int i = low;
    int j = high;
    int temp = array[i]; // 选取首元素作为基准

    while (i < j) {
        // 从右向左扫描，找到小于 temp 的元素
        while ((array[j] >= temp) && (i < j)) {
            j--;
            array[i] = array[j]; // 小值填到左边空位
        }
        // 从左向右扫描，找到大于 temp 的元素
        while ((array[i] <= temp) && (i < j)) {
            i++;
            array[j] = array[i]; // 大值填到右边空位
        }
    }
    array[i] = temp; // 基准值放入最终位置

    // 递归处理左半部分
    if (i - 1 > low) {
        fun(array, low, i - 1);
    }
    // 递归处理右半部分
    if (high > i + 1) { // 注意：此处逻辑依赖上一轮后的 i/j 状态，通常应为 array[j+1] 或 array[i+1]
        fun(array, j + 1, high);
    } else {
        return;
    }
}

第2步：主程序入口与交互

在主函数中动态读取10个整数，调用 fun 进行排序，并输出结果。此段代码使用了较旧的 C 风格（void main, <iostream.h> 混合），在实际现代 C 项目中建议替换为标准 int main 和 <stdlib.h>。

void main() {
    int array[10];
    printf("输入十个数字进行快速排序：\n");
    for (int i = 0; i < 10; i++) {
        printf("请输入第%d个数：", i + 1);
        scanf("%d", &array[i]);
    }
    fun(array, 0, 9);
    printf("对这十个数字从小到大快速排序得：");
    for (int i = 0; i < 10; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

方法二：经典双指针 Partition 实现

这是更为通用的快速排序变体。它引入了一个独立的 partition 函数，利用两个指针 i 和 j 分别从两端向中间逼近。当发现逆序对时进行交换，最后将基准值置于正确位置。这种方式在工程实践中更为常见，因为其分区逻辑解耦，便于优化（如随机选取基准值）。请注意，此版本使用了 C++ 的特性（iostream, malloc），需在支持 C++ 的环境中编译，或手动转换为标准 C 的 printf/scanf 和 malloc/free。

第1步：辅助交换与分区逻辑

interchange 用于交换两个指针指向的值。partition 选定第一个元素为基准，i 从 p+1 开始向右找大于基准的，j 从 q 开始向左找小于基准的。若发现逆序则交换，直到指针相遇，最后将基准与 j 位置交换。

#include <iostream.h>
#include <malloc.h>

void interchange(int* m, int* n) {
    int temp = *m;
    *m = *n;
    *n = temp;
}

int partition(int array[], int p, int q) {
    int i, j;
    i = p;
    j = q + 1;
    while (1) {
        do { i++; } while ((array[i] < array[p]) && (i != q));
        do { j--; } while ((array[j] > array[p]) && (j != p));
        if (i < j) {
            interchange(&array[i], &array[j]);
        } else {
            break;
        }
    }
    interchange(&array[p], &array[j]);
    return j;
}

第2步：递归排序与动态内存管理

quicksort 递归调用 partition 返回的分割点。主程序中通过 malloc 动态申请内存以支持任意数量 n 的排序。需特别注意：在纯 C 环境中需包含 <stdlib.h> 并使用 free(a) 释放内存，否则会导致内存泄漏。

void quicksort(int array[], int p, int q) {
    int j;
    if (p < q) {
        j = partition(array, p, q);
        quicksort(array, p, j - 1);
        quicksort(array, j + 1, q);
    }
}

void main() {
    int n, i;
    cout << "please input the number of array:";
    cin >> n;
    int* a = (int*)malloc(n * sizeof(int));
    
    for (i = 0; i < n; i++) {
        cout << "please the " << i + 1 << "th element :";
        cin >> a[i];
    }
    
    cout << "before sort:";
    for (i = 0; i < n; i++)
        cout << a[i] << "  ";
    cout << endl;
    
    quicksort(a, 0, n - 1);
    
    cout << "after sort:";
    for (i = 0; i < n; i++)
        cout << a[i] << "  ";
    cout << endl;
    
    // 重要：释放动态分配的内存
    free(a);
}

注意事项与排错

• 头文件兼容性：示例代码中混用了 C 标准库（stdio.h）和 C++ I/O 流（iostream）。若使用 GCC 编译纯 C 文件，请移除 iostream 相关代码，改用 printf/scanf。
• 内存泄漏风险：在方法二中使用了 malloc 分配堆内存，务必在程序结束前调用 free()，尤其是在循环测试多次输入时。
• 递归深度：快速排序在最坏情况（已排序数组且未随机化基准）下时间复杂度退化为 $O(n^2)$，递归栈深度可能较大。对于超大数据量，建议结合随机基准选择或三数取中法优化。

以上就是C语言实现分治快速排序两种经典源码的详细内容，更多关于算法与C语言进阶的资料请关注本站其它相关文章！