分治法实现快速排序算法C语言

分治法是一种将复杂问题分解成更小的、相似的部分，然后分别解决这些部分，并将结果合并的方法。在快速排序（Quick Sort）这个经典的排序算法中，它采用了递归的方式来实现分治策略：

首先，快速排序选择一个基准元素（pivot），通常选取数组的第一个元素或最后一个元素。然后将数组分为两个子数组：
1. 小于基准的元素放在左边，大的元素放在右边。
2. 对左右两个子数组分别应用同样的快速排序过程，直到每个子数组只剩下一个元素，排序完成。

以下是基本的C语言实现快速排序的一个简化版伪代码：

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        int pivot = partition(arr, low, high); // 分区函数确定基准位置
        quicksort(arr, low, pivot - 1);    // 对左半部分递归排序
        quicksort(arr, pivot + 1, high);   // 对右半部分递归排序
    }
}

int partition(int arr[], int low, int high) {
    int pivot = arr[high];   // 基准元素
    int i = low - 1;          // 小于基准的元素索引

    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;
}