分区快速排序逻辑错误

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);
}

这是我的快速排序函数，其中包含一个用于交换的分区和 return 枢轴，以便快速排序使用不同的中点重新调用自身。我不太熟悉快速排序，但这是我想出的。

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

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

Answer 1

您似乎返回的是主元的值，而不是它在分区函数中的位置。

Answer 2

这是一个使用分区索引的实现：

void swap(int A[], int i1, int i2){
    int temp=A[i1];
    A[i1]=A[i2];
    A[i2]=temp;
}

int partition(int A[], int low, int high){
    int partitionIndex, i, pivot;

    pivot = A[high];
    partitionIndex=low;

    for(i=low; i < high; i++){
        if(A[i]<=pivot){
            swap(A,i,partitionIndex);
            partitionIndex++;
        }
    }
    swap(A,high,partitionIndex);
    return partitionIndex;
}

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

我无法弄清楚您的代码有什么问题。在调试过程中，我注意到您编辑了问题中的代码。希望上面的代码可以帮助您解决问题的根源。

Answer 3

你的分区函数不正确。在快速排序期间有两种主要的分割序列的方法：squeeze 和 sweep。前者是您正在尝试的方法，并且以更复杂的算法为代价，与后一种方法相比，交换次数极有可能更少。

横扫

我将首先向您展示更简单的 sweep 方法，因为它确实最容易理解。通常，该算法执行以下操作：

如果序列长度小于二，则提前退出。对于长度为一的序列，没有什么可划分的。
在序列中选择一个枢轴值。选择一个减少 O(N^2) 退化条件几率的枢轴值是快速排序分区的圣杯，我不会在这里介绍它，但有很多在线提供关于该主题的令状。
将主元值与序列中的最后一个值交换。
用两个索引值遍历序列； reader 索引和作者索引。当您向上移动序列时，任何 reader 索引值 "less than" 枢轴值被交换到 writer-index 的较低序列，并且 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;
}

请注意，完全可以想象大于的值可能会被交换 multiple 次，因为下分区在行进。最终一切都解决了，但最好避免这些额外的掉期。这就是 squeeze 方法的目的，如下所示。

挤压

虽然 sweep 有其优点（最显着的是简单性），但最小化交换不在其中。理想情况下，只有在确定 two 值在枢轴值最终着陆点的相对两侧不合适时才执行交换。为此，您需要执行从低到高的扫描同时和从高到低的扫描，一旦每个元素在错误的位置找到一个元素，交换那些。最终低指数和高指数相遇，这样你就找到了枢轴最后的归宿。

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;
}

这里发生了几件看起来很奇怪的事情。请注意减少 high 的 second 内部 while 循环的布尔逻辑。我本可以写 (A[high] >= A[len-1]) 但我想把一个常见的错误带回家。临界减少 high 逻辑上逆向的条件 =17=]。如果 low 被提升是因为它的元素严格小于我们这里的主元值，那么 high 只有当它的元素是 而不是 时才能减少（严格小于枢轴值）。毫无疑问，当我们按照上面的编码显示时，我们是正确的，我无法公正地描述特定要求被掩盖并导致神秘破坏的分区算法的次数。

使用快速排序的样本分区

以上任何一个都可以。对函数进行一些细微的修改以在交换发生时产生输出并对随机打乱的值数组进行排序表明交换计数减少。下面在两个分区函数中实现这两种算法，适当地标记为 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

祝你好运。

分区快速排序逻辑错误

Partition in quick sort logical error

c++

sorting

logic

quicksort