我们目前正在研究算法,因此即使这不是作业相关任务,我也将此问题标记为“作业”。只是为了保险起见。
我们刚刚学习了随机选择算法,它的逻辑似乎很简单。从列表中选择一个元素,然后将该元素放到其正确的位置。然后在一个子列表中重复这个过程,直到索引处的元素处于其位置。其中索引是您希望在排序列表中的元素的位置。
这应该是快速排序算法的修改版本。但我们只对一个子列表进行排序,而不是两个子列表。因此可以提高性能 (在大O符号方面)。
使用外部存储器 (C++和基于零的数组),我可以成功地实现这种算法:
在这两个例子中,第一个元素被用作枢轴以保持设计简单。在这两个例子中,
有没有想法第二个例子是哪里出了问题?这是一个简单的偏移错误吗?
谢谢大家!
我们刚刚学习了随机选择算法,它的逻辑似乎很简单。从列表中选择一个元素,然后将该元素放到其正确的位置。然后在一个子列表中重复这个过程,直到索引处的元素处于其位置。其中索引是您希望在排序列表中的元素的位置。
这应该是快速排序算法的修改版本。但我们只对一个子列表进行排序,而不是两个子列表。因此可以提高性能 (在大O符号方面)。
使用外部存储器 (C++和基于零的数组),我可以成功地实现这种算法:
int r_select2(vector<int>& list, int i)
{
int p = list[0];
vector<int> left, right;
for (int k = 1; k < list.size(); ++k)
{
if (list[k] < p) left.push_back(list[k]);
else right.push_back(list[k]);
}
int j = left.size();
if (j > i) p = r_select2(left, i);
else if (j < i) p = r_select2(right, i - j - 1);
return p;
}
然而,我想要使用原地算法(in-situ)来实现,而不是使用额外的子数组。我相信这应该是一个容易/平凡的任务。但是,在某个地方,我的原地版本出了问题。也许只是太晚了,我需要休息,但我看不到以下版本失败的根本原因:
int r_select(vector<int>& list, int begin, int end, int i)
{
i = i + begin;
int p = list[begin];
if (begin < end)
{
int j = begin;
for (int k = begin + 1; k < end; ++k)
{
if (list[k] < p)
{
++j;
swap(list[j], list[k]);
}
}
swap(list[begin], list[j]);
if (j > i) p = r_select(list, begin, j, i);
else if (j < i) p = r_select(list, j + 1, end, i - j);
}
return p;
}
在这两个例子中,第一个元素被用作枢轴以保持设计简单。在这两个例子中,
i
是我想要的元素的索引。有没有想法第二个例子是哪里出了问题?这是一个简单的偏移错误吗?
谢谢大家!
r_select(list, 0, list.size(), 88)
后,我期望返回88。 - PinkDuck