头歌（C语言）-数据结构与算法-排序-第2关：实现快速排序

头歌（C语言）中的快速排序是一种高效的排序算法，它基于分治策略。以下是快速排序的基本步骤：

1. **选择基准**：通常选择数组的第一个元素作为基准值（pivot）。

2. **分区过程**：
- 将数组分为两部分：一部分包含所有小于基准值的元素，另一部分包含所有大于或等于基准值的元素。
- 这通常通过一趟从左到右的扫描完成，遇到比基准值小的数就交换到数组左边，遇到大的数则不动。

3. **递归排序**：
- 对左右两个分区分别进行快速排序，直到每个分区只剩下一个元素，此时视为已经排好序。

4. **合并结果**：最后将这三个已排序的部分合并成一个有序序列。

下面是快速排序的一个简单示例（使用了迭代法而非传统的递归形式以减少栈空间消耗）：

#include <stdio.h>
#include <stdlib.h>

void swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

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); // 递归处理右侧
    }
}

// 示例
int main() {
    int arr[] = {9, 7, 5, 11, 12, 2, 14, 3};
    int n = sizeof(arr) / sizeof(arr[0]);

    quickSort(arr, 0, n - 1);
    
    for (int i = 0; i < n; i++)
        printf("%d ", arr[i]);
    printf("\n");
    return 0;
}