合并排序 - 向量不排序

我试图对std::vector<int>执行合并排序。矢量中的每个int对应于另一个矢量std::vector<Node>中的索引。每个节点都有一个深度。我试图根据深度进行排序。合并排序 - 向量不排序

我正在使用我找到的一些合并排序代码。它使用整数数组工作正常，所以我觉得它会在我的代码中正常工作。这里是我的代码缩短版本：

.h文件中：

class Log{ 
public: 
    static std::vector<int> a; 
};

.cpp文件：

std::vector<int> Log::a; 

int getNodeDepth (int index, std::vector<cv::ml::DTrees::Node::Node> nodeList, std::vector<int> treeList) { 
    //returns the node's depth 
} 

void exchange(int i, int j) { 
    int t = Log::a[i]; 
    Log::a[i] = Log::a[j]; 
    Log::a[j] = t; 
} 

void compare(int i, int j, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    if (getNodeDepth(nodeList[Log::a[i]], nodeList) > (getNodeDepth(nodeList[Log::a[j]], nodeList))) 
    exchange(i, j); 
} 

/** 
* lo is the starting position and 
* n is the length of the piece to be merged, 
* r is the distance of the elements to be compared 
*/ 
void oddEvenMerge(int lo, int n, int r, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    int m = r * 2; 
    if (m < n) { 
     oddEvenMerge(lo, n, m, nodeList); // even subsequence 
     oddEvenMerge(lo + r, n, m, nodeList); // odd subsequence 
     for (int i = lo + r; i + r < lo + n; i += m) 
      compare(i, i + r, nodeList); 
    } else 
     compare(lo, lo + r, nodeList); 
} 

/** 
* sorts a piece of length n of the array 
* starting at position lo 
*/ 
void oddEvenMergeSort(int lo, int n, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    if (n > 1) { 
     int m = n/2; 
     oddEvenMergeSort(lo, m, nodeList); 
     oddEvenMergeSort(lo + m, m, nodeList); 
     oddEvenMerge(lo, n, 1, nodeList); 
    } 
} 

int mergeSort(std::vector<int> treeList, std::vector<cv::ml::DTrees::Node::Node> nodeList) { 
    Log::a = treeList; 
    int i, n = sizeof(Log::a)/sizeof(Log::a[0]); 
    for (i = 0; i < n; i++) 
     std::cout << std::setw(3) << Log::a[i]; 
    std::cout << std::endl; 
    oddEvenMergeSort(0, n, nodeList); 
    //print sorted list 
    for (i = 0; i < Log::a.size(); i++) 
     std::cout << Log::a[i] << " * "; 
    std::cout << std::endl; 

    return(0); 
}

注意变量nodeList只是那里，因为深度方法需要它。输出看起来像只有矢量的前半部分被触摸。矢量的后半部分没有任何项目可以交换。我再次检查以确保深度是正确的，并且正确的事情正在交换。它只是没有完成这项工作。任何想法为什么？

来源

2015-12-17 iltp38

为什么不使用std :: sort？ http://www.cplusplus.com/reference/algorithm/sort/我认为你已经有了一个比较方法。 – LiMuBei

“我正在使用我找到的一些合并排序代码。” - 你找到了哪里？您不能只使用您在网上找到的未归属的代码，并遵守其随之列出的任何许可证。（虽然减少这个问题以缩短问题可能是合理的，但它必须在你真实的代码中，并且你应该从这里链接到它。） – BoBTFish

应该通过引用而不是按值传递nodeList吗？ – rcgldr

sizeof(Log::a)/sizeof(Log::a[0]);

这没有得到元素的数量Log::a！它获得std::vector类型的大小（以字节为单位），它与包含的元素的数量无关，然后除以元素的大小。这给你一些垃圾。

这个成语是阵列和std::size是更好的，但不是标准，但 - 你可以在你自己随便写这样的：

template <typename T, std::size_t N> 
std::size_t arraySize(T (&)[N]) 
{ 
    return N; 
}

（还有更令人费解的版本，如果你需要它作为一个编译时间常数。）

使用Log::a.size();可以获得std::vector的大小。

（我可能会遗漏其他问题，但这个问题很突出。）

来源

2015-12-17 11:25:39 BoBTFish

谢谢，我做了这个改变，它现在通过了所有的成员，但订单仍然是错误的。结果最终会写入数值，所以有重复。我不知道为什么它在正常的int数组上工作得很好时表现得如此奇怪。 – iltp38

合并排序 - 向量不排序

回答

相关问题