C语言快速排序详解（从零开始掌握快速排序算法）

快速排序的步骤

1. 从数组中选择一个元素作为基准值（通常选第一个、最后一个或中间元素）。
2. 重新排列数组，使得所有比基准值小的元素放在其左边，所有比基准值大的元素放在其右边（这个过程称为“分区操作”）。
3. 递归地对基准值左右两个子数组重复上述过程，直到子数组长度为1或0（此时已有序）。

C语言快速排序实现

下面是一个完整的C语言排序教程中的经典实现：

#include <stdio.h>// 分区函数：将数组按基准值分割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++;            // 交换 arr[i] 和 arr[j]            int temp = arr[i];            arr[i] = arr[j];            arr[j] = temp;        }    }    // 将基准值放到正确位置    int temp = arr[i + 1];    arr[i + 1] = arr[high];    arr[high] = temp;    return (i + 1);}// 快速排序主函数void quickSort(int arr[], int low, int high) {    if (low < high) {        // 获取分区索引        int pi = partition(arr, low, high);        // 递归排序基准值左右两部分        quickSort(arr, low, pi - 1);        quickSort(arr, pi + 1, high);    }}// 打印数组void printArray(int arr[], int size) {    for (int i = 0; i < size; i++)        printf("%d ", arr[i]);    printf("\n");}// 主函数测试int main() {    int arr[] = {10, 7, 8, 9, 1, 5};    int n = sizeof(arr) / sizeof(arr[0]);    printf("原始数组: \n");    printArray(arr, n);    quickSort(arr, 0, n - 1);    printf("排序后数组: \n");    printArray(arr, n);    return 0;}

代码解析

• partition 函数负责将数组按基准值分割，并返回基准值的最终位置。
• quickSort 是递归函数，不断对子数组进行排序。
• 主函数中创建了一个测试数组，并调用排序函数进行演示。

时间复杂度分析

• 最好情况：每次分区都能将数组均匀分割，时间复杂度为 O(n log n)。
• 平均情况：O(n log n)。
• 最坏情况：每次选到最大或最小元素作基准，退化为 O(n²)，但可通过随机选择基准优化。

总结

通过本教程，你已经掌握了快速排序实现的基本原理和C语言代码编写方法。快速排序不仅效率高，而且代码简洁，是面试和实际开发中的常客。建议你动手敲一遍代码，加深理解！

记住，学习算法的关键在于理解思想+动手实践。希望这篇C语言快速排序教程能为你打下坚实基础！