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

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

引用

CSDN

1.

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

快速排序是一种高效的排序算法，由C. A. R. Hoare在1962年提出。它采用分治策略来把一个序列分为较小和较大的两个子序列，然后递归地排序两个子序列。本文将详细讲解快速排序的各种实现方法，包括递归方法、Hoare方法、挖坑方法、双指针方法以及非递归方法。

一、递归方法快速排序

1. 递归主要思想

快速排序的基本思想是：任选待排序序列中的某元素作为基准值，按照该基准值将待排序集合分割成两个子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后对左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

快速排序的思想可以概括为：

1. 选择一个基准值，使得基准值左侧的所有数据全都小于基准值，基准值右侧的所有数据全都大于基准值。
2. 对基准值左侧和右侧的子序列递归地应用相同的过程。
3. 当子序列长度为1或0时，排序完成。

2. 递归代码实现

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

基准值的左子树就是 [left, keyi-1]，右子树就是 [keyi+1, right]。递归的结束条件是 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方法通过两个指针从两端向中间扫描，寻找合适的基准值位置。具体步骤如下：

1. 将第一个元素定位为基准值，left 为第二个元素，right 为最后一个元素。
2. right 从右向左找小于基准值的位置，left 从左向右找大于基准值的位置。
3. 交换 arr[left] 与 arr[right]。
4. 交换过后 left++，right--。
5. 当 left 与 right 相等时还需要继续循环，为了二分左右子树。
6. 将 keyi 位置的值与 right 位置的值进行交换，此时 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. 挖坑思想

挖坑方法通过创建左右指针，从右向左找出比基准小的数据，从左向右找出比基准大的数据，最终将基准值放入正确的位置。具体步骤如下：

1. 定义一个坑（hole），让它等于 left。
2. 假设 key 保存数组最左边的数据，记作基准值。
3. 让 right 从右往左找小，如果小于基准值，就用这个值来填坑，再让 right 位置变为新的坑。
4. 让 left 从左往右找大，如果大于基准值，就用这个值来填坑，再让 left 位置变为新的坑。
5. 重复上述步骤直到 left 不再小于 right。
6. 最后，让最开始保存的 key 填坑，返回 hole 就是基准值。

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前后指针法通过创建前后指针，从左往右找比基准值小的进行交换，使得小的都排在基准值的左边。具体步骤如下：

1. 定义 keyi 保存基准值下标，定义 prev = left，cur = left + 1。
2. cur 从左往右找小，如果找到比基准值小的数组，就让 prev++，并交换 prev 和 cur 中的数据。
3. 注意：如果此时 ++prev 后与 cur 重合就不交换了。
4. 直到 cur > right 结束循环，此时交换 key 与 prev 中元素，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);
}

总结

快速排序算法的时间复杂度通常为 O(n log n)，空间复杂度为 O(log n)。通过本文的详细讲解和代码实现，读者可以全面掌握快速排序的各种实现方法，从而更好地理解和应用这一重要的排序算法。