快速排序算法详解：Hoare法、挖坑法、前后指针法及非递归实现

快速排序算法详解：Hoare法、挖坑法、前后指针法及非递归实现

引用

CSDN

1.

https://m.blog.csdn.net/weixin_64099089/article/details/137792497

**快速排序是一种非常高效的排序算法，由C. A. R. Hoare在1960年提出。它采用分治法策略，通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。本文将详细介绍快速排序的多种实现方式，包括Hoare法、挖坑法、前后指针法以及非递归实现（栈和队列）。

1. Hoare法

快速排序的核心思想是选择一个基准元素（通常选择序列的第一个元素），通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

单趟排序步骤：

1. 选定一个基准元素（key），初始化左右指针L和R
2. R从右向左查找比key小的元素
3. L从左向右查找比key大的元素
4. 交换L和R位置的元素
5. 重复步骤2-4，直到L和R相遇
6. 最后将基准元素与相遇位置的元素交换

单趟排序的意义：

1. 基准元素被放置到正确的位置
2. 将序列分割成两个子区间，左侧元素都小于基准元素，右侧元素都大于基准元素

单趟排序实现：

void PartSort(int* a, int begin, int end) {
    if (begin >= end)
        return;
    int keyi = begin;
    int key = a[keyi];
    int Left = begin;
    int Right = end;
    while (Left < Right) {
        while (Left < Right && a[Right] >= key)
            Right--;
        while (Left < Right && a[Left] <= key)
            Left++;
        Swap(&a[Left], &a[Right]);
    }
    Swap(&a[keyi], &a[Left]);
}

快速排序递归实现：

void QuickSort(int *a, int begin, int end) {
    assert(a);
    if (begin >= end)
        return;
    int meet = PartSort(a, begin, end);
    QuickSort(a, begin, meet - 1);
    QuickSort(a, meet + 1, end);
}

2. 挖坑法

挖坑法是快速排序的另一种实现方式，其核心思想是通过"挖坑填数"的方式进行元素交换，可以减少代码中的边界条件判断，使代码更加简洁。

单趟排序步骤：

1. 选择一个基准元素（key），将其位置设为"坑"
2. R从右向左查找比key小的元素，找到后填入"坑"中，当前位置变成新的"坑"
3. L从左向右查找比key大的元素，找到后填入"坑"中，当前位置变成新的"坑"
4. 重复步骤2-3，直到L和R相遇
5. 最后将基准元素填入相遇位置的"坑"中

单趟排序实现：

int QuickPastSort2(int* a, int begin, int end) {
    assert(a);
    int keyi = GetMidIndex(a, begin, end);
    int key = a[keyi];
    Swap(&a[keyi], &a[begin]);
    keyi = begin;
    int hole = begin;
    int left = begin;
    int right = end;
    while (left < right) {
        while (left < right && a[right] >= key)
            right--;
        a[hole] = a[right];
        hole = right;
        while (left < right && a[left] <= key)
            left++;
        a[hole] = a[left];
        hole = left;
    }
    a[hole] = key;
    return hole;
}

3. 前后指针法

前后指针法是快速排序的另一种实现方式，其核心思想是使用两个指针（prev和cur）进行元素交换，可以进一步简化代码逻辑。

单趟排序步骤：

1. 初始化prev指向基准元素，cur指向基准元素的下一个位置
2. prev和cur同时向前移动，直到prev的下一个位置是比基准元素大的数
3. prev停在比基准元素大的数前面，cur继续向后查找比基准元素小的数
4. cur找到比基准元素小的值后，prev先++，然后prev和cur位置的数交换
5. 最后cur越界时，key与prev指向的位置交换

单趟排序实现：

int QuickPartSort3(int* a, int begin, int end) {
    assert(a);
    int keyi = GetMidIndex(a, begin, end);
    Swap(&a[keyi], &a[begin]);
    int key = a[begin];
    keyi = begin;
    int prev = begin;
    int cur = begin + 1;
    while (cur <= end) {
        if (a[cur] < key && ++prev != cur)
            Swap(&a[cur], &a[prev]);
        cur++;
    }
    Swap(&a[begin], &a[prev]);
    return prev;
}

4. 快排的非递归实现

快速排序的递归实现可能会导致栈溢出问题，特别是在数据量较大时。因此，可以使用栈或队列来实现非递归版本的快速排序。

4.1 栈实现快排非递归

使用栈实现非递归快速排序时，可以按照前序遍历的顺序，先处理左子区间，再处理右子区间。

void StackQuickSort(int* a, int n) {
    assert(a);
    ST st;
    STInit(&st);
    StackPush(&st, n - 1);
    StackPush(&st, 0);
    while (!StackEmpty(&st)) {
        int begin = StackTop(&st);
        StackPop(&st);
        int end = StackTop(&st);
        StackPop(&st);
        if (begin >= end)
            continue;
        int meet = QuickPastSort1(a, begin, end);
        StackPush(&st, end);
        StackPush(&st, meet + 1);
        StackPush(&st, meet - 1);
        StackPush(&st, begin);
    }
    STDestroy(&st);
}

4.2 队列实现快排非递归

使用队列实现非递归快速排序时，可以按照层序遍历的顺序，依次处理每个子区间。

void QueueQuickSort(int* a, int n) {
    assert(a);
    Queue q;
    QueueInit(&q);
    QueuePush(&q, 0);
    QueuePush(&q, n - 1);
    while (!QueueEmpty(&q)) {
        int begin = QueueFront(&q);
        QueuePop(&q);
        int end = QueueFront(&q);
        QueuePop(&q);
        if (begin >= end)
            continue;
        int meet = QuickPastSort1(a, begin, end);
        QueuePush(&q, begin);
        QueuePush(&q, meet - 1);
        QueuePush(&q, meet + 1);
        QueuePush(&q, end);
    }
    QueueDestroy(&q);
}

使用栈和队列实现非递归快速排序时，空间复杂度为O(1)，但在实际应用中，递归实现更为简洁和方便。