c++ - 我不明白为什么我收到段错误错误

Question

我目前正在尝试学习快速排序，这是我的代码:

#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
void swap(int *a, int *b)
{
    int t = *a;
    *a = *b;
    *b = t;
}

int partition(vector<int> &A, int low, int high)
{
    int pivot = A[low];
    int i = low; 
    int j = high;
    while(i < j){
        do
        {
            i++;
        }while(A[i]>=pivot);
        do
        {
            j--;
        }while(A[j]<pivot);
        if(i < j)
        {
            swap(A[i], A[j]);
        }
    }
    swap(A[low], A[j]);
    return j;
}

void QuickSort(vector<int> &A, int low, int high)
{
    int j = partition(A, low, high);
    QuickSort(A, low, j);
    QuickSort(A, j+1, high);
}

int main()
{
    vector<int> A{-7, 11, -3, 3, 2};

    QuickSort(A, 0, A.size()-1);
    for(int i:A)
    {
        cout << i << endl;  
    }
}

代码运行后，我不断收到段错误(核心转储)，我该如何解决这个错误。
另外，任何人都可以推荐一个好的 c++ 调试器。太感谢了

Answer 1

您的 QuickSort 中有无限递归。功能。每当它被调用时，它都会调用自己，并且没有条件可以打破循环。

另外，您的 swap功能不起作用。如其所写，A 中的值bins 将提供给函数并解释为地址。那不应该编译。它编译的唯一原因是您没有在程序中使用该函数。您正在使用 std::swap因为你已经完成了using namespace std; ，所以不要那样做。

您的 swap函数应通过引用获取参数，您需要在 QuickSort 中添加条件功能。

我不确定您尝试实现哪种分区方案，所以我做了一些更改以使其符合 Hoare partition scheme 的要求。 .

#include <iostream>
#include <vector>

void swap(int& a, int& b) {                    // take arguments by reference
    int t = a;
    a = b;
    b = t;
}

size_t partition(std::vector<int>& A, size_t low, size_t high) {
    int pivot = A[(high + low) / 2];
    size_t i = low;
    size_t j = high;
    while(true) {
        while(A[i] < pivot) ++i;
        while(A[j] > pivot) --j;
        if(i >= j) return j;
        swap(A[i], A[j]);
        ++i;
        --j;
    }
}

void QuickSort(std::vector<int>& A, size_t low, size_t high) {
    if(low < high) {                         // added condition
        size_t j = partition(A, low, high);
        QuickSort(A, low, j);
        QuickSort(A, j + 1, high);
    }
}

int main() {
    std::vector<int> A{-7, 11, -3, 3, 2};

    QuickSort(A, 0, A.size() - 1);
    for(int i : A) {
        std::cout << i << '\n';
    }
}