c++ - 归并排序的归并函数
问题描述
我在合并排序的合并部分遇到了困难。每次我合并向量的两半时,它最终都会丢失向量中的至少一个值。
void merge(vector <double> &v, vector <double> &temp, int start, int size) {
int i, j, k;
i = start;
j = start + size - size/2;
k = start;
temp.resize(v.size());
while(i < start+size/2 && j < start+size) {
if(v[i] <= v[j]) {
temp[k] = v[i];
i++;
k++;
// cout << "i <= j " << temp[k] << endl;
} else {
temp[k] = v[j];
j++;
k++;
// cout << "i > j "<< temp[k] << endl;
}
}
for(i = start; i < start+size; i++) {
v[i] = temp[i];
}
}
解决方案
由于我不知道调用者的实现,我可能是错的,但我认为有两个错误。
首先,在第一个 while 循环
i
中终止。start+size/2
此值必须等于第一个值j
isstart+size-size/2
。但是,例如,如果size==5
,那么start+5/2=start+2
和start+5-5/2=start+3
。在这种情况下v[start+2]
永远不会进入最终结果。其次,在跳出第一个 while 循环之后,
v
还必须将剩余的值分配给temp
。
总之,我的快速回答如下。演示在这里。
void merge(std::vector<double> &v, std::vector<double> &temp, int start, int size)
{
int i = start; // left array begin
int j = i + size - size/2; // right array begin (which should be guaranteed by caller.)
int i_max = j; // left array end
int j_max = start+size; // right array end
int k = i;
temp.resize(v.size());
while(i < i_max && j < j_max)
{
if(v[i] <= v[j]){
temp[k] = v[i];
i++;
k++;
//std::cout << "i <= j: " << temp[k-1] << std::endl;
}
else {
temp[k] = v[j];
j++;
k++;
//std::cout << "i > j: "<< temp[k-1] << std::endl;
}
}
while (i < i_max) {
temp[k] = v[i];
i++;
k++;
}
while (j < j_max) {
temp[k] = v[j];
j++;
k++;
}
for(i = start; i < j_max; i++) {
v[i] = temp[i];
}
}
推荐阅读
- sql - 如何解决存储过程中的性能问题?
- primefaces - PrimeFaces 计划在某些 SlotDuration 配置下不会一直显示
- c# - 如何查找用户基于 2 个时间间隔将行插入数据库的频率(每周、每月)
- batch-file - 如何遍历给定目录中的所有文件夹并在vbs中为它们创建快捷方式?
- c# - 在用户键入时验证用户名、电子邮件
- smtp - 如何使用 Java Mail API 发送大于 25 MB 的文件
- php - 如何使用“MongoDB\Driver\Query($filter, $options)”?
- php - PHP:检查表单字段是否已设置且不为空 - 在 preg_replace 之前和之后
- python - 通过排除 Pandas 另一列中的特定值来填充一列
- sass - SCSS 复杂/嵌套映射