C 语言快速排序详解：从基础到非递归实现

2. 小区间优化

当区间长度较小时（例如小于 10），递归开销可能超过收益。此时可切换至插入排序或堆排序，减少递归层数，提升整体效率。

// 插入排序辅助函数
void InsertSort(int* a, int n) {
    for (int i = 0; i < n - 1; i++) {
        int end = i;
        int tmp = a[end + 1];
        while (end >= 0) {
            if (tmp < a[end]) {
                a[end + 1] = a[end];
                --end;
            } else break;
        }
        a[end + 1] = tmp;
    }
}

// 堆排序辅助函数
void AdJustDown(int* a, int parent, int size) {
    int child = 2 * parent + 1;
    while (child <= size - 1) {
        if (child + 1 <= size - 1 && a[child + 1] > a[child]) child++;
        if (a[child] > a[parent]) {
            Swap(&a[child], &a[parent]);
            parent = child;
            child = 2 * parent + 1;
        } else break;
    }
}

void HeapSort(int* a, int sz) {
    int i;
    for (i = (sz - 1 - 1) / 2; i >= 0; i--) AdJustDown(a, i, sz);
    for (i = sz - 1; i > 0; i--) {
        Swap(&a[0], &a[i]);
        AdJustDown(a, 0, i);
    }
}

3. 综合框架

结合上述优化，主排序逻辑如下：

void QuickSort1(int* a, int left, int right) {
    if (left >= right) return;
    int g = right - left + 1;
    if (g < 10) {
        HeapSort(a + left, g);
    } else {
        int key = PartSort1(a, left, right);
        QuickSort1(a, left, key - 1);
        QuickSort1(a, key + 1, right);
    }
}

三、非递归实现

递归深度过大可能导致栈溢出。我们可以使用显式的栈结构来模拟递归调用过程。每次划分后，将左右区间的边界压入栈中，循环处理直到栈为空。

1. 栈结构定义

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>

typedef int STDataType;
typedef struct Stack {
    STDataType* a;
    int size;
    int capacity;
} Stack;

void StackInit(Stack* ps);
void StackPush(Stack* ps, STDataType data);
void StackPop(Stack* ps);
STDataType StackTop(Stack* ps);
int StackSize(Stack* ps);
int StackEmpty(Stack* ps);
void StackDestroy(Stack* ps);

2. 主体逻辑

void QuickSortNonR(int* a, int left, int right) {
    Stack S;
    StackInit(&S);
    StackPush(&S, right);
    StackPush(&S, left);
    while (!StackEmpty(&S)) {
        int L = StackTop(&S); StackPop(&S);
        int R = StackTop(&S); StackPop(&S);
        if (L >= R) continue;
        int g = R - L + 1;
        if (g < 10) {
            HeapSort(a + L, g);
        } else {
            int key = PartSort1(a, L, R);
            if (R - key - 1 > 1) {
                StackPush(&S, R);
                StackPush(&S, key + 1);
            }
            if (key - 1 - L > 1) {
                StackPush(&S, key - 1);
                StackPush(&S, L);
            }
        }
    }
    StackDestroy(&S);
}

四、总结

快速排序在实际应用中非常广泛。理解其分区机制及优化手段，对于掌握算法设计思想至关重要。通过上述改进，我们可以在保持平均 O(N log N) 复杂度的同时，增强算法的鲁棒性。