我目前正在尝试学习快速排序,这是我的代码:
#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++ 调试器。太感谢了
最佳答案
您的 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';
}
}
关于c++ - 我不明白为什么我收到段错误错误,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/62395175/