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);  // 对大于基准的部分进行递归排序
    }
}

在上面的代码中，swap函数用于交换两个元素的值，partition函数用于将数组分为两部分，并返回基准元素的索引。quickSort函数是快速排序的主体，它首先调用partition函数获取基准元素的索引，然后递归地对小于基准和大于基准的部分进行排序。

以下是快速排序的性能分析：

• 最好情况下的时间复杂度：O(n log n)，此时每次划分都能大致将数组分成相等的大小。
• 最坏情况下的时间复杂度：O(n^2)，此时每次划分都使得一个部分为空，另一个部分包含所有元素。但这种情况出现的概率很小。
• 平均时间复杂度：O(n log n)。
• 空间复杂度：O(log n)，需要递归调用的栈空间。

在实际应用中，快速排序是一种非常高效的排序算法，尤其在处理大型数据集时。但需要注意的是，对于特定类型的数据集（例如已经部分排序的），可能需要选择其他的排序算法来获得更好的性能。