[数据结构]排序之 快速排序详解（递归版非递归版）

目录

一、递归版本

1. hoare版本

（一）低配版

（二）高配版

①随机选key

②三数取中法选key（在begin，end，mid三个数中选）

2. 挖坑法

3. 前后指针版本（推荐，细节容易把控）

二、非递归版本

#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int GetMidNumi(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    //求中间值
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])//此时mid最大
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else//a[left] > a[mid]
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])//此时mid最小,此时另外两个小的那个就是中间值
        {
            return a[right];
        }
        else
        {
            return a[left];
        }
    }
}
void QuickSort(int* a, int left, int right)
{
    //递归结束条件
    //当递归到begin==0，end==1，keyi==1时，区间通过[begin,kei-1] key [key+1,end]划分后
    //分为[0,0] keyi [2,1],此时会出现left>right的情况
    if (left >= right)
        return;
    int begin = left;
    int end = right;
    //三数选中
    int mini = GetMidNumi(a, left, right);
    Swap(&a[left], &a[mini]);
    
    int keyi = left;
    int prev = left;
    int cur = left + 1;
    while (cur<=right)
    {
        if (a[cur] < a[keyi] && ++prev != cur)
        {
            Swap(&a[cur], &a[prev]);
        }
        ++cur;
    }
    Swap(&a[keyi], &a[prev]);
    keyi = prev;
    //[begin,kei-1] key [key+1,end]
    //递归
    QuickSort(a, begin, keyi - 1);
    QuickSort(a, keyi + 1, end);
}
int main()
{
    int a[] = { 6,1,2,7,9,3,4,5,10,8 };
    QuickSort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
}

二、非递归版本

#define _CRT_SECURE_NO_WARNINGS 1
#include "stack.h"
void Swap(int* a, int* b)
{
    int temp = *a;
    *a = *b;
    *b = temp;
}
int GetMidNumi(int* a, int left, int right)
{
    int mid = (left + right) / 2;
    if (a[left] < a[mid])
    {
        if (a[mid] < a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return left;
        }
        else
        {
            return right;
        }
    }
    else
    {
        if (a[mid] > a[right])
        {
            return mid;
        }
        else if (a[left] > a[right])
        {
            return right;
        }
        else
        {
            return left;
        }
    }
}
void QuickSort(int* a, int left, int right)
{
    ST st;
    STInit(&st);
    STPush(&st, right);
    STPush(&st, left);
    while (!STEmpty(&st))
    {
        int begin = STTop(&st);
        STPop(&st);
        int end = STTop(&st);
        STPop(&st);
        // 三数选中
        int mini = GetMidNumi(a, begin, end);
        // 修正：将 left 改为 begin
        Swap(&a[begin], &a[mini]);
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        // 修正：将 right 改为 end
        while (cur <= end)
        {
            if (a[cur] < a[keyi] && ++prev != cur)
            {
                Swap(&a[cur], &a[prev]);
            }
            ++cur;
        }
        Swap(&a[keyi], &a[prev]);
        keyi = prev;
        if (keyi + 1 < end)
        {
            // 先入后出，先入右区间
            STPush(&st, end);
            STPush(&st, keyi + 1);
        }
        if (begin < keyi - 1)
        {
            // 先入后出，先入右区间
            STPush(&st, keyi - 1);
            STPush(&st, begin);
        }
    }
    STDestroy(&st);
}
int main()
{
    int a[] = { 6,1,2,7,9,3,4,5,10,8 };
    QuickSort(a, 0, 9);
    for (int i = 0; i < 10; i++)
    {
        printf("%d ", a[i]);
    }
    return 0;
}