C 语言快速排序详解与优化实践

1. 三数取中法

如果数组本身有序或接近有序，固定选取首元素作为 key 会导致时间复杂度退化为 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;
    }
}

在调用快排前，先通过 FindKey 找到中位数下标，并将其与首元素交换，确保 key 位于首位，随后逻辑同基础版。

2. 小区间优化

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

通常设定阈值（如 10），当区间长度小于该值时，直接调用插入排序或堆排序处理。

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. 辅助结构：栈

我们需要一个简单的栈来管理区间范围。

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

3. 主体逻辑

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

通过上述优化与非递归改造，快速排序在实际工程应用中更加稳健高效。理解这些细节有助于在面对不同数据特征时做出合适的选择。