分治法解决快速排序C语言

快速排序是一种基于分治思想的排序算法。其核心思想是通过一次排序将待排序序列分成两个子序列，其中一个子序列的所有元素都小于另一个子序列的所有元素，然后对这两个子序列分别进行递归排序，直到整个序列有序。

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

#include<stdio.h>

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

    while(i <= j){
        while(arr[i] < pivot)
            i++;
        while(arr[j] > pivot)
            j--;
        if(i <= j){
            temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
            i++;
            j--;
        }
    }

    if(left < j){
        quick_sort(arr, left, j);
    }
    if(i < right){
        quick_sort(arr, i, right);
    }
}

int main(){
    int arr[] = {10, 7, 8, 9, 1, 5};
    int n = sizeof(arr) / sizeof(arr[0]);

    quick_sort(arr, 0, n - 1);

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

    return 0;
}

在实现中，我们以数组中间的元素为基准点，将数组分为左右两个子序列，并对这两个子序列进行递归排序，直到整个序列有序。在排序过程中，我们维护两个指针i和j，分别从序列的左右两边逼近，当i所指向的元素大于等于基准点时，停止移动；当j所指向的元素小于等于基准点时，停止移动。如果i和j都停止移动，且i <= j，则交换i和j所指向的元素，并将i和j分别向右和向左移动一位。重复上述过程，直到i > j为止。最后，我们将数组分为的左右两个子序列分别进行递归排序。