C语言快速排序法

快速排序（Quick Sort）是一种常用的排序算法，它基于分治法（Divide and Conquer）的思想，通过将数组分成较小的子数组，然后对子数组进行排序，最后合并子数组以达到整体有序的目的。以下是一个使用 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; 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 pivotIndex = partition(arr, low, high);  // 获取基准值位置
        quickSort(arr, low, pivotIndex - 1);         // 对左子数组递归排序
        quickSort(arr, pivotIndex + 1, high);        // 对右子数组递归排序
    }
}

int main() {
    int arr[] = {56, 10, 89, 32, 6, 70, 49};
    int size = sizeof(arr) / sizeof(arr[0]);

    printf("未排序数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    quickSort(arr, 0, size - 1);

    printf("快速排序后数组：");
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\\n");

    return 0;
}

在这段代码中，swap 函数用于交换数组中两个元素的值。partition 函数用于将数组分成两部分，小于基准值的元素在基准值左边，大于基准值的元素在基准值右边，并返回基准值的位置。quickSort 函数是主要的快速排序函数，它使用递归的方式对数组进行分治排序。

快速排序算法的平均时间复杂度为 O(n log n)，但最坏情况下可能达到 O(n^2)，这取决于选择的基准值以及数组的初始排序情况。在实际应用中，通常快速排序表现良好，并且是常用的排序算法之一。