快速排序递归与非递归，C语言实例

快速排序是一种常用的高效排序算法，它的基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分继续进行排序，以达到整个序列有序。

**递归实现**:
递归版快速排序通常采用分治策略。这里是一个简单的C语言例子：

#include <stdio.h>

void quicksort(int arr[], int low, int high) {
    if (low < high) {
        // 找到基准值的索引
        int pivot_index = partition(arr, low, high);
        
        // 对基准值左边和右边的部分递归排序
        quicksort(arr, low, pivot_index - 1);
        quicksort(arr, pivot_index + 1, high);
    }
}

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 swap(int* a, int* b) {
    int temp = *a;
    *a = *b;
    *b = temp;
}

// 测试
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]);
    return 0;
}

运行上述代码会将数组按升序排列。

**非递归实现**:
非递归版本通常使用栈数据结构来保存分割过程中的子区间。但是由于C语言原生没有内置栈支持，需要自己手动管理堆栈，这相对复杂一些，适合学习递归思路后再深入了解。