C++ QuickSort算法不断崩溃

Question

尝试实现快速排序算法。我认为问题出在递归上，但我不知道该如何解决。程序每次运行都会崩溃，我不明白为什么。这是代码:

#include<iostream>

using namespace std;
int pIndex;

int Partition(int *A,int start,int end){

int pivot;
int pIndex;
 if(start<end){
    int pivot=A[end];
    int pIndex=start;
    for(int x=0;x<end;x++){
        if(A[x]<A[end]){
            swap(A[x],A[pIndex]);
             pIndex=pIndex+1;   
        }   
    }
    swap(A[pIndex],A[end]);
 }
//cout<<pIndex<<endl;
swap(A[pIndex],A[end]);
return pIndex;
};
void QuickSort(int *A, int start,int end){
    if(start<end)
    {

    pIndex=Partition(A,start,end);
    QuickSort(A,pIndex+1,end);
    QuickSort(A,start,pIndex-1);
}
};
int main(){

int A[10]{4,23,1,43,2,10};  
//Partition(A,0,9);
QuickSort(A,0,5);
for(int x=0;x<10;x++){
    cout<< A[x]<<" ";
}
}

Answer 1

您的分区算法的代码量大约是所需代码量的两倍。您似乎总是选择序列中的最后一个 元素作为您的主元，虽然不可取，但它可以用于学术演示。

你的崩溃

您正在定义两个 pIndex 值，其中只有一个是确定性的。您还声明了两个 pivot 变量，但这不会导致您的崩溃(第一个从未使用过)。尽管如此，它应该被清理干净，但是你代码中的丧钟是重复的 pIndex

int pivot;
int pIndex;     // HERE
if(start<end){
    int pivot=A[end];
    int pIndex=start; // HERE AGAIN
    for(int x=0;x<end;x++){
        if(A[x]<A[end]){
            swap(A[x],A[pIndex]);
            pIndex=pIndex+1;   
        }   
    }
    swap(A[pIndex],A[end]);
}
swap(A[pIndex],A[end]); // uses non-determined pIndex
return pIndex; // returns non-determined pIndex

将 int pIndex=start; 简单地更改为 pIndex=start; 将解决您的崩溃问题，但您的分区方法仍然需要...帮助。

---

“扫描”分区方法

对于假设为右尾的主元值，分区的“扫掠”方法通常是这样完成的，您很难将其简化(调用 std::partition 无法承受):

size_t Partition(int *A, size_t len)
{
    if (len < 2)
        return 0;

    size_t pvt = 0;
    for (size_t i=0; i<end; ++i)
    {
        if (A[i] < a[len-1])
            std::swap(A[i], A[pvt++])
    }
    std::swap(A[pvt], a[len-1]);
    return pvt;
};

上述算法仅包括分区所需的必需品:序列迭代器(在您的情况下为指针)和序列长度。其他一切都是基于这两项的确定性。下面是一个快速示例程序，它是如何工作的，有意将 5 作为枢轴值:

#include <iostream>

size_t Partition(int *A, size_t len)
{
    if (len < 2)
        return 0;

    size_t pvt = 0;
    for (size_t i=0; i<len-1; ++i)
    {
        if (A[i] < A[len-1])
            std::swap(A[i], A[pvt++]);
    }
    std::swap(A[pvt], A[len-1]);
    return pvt;
};

int main()
{
    int arr[] = { 4, 8, 7, 3, 9, 2, 1, 6, 5 };
    size_t n = Partition(arr, sizeof(arr)/sizeof(*arr));
    std::cout << "Partition : " << n << '\n';
    for (auto x : arr)
        std::cout << x << ' ';
    std::cout << '\n';
}

输出

Partition : 4
4 3 2 1 5 7 8 6 9 

---

如何从 QuickSort 调用

调用快速排序中的分区设置枢轴位置，它成为底部段的“结束”迭代点，以及顶部段的 one-BEFORE 迭代点。 关键从 Partition() 调用返回的枢轴位置在递归时不应包含在 either 子序列中。

void QuickSort(int *A, size_t len)
{
    if (len < 2)
        return;

    size_t pvt = Partition(A, len);
    QuickSort(A, pvt++);        // NOTE: post increment...
    QuickSort(A+pvt, len-pvt);  // ...which makes this skip the pivot
}

是的，指针算术很厉害，你不觉得吗？

---

将它们放在一起

下面的程序结合了 Partition 和 QuickSort :

#include <iostream>

size_t Partition(int *A, size_t len)
{
    if (len < 2)
        return 0;

    size_t pvt = 0;
    for (size_t i=0; i<len-1; ++i)
    {
        if (A[i] < A[len-1])
            std::swap(A[i], A[pvt++]);
    }
    std::swap(A[pvt], A[len-1]);
    return pvt;
};

void QuickSort(int *A, size_t len)
{
    if (len < 2)
        return;

    size_t pvt = Partition(A, len);
    QuickSort(A, pvt++);            // NOTE: post increment
    QuickSort(A+pvt, len-pvt);
}

int main()
{
    int arr[] = { 4, 8, 7, 3, 9, 2, 1, 6, 5 };
    QuickSort(arr, sizeof(arr)/sizeof(*arr));
    for (auto x : arr)
        std::cout << x << ' ';
    std::cout << '\n';
}

输出

1 2 3 4 5 6 7 8 9 

希望对你有帮助。