c++ - 递归合并排序算法实现
问题描述
我是算法的新手。我尝试使用std::vector
. 但我被困住了。代码不起作用。
我看过算法介绍中的算法,Cormen/Leiserson/Rivest/Stein 第 3 版。我尝试实现的伪代码。
这是我的合并功能:
void merge(std::vector<int>& vec, size_t vec_init, size_t vec_mid, size_t vec_size) {
int leftLoop = 0;
int rightLoop = 0;
int vecLoop = 0;
size_t mid = vec_mid - vec_init + 1;
std::vector<int> Left_Vec(std::begin(vec), std::begin(vec) + mid);
std::vector<int> Right_Vec(std::begin(vec) + mid, std::end(vec));
for (size_t vecLoop = vec_init; vecLoop<vec_size; ++vecLoop) {
vec[vecLoop] = (Left_Vec[leftLoop] <= Right_Vec[rightLoop]) ? Left_Vec[leftLoop++] : Right_Vec[rightLoop++];
}
}
这里是我的合并排序功能
void merge_sort(std::vector<int>& vec, size_t vec_init, size_t vec_size) {
if (vec_init < vec_size) {
size_t vec_mid = (vec_init + vec_size) / 2;
merge_sort(vec, vec_init, vec_mid);
merge_sort(vec, vec_mid + 1, vec_size);
merge(vec, vec_init, vec_mid, vec_size);
}
}
输入vec = {30,40,20,10}
时,输出vec = {10, 10, 0, 20}
:
int main() {
auto data = std::vector{ 30, 40, 20, 10 };
merge_sort(data, 0, data.size());
for (auto e : data) std::cout << e << ", ";
std::cout << '\n';
// outputs 10, 10, 0, 20,
}
我对算法或代码的错误在哪里?
解决方案
有几个问题。这些更改将修复代码:
void merge(std::vector<int>& vec, size_t vec_start, size_t vec_mid, size_t vec_end) {
size_t leftLoop = 0;
size_t rightLoop = 0;
size_t vecLoop = 0;
// Not needed, much simpler if mid is relative to vec.begin()
//size_t mid = vec_mid - vec_init + 1;
// You didn't take vec_init and vec_size into account when calculating the ranges.
std::vector<int> Left_Vec(std::begin(vec) + vec_start, std::begin(vec) + vec_mid);
std::vector<int> Right_Vec(std::begin(vec) + vec_mid, std::begin(vec) + vec_end);
// Values are not uniformly distributed in the left and right vec. You have to check for
// running out of elements in any of them.
for (/*size_t*/ vecLoop = vec_start; leftLoop < Left_Vec.size() && rightLoop < Right_Vec.size(); ++vecLoop) {
// ^~~~~ shadowed outer vecLoop ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
vec[vecLoop] = Left_Vec[leftLoop] <= Right_Vec[rightLoop] ? Left_Vec[leftLoop++] : Right_Vec[rightLoop++];
}
// Copy the rest of the values into vec.
if (leftLoop == Left_Vec.size())
std::copy(Right_Vec.begin() + rightLoop, Right_Vec.end(), vec.begin() + vecLoop);
else
std::copy(Left_Vec.begin() + leftLoop, Left_Vec.end(), vec.begin() + vecLoop);
}
void merge_sort(std::vector<int>& vec, size_t vec_start, size_t vec_end) {
// Should only run the function if there are at least 2 elements, otherwise vec_mid
// would be always at least vec_start + 1 and the recursion would never stop.
if (vec_end - vec_start >= 2) {
size_t vec_mid = (vec_start + vec_end) / 2;
merge_sort(vec, vec_start, vec_mid);
merge_sort(vec, vec_mid /* + 1 */, vec_end);
// ^~~ + 1 here would skip an element
merge(vec, vec_start, vec_mid, vec_end);
}
}
推荐阅读
- javascript - Javascript数字分隔符?
- r - 在 R 中使用分隔符读取多个 CSV 文件
- python - 将具有相同类的选择元素中的多个值传递给 django 视图
- c - 当我尝试在 C 中使用 strtok 时出现分段错误(核心转储)
- java - SpringBoot 上传 Excel 并读取为 JSON
- javascript - Jquery UI - 在旋转元素上拖动时出现问题
- html - html文本元素有奇怪的高度
- java - 在 Java 中,如何通过带有 varargs(可变参数)的方法传递用户输入?
- c - 如何在 C 中读取名称中有空格的文件
- javascript - 无法在 div 上显示循环的 JSON 数据