史上最细快速排序讲解（Hoare，挖坑，双指针，非递归）

创作时间:

作者:

@小白创作中心

史上最细快速排序讲解（Hoare，挖坑，双指针，非递归）

引用

CSDN

https://blog.csdn.net/Jdxxwu/article/details/142604921

快速排序是一种高效的排序算法，由C. A. R. Hoare在1962年提出。它采用分治策略，通过一趟排序将待排序的数据分割成独立的两部分，其中一部分的所有数据都比另一部分的所有数据小，然后分别对这两部分数据继续进行排序，以此达到整个数据变成有序序列的目的。本文将详细介绍快速排序的各种实现方法，包括递归方法、Hoare方法、挖坑方法、双指针方法以及非递归方法。

一、递归方法快速排序

1. 递归主要思想

快速排序的基本思想是：任选一个元素作为基准值，将待排序序列分割成两个子序列，其中左子序列的所有元素都小于基准值，右子序列的所有元素都大于基准值，然后递归地对这两个子序列进行快速排序。

快速排序的过程可以看作是构建一棵二叉树，每个节点的左右子树分别对应小于和大于基准值的子序列。递归的终止条件是子序列长度为1或0。

2. 递归代码实现

假设有一个函数int _QuickSort(int* arr, int left, int right)，其功能是返回数组arr中左边界left和右边界right的基准值位置。我们可以用这个函数模拟前序遍历的方式遍历数组。

//快速排序
void QuickSort(int* arr, int left, int right)
{
    if (left >= right)
    {
        return;
    }
    int keyi = _QuickSort(arr, left, right);
    //遍历它的左子树
    QuickSort(arr, left, keyi - 1);
    //遍历它的右子树
    QuickSort(arr, keyi + 1, right);
}

二、Hoare方法实现找基准值

1. Hoare思想

Hoare方法通过两个指针left和right从两端向中间扫描，left从左向右找大于基准值的位置，right从右向左找小于基准值的位置，找到后交换这两个位置的值。当left和right相遇时，将基准值与相遇位置的值交换，完成一次划分。

2. Hoare代码实现

//找基准值
int _QuickSort(int* arr, int left, int right)
{
    int keyi = left;
    left++;
    while (left <= right)
    {
        while (left <= right && arr[right] > arr[keyi])
        {
            right--;
        }
        while (left <= right && arr[left] < arr[keyi])
        {
            left++;
        }
        if (left <= right)
        {
            Swap(&arr[left++], &arr[right--]);
        }
    }
    Swap(&arr[keyi], &arr[right]);
    return right;
}

三、挖坑方法实现找基准值

1. 挖坑思想

挖坑方法通过创建一个"坑"，初始位置为left。right从右向左找小于基准值的元素填入"坑"中，然后更新"坑"的位置为right；left从左向右找大于基准值的元素填入"坑"中，然后更新"坑"的位置为left。重复此过程直到left不再小于right，最后将基准值填入"坑"中。

2. 挖坑代码实现

//挖坑法
int _QuickSort2(int* arr, int left, int right)
{
    int key = arr[left];
    int hole = left;
    while (left < right)
    {
        while (left < right && arr[right] > key)
        {
            right--;
        }
        if (left < right)
        {
            arr[hole] = arr[right];
            hole = right;
        }
        while (left < right && arr[left] < key)
        {
            left++;
        }
        if (left < right)
        {
            arr[hole] = arr[left];
            hole = left;
        }
    }
    arr[hole] = key;
    return hole;
}

四、双指针方法实现找基准值

1. Lomuto前后指针法思想

Lomuto方法使用两个指针prev和cur，从左向右扫描数组。cur从左向右找小于基准值的元素，找到后与prev位置的元素交换，然后prev右移一位。重复此过程直到cur超过右边界，最后将基准值与prev位置的元素交换。

2. Lomuto前后指针法代码实现

//lomuto前后指针法
int _QuickSort3(int* arr, int left, int right)
{
    int keyi = left;
    int prev = left, cur = left + 1;
    while (cur <= right)
    {
        if (arr[cur] < arr[keyi] && ++prev != cur)
        {
            Swap(&arr[cur], &arr[prev]);
        }
        cur++;
    }
    Swap(&arr[keyi], &arr[prev]);
    return prev;
}

五、非递归方法快速排序

1. 非递归主要思想

非递归版本的快速排序使用栈来存储未处理的子数组边界。每次分区后，将左、右子数组的边界压入栈中，继续处理子数组，直到栈为空。

2. 非递归代码实现

//使用遍历的方法
void QuickSortNonR(int* arr, int left, int right)
{
    ST st;
    STInit(&st);
    StackPush(&st, right);
    StackPush(&st, left);
    while (!StackEmpty(&st))
    {
        int begin = StackTop(&st);
        StackPop(&st);
        int end = StackTop(&st);
        StackPop(&st);
        int keyi = begin;
        int prev = begin;
        int cur = begin + 1;
        while (cur <= end)
        {
            if (arr[cur] < arr[keyi] && ++prev != cur)
            {
                Swap(&arr[prev], &arr[cur]);
            }
            cur++;
        }
        Swap(&arr[keyi], &arr[prev]);
        keyi = prev;
        if (keyi + 1 < end)
        {
            StackPush(&st, end);
            StackPush(&st, keyi + 1);
        }
        if (keyi - 1 > begin)
        {
            StackPush(&st, keyi - 1);
            StackPush(&st, begin);
        }
    }
    STDestroy(&st);
}