gpt4 book ai didi

c++ - 我的快速排序代码溢出堆栈

转载 作者:行者123 更新时间:2023-11-28 00:53:26 25 4
gpt4 key购买 nike

该代码适用于较小的 num_items,但会溢出堆栈 num_items = 1000

我认为 1000 是一个非常小的数字,因此应该有一种方法可以使这项工作达到更大的数字。我该怎么做才能让它在更多的递归调用中存活下来?

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime>

void printv(std::vector<int>& v) {
for (int i=0; i<v.size(); i++) std::cout << v[i] << " ";
std::cout << std::endl;
}

void quicksort(std::vector<int>& v, int begin, int end) {

if (((end - begin) <= 1) ||
(begin < 0) ||
(end > (v.size() - 1))) return;

int pivot = v[std::rand() % v.size()];

int x = 0;
int y = v.size() -1;

while(x < y) {
int changed = 0;
if(v[x] <= pivot) {
x++;
changed = 1;
}
if (v[y] > pivot) {
y--;
changed = 1;
}
if (!changed){
std::swap(v[x], v[y]);
x++;
y--;
}
}

if (x == y) y++;
if (x > y) std::swap(x, y);

quicksort(v, begin, x);
quicksort(v, y, end);
}

int ran() {
return std::rand() % 100;
}

int main() {
std::srand(std::time(0));
int num_items = 1000;
std::vector<int> v (num_items);
std::generate_n(v.begin(), num_items, ran);

printv(v);
quicksort(v, 0, v.size()-1);
printv(v);
}

也欢迎对代码提出一般性意见。


卡在 [0,4]:

#1  0x0000000000400b4c in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:14
#2 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#3 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#4 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#5 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#6 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43
#7 0x0000000000400cc1 in quicksort (
v=std::vector of length 1000, capacity 1000 = {...}, begin=0, end=4)
at quicksort.cpp:43

最佳答案

int pivot = v[std::rand() % v.size()];

int x = 0;
int y = v.size() -1;

您显式地传递了 beginend 位置,但是您从完整列表中选择了 pivot 元素。这听起来不对。您应该在 beginend 之间选择一个枢轴元素。此外,x 应该从 begin 开始,y 应该从 end 开始。否则,您总是在每个递归步骤中处理完整列表,这可以解释您正在经历的无限递归。

关于c++ - 我的快速排序代码溢出堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12769848/

25 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com