C语言实现快速排序算法 - 代码示例及解析

以下是一个快速排序算法的C语言程序：

#include <stdio.h>

// 交换元素位置
void swap(int* a, int* b) {
    int t = *a;
    *a = *b;
    *b = t;
}

// 分割数组
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 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[] = {64, 25, 12, 22, 11};
    int n = sizeof(arr) / sizeof(arr[0]);
    
    printf("排序前的数组：\n");
    printArray(arr, n);
    
    quickSort(arr, 0, n - 1);
    
    printf("排序后的数组：\n");
    printArray(arr, n);
    
    return 0;
}

该程序实现了快速排序算法。在主函数中，我们定义了一个整型数组 arr，并初始化了一些随机元素。然后调用 quickSort 函数对数组进行排序。最后，通过 printArray 函数打印排序后的数组。运行程序后，将会输出排序前和排序后的数组。

代码解析：

swap(int* a, int* b) 函数： 该函数用于交换两个整数元素的位置。
partition(int arr[], int low, int high) 函数： 该函数负责对数组进行分区操作。它选择最后一个元素作为枢纽元素，将比枢纽元素小的元素放在其左侧，比枢纽元素大的元素放在其右侧，并返回枢纽元素的最终位置。
quickSort(int arr[], int low, int high) 函数： 该函数是快速排序算法的核心函数。它使用递归的方式对数组进行排序。首先调用 partition 函数对数组进行分区，然后递归地对左子数组和右子数组进行排序。
printArray(int arr[], int size) 函数： 该函数用于打印数组元素。
main 函数： 主函数中定义了一个待排序数组 arr，调用 quickSort 函数进行排序，并调用 printArray 函数打印排序结果。

快速排序算法的核心思想：

快速排序算法是一种分治算法，其核心思想是将待排序的数组划分为两个子数组，分别对子数组进行排序，然后将排序后的子数组合并。具体步骤如下：

选择一个枢纽元素： 通常选择最后一个元素作为枢纽元素。
分区： 将数组划分为两个子数组，左侧子数组包含所有小于枢纽元素的元素，右侧子数组包含所有大于枢纽元素的元素。
递归排序： 递归地对左子数组和右子数组进行排序。
合并： 排序后的左子数组和右子数组自动合并为一个排序后的数组。

快速排序算法的优点：

平均时间复杂度为 O(n log n)，效率较高。
是一种原地排序算法，不需要额外的空间。

快速排序算法的缺点：

最坏情况下时间复杂度为 O(n^2)，例如数组已经排序或逆序排序。
不稳定排序，排序后相同元素的相对位置可能发生改变。

总结：

快速排序算法是一种常用的排序算法，它效率高、空间复杂度低，但最坏情况下效率会很低。在实际应用中，需要根据数据特点选择合适的排序算法。