快速排序的非递归算法 C语言

快速排序是一种常用的排序算法，其基本思想是通过一趟排序将待排记录分隔成独立的两部分，其中一部分的所有数据都比另一部分小，然后分别对这两部分继续进行排序。非递归实现的快速排序通常采用“栈”这一数据结构来模拟递归过程。

以下是一个简单的非递归快速排序算法的C语言版本：

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

// 小数组优化处理
#define IS_SMALL(arr, size) (size <= 10)

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

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 (!IS_SMALL(arr, high - low + 1)) {
        // 如果子数组大小大于阈值，使用栈保存子区间边界
        int stack[40], top = -1;
        stack[++top] = low;
        stack[++top] = high;

        while (top >= 0) {
            high = stack[top--];
            low = stack[top--];

            int pi = partition(arr, low, high);

            if (pi - 1 > low) {
                stack[top] = low;
                stack[top++] = pi - 1;
            }

            if (pi + 1 < high) {
                stack[top] = pi + 1;
                stack[top++] = high;
            }
        }
    } else {
        // 对小数组直接插入排序
        for (int i = 1; i < high - low + 1; i++) {
            int key = arr[low + i];
            int j = low - 1;

            while (j >= 0 && arr[j + 1] > key) {
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j + 1] = key;
        }
    }
}

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

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

    quickSort(arr, 0, n - 1);
    printf("Sorted array: \n");
    printArray(arr, n);

    return 0;
}

这个程序首先检查数组是否足够小，如果是，则直接使用插入排序；否则，它会使用栈来存储分割操作的范围，并反复进行分区操作直到整个数组有序。