c++ - 划分快速排序逻辑错误

Question

int partition(int A[], int low, int high){
    int mid = (low+high)/2;
    int pivot = A[mid];
    while(low <= high) {
        while(low <= high && A[high] >= pivot) {
            high--;
        }
        while (low <= high && A[low] <= pivot) {
            low ++;
        }
        if(low <= high) {
            int tmp = A[low];
            A[low] = A[high]; 
            A[high] = tmp;
            high--;
           low++;
        }
    }
    return mid;
}

void quickSort(int A[], int low, int high) {
    if (low >= high) {
      return;
    }
    int ppos = partition(A, low, high);//does the swapping and returns the pivot
    quickSort(A, low, ppos-1);
    quickSort(A, ppos+1, high);
}

这是我的quicksort函数，带有一个分区来进行交换并返回数据透视表，以便quicksort用不同的中点调用自身。我对quicksort不太熟悉，但这就是我想出的。

问题是它可以很好地编译，但是在运行时总是崩溃。我的功能存在逻辑缺陷吗？关于如何修复我的函数，以便对随机数组进行快速排序的任何建议？

-编辑-
修复了崩溃错误，但分区无法正确进行排序，是否有任何建议更改功能，以便它可以对数组进行快速排序？

Answer 1

您的分区功能不正确。在快速排序过程中，有两种主要方法可用于划分序列:挤压和扫描。前者是您要尝试的一种，与后者的交换相比，交换可能性更高，但代价是算法更加复杂。

扫频

首先，我将向您展示更简单的扫描方法，因为这是最简单易懂的方法。通常，该算法执行以下操作:

如果序列长度小于2，则提早退出。长度为1的序列没有分区。

在序列中选择一个枢轴值。选择一个减少O(N ^ 2)退化条件机会的枢轴值是快速排序分区的主要目标，在此不做介绍，但是在线上有很多有关此主题的命令。

将枢轴值与序列中的最后一个值交换。

使用两个索引值遍历序列；读者索引和作者索引。在按顺序排列时，将“小于”枢轴值的任何阅读器索引值交换为在书写器索引处的较低序列，并增加书写器索引。

完成后，writer索引是将枢轴值交换到最终位置且分区完成的点。返回的结果分区点是作者索引位置。

使用代码实际上更容易理解该算法:

size_t partition(int A[], size_t len)
{
    if (len < 2) // 1.
        return 0;

    std::iter_swap(A+len/2, A+len-1); // 2. 3.
    size_t pvt = 0;

    for (size_t i=0; i<len-1; ++i) // 4.
    {
        if (A[i] < A[len-1])
            std::iter_swap(A + pvt++, A+i);
    }
    std::iter_swap(A + pvt, A+len-1); // 5.

    return pvt;
}

请注意，在行进期间填充下部分区时，完全可以想象到大于枢轴值的值可能会多次交换。最终，一切都解决了，但是理想情况下避免了这些额外的交换。这就是挤压方法的目的，如下所示。

挤压

尽管清除具有其优点(最显着的优点是简单性)，但最大程度地减少交换并不是其中之一。理想情况下，只有在确定两个值在最终枢轴值的着陆点的相对侧都不正确时，才执行交换。为此，您需要同时执行从低到高的扫描和从高到低的扫描，并且一旦每个人在错误的位置找到一个元素，就交换它们。最终，低索引和高索引相遇，并在此之后找到了关键的最终休息点。

size_t partition(int A[], size_t len)
{
    if (len < 2)
        return 0;

    std::iter_swap(A + len/2, A+len-1);
    size_t low = 0, high = len;

    while (1)
    {
        while (low < high && (A[low] < A[len-1]))
            ++low;

        if (low == high--)
            break;

        while (low < high && !(A[high] < A[len-1]))
            --high;

        if (low == high)
            break;

        std::iter_swap(A+low++, A+high);
    }
    std::iter_swap(A+low, A+len-1);

    return low;
}

这里发生了几件事，可能看起来很奇怪。注意第二个内部while循环的 bool(boolean) 逻辑，该逻辑减少了 high。我本可以写 (A[high] >= A[len-1])，但我想开车回家是一个常见的错误。 临界降低 high的条件与提升 low的条件在逻辑上相反。如果 low因其元素严格小于我们在此处的枢轴值而得到提升，则只有在其元素为 而不是(严格小于枢轴值)的情况下，才能减少 high。毫无疑问，如上所示，当我们将其正确显示时，我根本无法公正地满足那些满足特定要求并导致神秘破坏的分区算法的次数。

使用QuickSort的示例分区

以上任何一种都可以。对发生交换时产生输出的函数进行了一些细微修改，并对随机混排的值数组进行排序证明了交换计数的减少。下面的代码在两个分区函数中实现了这两种算法，分别标记为 sweep和 squeeze。它们都在相同的随机序列上变松，然后在完全排序的序列上变松，以显示交换计数差异。

#include <iostream>
#include <algorithm>
#include <random>
#include <numeric>

size_t sweep(int A[], size_t len)
{
    if (len < 2)
        return 0;

    std::iter_swap(A+len/2, A+len-1);
    size_t pvt = 0;

    for (size_t i=0; i<len-1; ++i)
    {
        if (A[i] < A[len-1])
        {
            std::cout << "swap: " << A[pvt] << ',' << A[i] << '\n';
            std::iter_swap(A + pvt++, A+i);
        }
    }
    std::iter_swap(A + pvt, A+len-1);

    return pvt;
}

size_t squeeze(int A[], size_t len)
{
    if (len <= 1)
        return 0;

    std::iter_swap(A + len/2, A+len-1);
    size_t low = 0, high = len;

    while (1)
    {
        while (low < high && A[low] < A[len-1])
            ++low;

        if (low == high--)
            break;

        while (low < high && !(A[high] < A[len-1]))
            --high;

        if (low == high)
            break;

        std::cout << "swap: " << A[low] << ',' << A[high] << '\n';
        std::iter_swap(A+low++, A+high);
    }
    std::iter_swap(A+low, A+len-1);

    return low;
}

void quicksort(int A[], size_t len, size_t (*part)(int[], size_t))
{
    if (len < 2)
        return;

    size_t pvt = part(A, len);
    quicksort(A, pvt++, part);
    quicksort(A+pvt, len-pvt, part);
}

int main()
{
    std::random_device rd;
    std::mt19937 rng(rd());

    int ar[31] = {0}, ar2[31];
    std::iota(std::begin(ar), std::end(ar), 1);
    std::shuffle(std::begin(ar), std::end(ar), rng);
    std::copy(std::begin(ar), std::end(ar), std::begin(ar2));

    for (auto x : ar)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Sweep Algorithm\n";
    quicksort(ar, sizeof(ar)/sizeof(*ar), sweep);

    for (auto x : ar)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Squeeze Algorithm\n";
    quicksort(ar2, sizeof(ar2)/sizeof(*ar2), squeeze);

    for (auto x : ar2)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Sweep Algorithm (sorted)\n";
    quicksort(ar, sizeof(ar)/sizeof(*ar), sweep);

    for (auto x : ar)
        std::cout << x << ' ';
    std::cout << '\n';

    std::cout << "Squeeze Algorithm (sorted)\n";
    quicksort(ar2, sizeof(ar2)/sizeof(*ar2), squeeze);

    for (auto x : ar2)
        std::cout << x << ' ';
    std::cout << '\n';
}

输出(随机)

8 28 21 26 10 12 17 1 11 20 30 3 18 5 24 15 9 6 13 27 31 4 16 7 19 22 14 25 29 2 23 
Sweep Algorithm
swap: 8,8
swap: 28,10
swap: 21,12
swap: 26,1
swap: 28,11
swap: 21,3
swap: 17,5
swap: 26,9
swap: 28,6
swap: 20,13
swap: 30,4
swap: 21,7
swap: 18,14
swap: 17,2
swap: 8,8
swap: 10,1
swap: 12,3
swap: 10,5
swap: 11,2
swap: 12,6
swap: 10,4
swap: 11,7
swap: 8,1
swap: 3,3
swap: 5,5
swap: 7,4
swap: 3,3
swap: 4,4
swap: 3,3
swap: 7,7
swap: 13,10
swap: 12,12
swap: 13,13
swap: 12,12
swap: 23,20
swap: 26,16
swap: 28,19
swap: 23,18
swap: 27,17
swap: 20,16
swap: 20,17
swap: 20,18
swap: 16,16
swap: 30,22
swap: 24,24
swap: 30,26
swap: 31,28
swap: 30,27
swap: 26,26
swap: 27,27
swap: 26,26
swap: 30,30
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
Squeeze Algorithm
swap: 28,2
swap: 21,14
swap: 26,7
swap: 17,4
swap: 20,13
swap: 30,6
swap: 18,9
swap: 14,3
swap: 7,4
swap: 14,9
swap: 12,6
swap: 30,25
swap: 27,21
swap: 31,22
swap: 23,16
swap: 25,17
swap: 30,28
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
Sweep Algorithm (sorted)
swap: 1,1
swap: 2,2
swap: 3,3
swap: 4,4
swap: 5,5
swap: 6,6
swap: 7,7
swap: 8,8
swap: 9,9
swap: 10,10
swap: 11,11
swap: 12,12
swap: 13,13
swap: 14,14
swap: 15,15
swap: 1,1
swap: 2,2
swap: 3,3
swap: 4,4
swap: 5,5
swap: 6,6
swap: 7,7
swap: 1,1
swap: 2,2
swap: 3,3
swap: 1,1
swap: 5,5
swap: 9,9
swap: 10,10
swap: 11,11
swap: 9,9
swap: 13,13
swap: 17,17
swap: 18,18
swap: 19,19
swap: 20,20
swap: 21,21
swap: 22,22
swap: 23,23
swap: 17,17
swap: 18,18
swap: 19,19
swap: 17,17
swap: 21,21
swap: 25,25
swap: 26,26
swap: 27,27
swap: 25,25
swap: 29,29
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 
Squeeze Algorithm (sorted)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 

祝你好运。