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

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

快速排序是 C 标准库中内置的高效排序算法，其核心在于分治思想与基准值选取。本文详细拆解了 Hoare 分区方案的实现逻辑，通过双指针扫描完成区间划分。针对极端数据场景，阐述了三数取中法如何规避最坏时间复杂度，以及小区间内采用堆排序替代递归的优化策略。此外，还展示了利用显式栈模拟递归调用的非递归实现，有效防止深层递归引发的栈溢出问题。

一、快速排序（初阶）

1. 算法思想

快速排序有一个 key 值，称为基准元素。在第一次快速排序结束后，这个 key 的位置会发生改变，其他元素位置也会相应调整。最终，在 key 的左边都是小于 key 的数，右边都是大于 key 的数。此时 key 的顺序就被排好了，后续不需要再动。

接着将整个数组以 key 分成左右两个区间，并在这两个区间循环执行上述步骤。直到区间不可再分（区间只剩一个元素），排序结束。

简单来说，快速排序就是不断将比 key 小的数放左边，把比 key 大的数放右边，最后完成排序。

2. 实现思路

（1）定 key 值

第一步确定 key 值，通常理解为第一个数字（后续会改进）。后续的排序围绕这个基准元素进行。

（2）大小交换

使用两个指针，一个从左往右走，一个从右往左走。

• 右指针向左走，直到遇到比 key 小的数停下。
• 左指针向右走，直到遇到比 key 大的数停下。
• 两指针停下后，交换对应的值，大的换到右边，小的换到左边。

（3）循环

两指针继续移动，满足条件时继续交换，直到相遇，循环停止。

（4）交换 key

将 key 与两指针相遇点的值进行交换。此时 key 左边都小于它，右边都大于它，第一轮快速排序结束。

（5）分割区间

将 key 左右的区间分割开来，分别对这两个区间重复第一轮的排序步骤。

（6）结束

当每个区间分割成只剩下一个元素时，跳出循环。所有区间处理完毕，排序完成。

3. 实现代码

void QuickSort1(int* a, int left, int right) {
    if (left >= right) // 判断是否继续，当区间只有一个数时跳出循环
        return;
    
    int key = left; // 确定 key 的值，为第一个元素
    int L = left;
    int R = right; // 先将左右的下标记录下来，以免后面丢失
    
    while (left < right) { // 当左右小人相遇时就停止循环
        while (left < right && a[right] >= a[key]) // 右小人向左走，直到找到比 key 小的值
            right--;
        while (left < right && a[left] <= a[key]) // 左小人向右走，直到找到比 key 大的值
            left++;
        Swap(&a[left], &a[right]); // 交换大的值和小的值
    }
    Swap(&a[right], &a[key]); // 最后交换 key 和相遇点对应的值
    key = right; // key 的下标也要改变
    
    QuickSort1(a, L, key - 1); // 递归 key 的左区间
    QuickSort1(a, key + 1, R); // 递归 key 的右区间
}

二、快速排序（中阶）

1. 存在的问题

在初阶代码中，key 值固定为数组的第一项。如果数组是完全有序的，会出现性能问题。

若数组有序，右指针向左走找不到比 key 小的值，会一直走到 key 处，导致左右指针相遇。分割后 key 单独一个区间，右边所有数一个区间。每次循环只排好一个数，时间复杂度退化为 O(N^2)。

因此，当数组顺序有序或几乎有序时，key 容易取到极值，算法变慢。

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

3. 实现代码（中阶）

封装成函数使用，先调用 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);
}

三、快速排序（高阶）

1. 仍存在的问题

由于快速排序由递归实现，每递归一次就多一半的区间。在倒数第 1、2 层递归时，区间内只有几个数，之前的办法效率不高且增加了递归开销。

2. 优化（小区间优化）

当区间个数小于一定阈值（如 10）时，采用插入排序或堆排序，可以减少大量递归，提高效率。

3. 实现代码（高阶）

包含堆排序辅助逻辑。

（1）三数取中函数

见上文 FindKey。

（2）主要的快速排序代码

将分区逻辑封装为 PartSort1。

// 快速排序 hoare 版本
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; // 返回最后 key 的下标，方便分割
}

（3）堆排序

用于小区间优化。

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

（4）快速排序的框架

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. 实现代码

（1）栈的实现（Stack.h）

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

（2）栈的实现（Stack.c）

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

---

以上便是快速排序从基础到高阶再到非递归实现的完整解析。实际开发中，根据数据规模选择合适的优化策略至关重要。