- html - 出于某种原因,IE8 对我的 Sass 文件中继承的 html5 CSS 不友好?
- JMeter 在响应断言中使用 span 标签的问题
- html - 在 :hover and :active? 上具有不同效果的 CSS 动画
- html - 相对于居中的 html 内容固定的 CSS 重复背景?
该代码适用于较小的 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;
您显式地传递了 begin
和 end
位置,但是您从完整列表中选择了 pivot 元素。这听起来不对。您应该在 begin
和 end
之间选择一个枢轴元素。此外,x
应该从 begin
开始,y
应该从 end
开始。否则,您总是在每个递归步骤中处理完整列表,这可以解释您正在经历的无限递归。
关于c++ - 我的快速排序代码溢出堆栈,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/12769848/
我有一个 div(蓝色框),它在父元素(红色框)内的页面上绝对定位,我需要将 overflow-y 设置为隐藏,以便它强制 Y 轴上的溢出内容切掉了,但我希望任何溢出-x 的内容都可见。 HTML:
请参阅以下帖子以获取突出显示我的问题和可能的解决方案的图片: CSS overflow-y:visible, overflow-x:scroll 但是,当您实际移动滚动条时,此策略会中断。在建议的实现
我在搜索中看到过几个类似的问题,但要么没有正确回答问题,要么没有给出答案。所以,我再问一次。 .parent { overflow-y:scroll; overflow-x:visible; wid
我读过这个CSS overflow-x hidden and overflow-y visible (以及很多其他帖子)但我无法在我的具体情况下使用它。 我正在使用 slick-slider并想添加下
我有以下 Spark 作业,试图将所有内容保留在内存中: val myOutRDD = myInRDD.flatMap { fp => val tuple2List: ListBuffer[(St
我有疑问 两个16位的值加上最大值,16位机会不会溢出? 我会详细说明 unsigned short a; unsigned short b; unsigned long c; c=(unsigne
我有这个 HTML 和 CSS,但“溢出:隐藏”标签在 Firefox 中不起作用。这让我感到难过...有人知道为什么它不起作用吗?是因为A标签不支持overflow标签吗? #page_sideba
我正在开发一个程序,用于在 C++ 中分解非常大的数字(20 位或更多),并且正在使用 GMP 来处理溢出问题。我的程序对于大约 10 位或更少的数字运行良好,但是当我向它抛出一个 15 位数字时,它
我创建了一个 Canvas ,并在其中放置了一个StackPanel。 StackPanel是水平的,它接受缩略图图像的列表。 Canvas 具有固定的大小。当我放置的缩略图多于Canvas宽度不能容
当 g_array_append_val() 时会发生什么或 GLib 中的其他附加/前置函数之一,使 GArray 的长度大于 guint (unsigned int) 所能容纳的长度? 文档对此没
overflow-x:hidden 和 overflow:hidden; 有什么区别? 我所知道的是overflow-x:hidden;禁用水平滚动,但当我使用它时,它不仅仅适用于 Firefox,所
我们正在运行 Solr 来索引大量数据,但遇到了一个非常有趣的问题,我无法在任何地方找到任何帮助。 似乎 Solr 使用带符号的 32 位整数来计算索引中当前的文档数。我们刚刚达到了这个数字,我们的
这是我的查询: 从相似性中选择 COUNT(*),其中 T1Similarity = 0 或 T2Similarity = 0 结果如下: Msg 8115, Level 16, State 2, L
int main(void) { char x1 = 0x81; char x2 = 0x1; int a, b; a = x1
我有一个 div,其中的内容通过查询的 append() 定期附加到它。随着内容越来越长,最终会溢出div。我不希望在溢出时出现滚动条,但仍然让内容向上滚动以显示下面的新内容。 这可能吗?当我使用 o
我为 UITextField 创建了一个简单的子类,它按预期工作。我遇到的唯一问题是当文本值变得太大时,它会溢出到清除按钮中。 我似乎无法找到如何仅更改文本的右侧以具有一些填充而不与清除按钮相交的方法
我想要一个包括下拉菜单的粘性导航栏。但是,当我将鼠标悬停在它上面时,下拉菜单没有显示。 如果我删除 overflow: hidden;在无序列表中,当我向下滚动时,导航栏设法保持在顶部,但是导航栏是不
我正在研究一些按钮。我想要一个翻转状态,我在一个 div 的图像中有这个,溢出:隐藏以隐藏不活动的状态。它有时有效,但有时看起来像这样: 最奇怪的是,当我尝试使用 Chrome Web Inspect
基本上,我正在尝试创建一个六边形形状,它内部有一个圆圈,圆圈的多余部分应该被隐藏。演示:https://codepen.io/AskSaikatSinha/pen/jwXNPJ?editors=110
这似乎是一个相当常见且不那么奇特的用例,但我以前没有遇到过。我设置了一支笔,但无法在那里复制它,我正在努力找出原因。 Demo Pen 左侧边栏有一个用于元素列表的自定义滚动窗口,但是虽然设置 ove
我是一名优秀的程序员,十分优秀!