C 语言快速排序详解与多种优化变式

二、快速排序中阶优化

存在的问题

在初阶实现中，key 值固定为数组首项。如果数组本身已经有序或接近有序，每次划分都会极不平衡（一边为空，另一边包含 N-1 个元素），导致时间复杂度退化为 O(N^2)。

优化方案：三数取中

为了避免取到极值，我们可以采用'三数取中'法。即取数组的开头、中间、结尾三个数，将大小居中的那个数定为 key。这样能一定程度上避免最坏情况的发生。

辅助函数

// 三数取中，返回三个数的中间值下标
int FindKey(int* a, int left, int right) {
    int mid = (left + right) / 2;
    if (a[left] > a[right]) {
        if (a[right] > a[mid]) {
            return right;
        } else if (a[mid] > a[left]) {
            return left;
        } else {
            return mid;
        }
    } else {
        if (a[left] > a[mid]) {
            return left;
        } else if (a[mid] > a[right]) {
            return right;
        } else {
            return mid;
        }
    }
}

主函数调整

在调用 QuickSort1 前，先调用 FindKey 获取索引并交换到首位。

void QuickSort1(int* a, int left, int right) {
    if (left >= right) {
        return;
    }
    
    int L = left;
    int R = right;
    int key = FindKey(a, left, right);
    Swap(&a[key], &a[left]);
    key = left;
    
    while (left < right) {
        while (left < right && a[right] >= a[key]) {
            right--;
        }
        while (left < right && a[left] <= a[key]) {
            left++;
        }
        Swap(&a[left], &a[right]);
    }
    
    Swap(&a[right], &a[key]);
    key = right;
    
    QuickSort1(a, L, key - 1);
    QuickSort1(a, key + 1, R);
}

三、快速排序高阶优化

小区间优化

由于快速排序是递归实现的，当区间长度较小时，递归调用的开销可能超过排序本身的收益。此时，可以使用插入排序或堆排序来处理小区间，以减少递归深度。

完整框架

这里展示一个结合了堆排序处理小区间的完整框架。

// 插入排序辅助函数
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);
    }
}

// 分区函数
int PartSort1(int* a, int left, int right) {
    int key = FindKey(a, left, right);
    Swap(&a[key], &a[left]);
    key = left;
    
    while (left < right) {
        while (left < right && a[right] >= a[key]) {
            right--;
        }
        while (left < right && a[left] <= a[key]) {
            left++;
        }
        Swap(&a[left], &a[right]);
    }
    Swap(&a[right], &a[key]);
    return right;
}

// 最终快速排序入口
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. 创建一个栈，存储待排序区间的左右边界。
2. 初始时将整个数组的左右边界入栈。
3. 循环检查栈是否为空：
   • 弹出栈顶的两个元素作为当前区间 [L, R]。
   • 对该区间进行分区，得到 key 的位置。
   • 如果左区间有效，将其边界入栈。
   • 如果右区间有效，将其边界入栈。

栈结构定义

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#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);

栈实现主体

#include "Stack.h"

void StackInit(Stack* ps) {
    assert(ps);
    ps->a = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

void StackPush(Stack* ps, STDataType data) {
    assert(ps);
    if (ps->size == ps->capacity) {
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity;
        STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType));
        if (tmp == NULL) {
            perror("realloc");
            return;
        }
        ps->a = tmp;
        ps->capacity = newcapacity;
    }
    ps->a[ps->size] = data;
    ps->size++;
}

void StackPop(Stack* ps) {
    assert(ps && ps->size > 0);
    ps->size--;
}

STDataType StackTop(Stack* ps) {
    assert(ps && ps->size > 0);
    return ps->a[ps->size - 1];
}

int StackSize(Stack* ps) {
    assert(ps);
    return ps->size;
}

int StackEmpty(Stack* ps) {
    assert(ps);
    return ps->size == 0;
}

void StackDestroy(Stack* ps) {
    assert(ps);
    free(ps->a);
    ps->a = NULL;
    ps->capacity = 0;
    ps->size = 0;
}

非递归排序主体

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);
}

以上便是快速排序从基础到高阶的完整实现与分析。在实际工程中，根据数据规模选择合适的优化策略至关重要。