C语言快速排序算法实现与代码示例

快速排序是一种高效的排序算法，其平均时间复杂度为O(n log n)。

以下是使用C语言实现快速排序的示例代码：

#include <stdio.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];  // 选取最后一个元素作为基准
    int i = (low - 1);  // i为小于基准的元素的最右位置

    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[] = {64, 34, 25, 12, 22, 11, 90};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);
    
    printf('排序后的数组：');
    for (int i = 0; i < n; i++) {
        printf('%d ', arr[i]);
    }
    
    return 0;
}

代码说明:

swap 函数: 该函数用于交换数组中两个元素的位置。
partition 函数: * 选择数组的最后一个元素作为基准元素。
- 遍历数组，将小于等于基准元素的元素放到左侧，大于基准元素的元素放到右侧。
- 将基准元素放到正确的位置，并返回其索引。
quickSort 函数:
- 递归地调用 partition 函数对数组进行划分。
- 对划分后的子数组进行递归排序，直到子数组的大小为 1 或 0。
main 函数:
- 创建一个示例数组 arr。
- 调用 quickSort 函数对数组进行排序。
- 打印排序后的数组。

运行结果：

排序后的数组：11 12 22 25 34 64 90

这段代码演示了如何使用 C 语言实现快速排序算法。快速排序是一种高效的排序算法，适用于各种应用场景。