快速排序

快速排序（Quick Sort）是一种常用的排序算法，也是一种分治策略的算法。它的基本思想是选择一个基准元素，然后将数组中小于该元素的放在左边，大于该元素的放在右边，然后递归地对左右两部分进行排序，直到整个序列有序。

以下是快速排序的一般步骤：

1. 选取一个基准元素，一般选取序列的第一个元素；
2. 将序列中小于基准元素的移到基准元素的左边，大于基准元素的移到右边；
3. 对左右两个子序列分别递归地进行快速排序；
4. 递归结束条件是子序列只剩下一个元素或者为空。

快速排序的时间复杂度为 O(nlogn)，空间复杂度为 O(logn)，其中 n 表示数组的长度。

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

#include <stdio.h>

void quicksort(int arr[], int left, int right) {
    int i = left, j = right;
    int temp, 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) quicksort(arr, left, j);
    if (i < right) quicksort(arr, i, right);
}

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

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

    quicksort(arr, 0, n - 1);

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

    return 0;
}

该实现代码使用了递归方式进行快速排序，以数组中间的元素作为基准元素，通过比较大小将数组分成两个子数组进行排序，最终将两个子数组合并成一个有序数组。