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

二、快速排序（中阶）

1. 存在的问题

在刚刚快速排序的初阶代码中，我们的 key 值是固定的，始终都是数组的第一项。但这样也会出现一些小问题。

若这个数组是完全有序的，会出现什么情况呢？首先，右小人先向左走，因为数组是有序的，找不到比第一个数 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. 实现代码（中阶）

我们可以封装成一个函数来使用。

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]) // 右小人向左走，直到找到比 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. 仍存在的问题

由于我们的快速排序是由递归实现的，每递归一次就多一半的区间，最后的区间数是 2^n (n 为递归次数)。而在第倒数 1、2 个递归时，区间内只有几个数，这时候用之前的办法就效率不高，且还会多两倍的区间。所以，我们可以当区间内个数少于一定时，采用其他排序，这样就可以减少大量的递归，提高效率。

2. 优化（小区间优化）

当区间个数小于 10 时，就采用堆排序，可以有效的提高效率。

3. 实现代码（高阶）

（1）三数取中函数

// 三数取中，返回三个数的中间值
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;
    }
}

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

// 快速排序递归实现
// 快速排序 hoare 版本
int PartSort1(int* a, int left, int right)
{
    int key = FindKey(a, left, right); // 找到中间下标并给 key
    Swap(&a[key], &a[left]);
    key = left; // 将 key 位置换到首项
    
    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 和相遇点对应的值
    return right; // 返回最后 key 的下标，方便分割
}

（3）堆排序

// 插入排序
void InsertSort(int* a, int n)
{
    // [0, n-1]
    for (int i = 0; i < n - 1; i++)
    {
        // [0, n-2] 是最后一组
        // [0,end] 有序 end+1 位置的值插入 [0,end]，保持有序
        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); // 递归 key 的左区间
        QuickSort1(a, key + 1, right); // 递归 key 的右区间
    }
}

四、快速排序（非递归）

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);
// 检测栈是否为空，如果为空返回非零结果，如果不为空返回 0
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; // 全部初始化置 0 / NULL
}

// 入栈
void StackPush(Stack* ps, STDataType data)
{
    assert(ps); // 断言空指针
    if (ps->size == ps->capacity) // 当 size=capacity 时就表示空间不足，此时需要增容，故进入 if 语句
    {
        // 先设置新变量，增容后再赋值
        int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; // 设置一个三目操作符判断原空间是否为 0
        // 当原空间为 0 时给空间开辟 4 字节；当原空间不为 0 时给空间增容 2 倍
        STDataType* tmp = (STDataType*)realloc(ps->a, newcapacity * sizeof(STDataType)); // 由于是在原空间的基础上给空间增容，故我们这里使用 realloc 函数 增容
        // 增容大小为上面的 newcapacity *（类型大小）
        if (tmp == NULL) // 加一个 if 语句 防止增容失败
        {
            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--; // 将元素个数进行 -1 就行
    // 这样也不会影响到后面的 增、删、查、改
}

// 获取栈顶元素
STDataType StackTop(Stack* ps)
{
    assert(ps && ps->size > 0); // 断言空指针
    // 断言顺序表不能为空
    return ps->a[ps->size - 1];
}

// 获取栈中有效元素个数
int StackSize(Stack* ps)
{
    assert(ps); // 断言空指针
    return ps->size;
}

// 检测栈是否为空，如果为空返回非零结果，如果不为空返回 0
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; // 全部初始化置 0 / NULL
}

（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)
            return;
        
        // 小区间优化
        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);
}