C 语言快速排序算法详解与优化实现

三、快速排序高阶（小区间优化）

1. 优化思路

递归深度过深会消耗大量栈空间。当区间长度较小时（如小于 10），递归开销可能超过直接排序的开销。此时可切换至插入排序或堆排序处理小区间，减少递归调用次数。

2. 辅助函数

三数取中

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

分区函数

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 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];
            else
                break;
            --end;
        }
        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);
    }
}

主框架

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. 实现思路

利用栈存储待处理的区间范围 [Left, Right]。每次弹出一个区间进行分区，若子区间有效则压入栈中，直至栈空。

3. 代码实现

栈定义

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

本文涵盖了快速排序从理论到工程优化的完整路径。理解这些变式有助于在实际开发中根据数据特征选择最优策略。