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); // 对基准值右侧的元素进行递归排序
    }
}

// 主函数
int main() {
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    printf("Original array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");

    quickSort(arr, 0, n - 1);

    printf("Sorted array: \n");
    for (int i = 0; i < n; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
    return 0;
}

这段代码实现了快速排序算法。在快速排序中，我们选择一个元素作为基准值，然后将小于基准值的元素放到其左边，大于基准值的元素放到其右边。然后对基准值左右两侧的子数组进行递归排序，直到整个数组有序。

让我进一步解释代码中的几个关键点：

swap() 函数：
这个函数用于交换两个元素的值，它是快速排序中的一个常见操作。

partition() 函数：
这个函数选择数组中的最后一个元素作为基准值 pivot，然后将数组分割成两部分，一部分是小于等于 pivot 的元素，另一部分是大于 pivot 的元素。函数返回基准值的索引，以便后续的递归调用。

quickSort() 函数：
这个函数是递归调用的核心。它首先通过 partition() 函数将数组分割成两部分，然后对每个部分递归地调用 quickSort() 函数，直到数组完全排序。

main() 函数：
主函数中包含了一个示例数组，调用 quickSort() 函数对其进行排序，并输出排序前后的数组。