c语言实现分治法实现快速排序

快速排序是一种常见的基于分治思想的排序算法，可以通过C语言实现。下面是一个简单的快速排序算法实现：

#include <stdio.h>

void quicksort(int arr[], int left, int right) {
    int i = left, j = right;
    int tmp;
    int pivot = arr[(left + right) / 2];

    /* partition */
    while (i <= j) {
        while (arr[i] < pivot) {
            i++;
        }
        while (arr[j] > pivot) {
            j--;
        }
        if (i <= j) {
            tmp = arr[i];
            arr[i] = arr[j];
            arr[j] = tmp;
            i++;
            j--;
        }
    };

    /* recursion */
    if (left < j) {
        quicksort(arr, left, j);
    }
    if (i < right) {
        quicksort(arr, i, right);
    }
}

int main() {
    int arr[] = {5, 3, 7, 2, 8, 4};
    int n = sizeof(arr) / sizeof(arr[0]);
    int i;

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

    quicksort(arr, 0, n - 1);

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

    return 0;
}

在这个程序中，我们首先定义了一个`quicksort`函数来实现快速排序。传入的参数包括待排序的数组、数组的左边界和右边界。

在`quicksort`函数中，我们先选择数组中间的一个元素作为基准值（pivot），然后通过移动左右指针来将数组分为两部分，一部分是小于基准值的，另一部分是大于基准值的。当左右指针相遇时，这个过程就结束了。接下来，我们对两个子数组分别递归调用`quicksort`函数，直到子数组长度为1或0时，递归结束。

最后，在主函数中，我们定义了一个整型数组，并调用`quicksort`函数对其进行排序。