0

我想按它们的 x 对 n 维点的列表进行排序并存储它们的原始索引：

original=[(3,2,3)(1,2,1)(5,1,5)]

排序后：

[(1,2,1)(3,2,3)(5,1,5)]

和索引：

store=[1,0,2]

我曾经vector< vector<double>存储n维点：

a[0][0] = x, a[0][1] = y, a[0][2] = z, ...

我写了一个合并排序来做到这一点，source通过引用传输调用并通过引用传输result调用以获取索引。

我遇到了一个问题，如果我想打印结果，程序就会关闭。

#include <vector>
#include <cmath>
#include <cfloat>
#include <iostream>
#include <algorithm>
using namespace std;

void merge(vector< vector<double> >& source, vector< int >& result, int lmin, int lmax, int rmin, int rmax){
    int i = lmin, j = rmin;
    while(i <= lmin && j <= rmin){
        //left > right
        if(source[i][0] > source[j][0]){
            source[i].swap(source[j]);
            //exchange result
            int temp = result[j];
            result[j] = result[i];
            result[i] = temp;

            i ++;
        }
        else if(source[i][0] < source[j][0])
            source[i].swap(source[j]);

            j ++;
        }

}

void merge_sort(vector< vector<double> >& source, vector< int >& result, int min, int max){
    if(max - min == 0){
            result[min] = min;
            return;
    }
    int median = (max - min) / 2;
    merge_sort(source, result, min , median);
    merge_sort(source, result, median + 1 , max);
    merge(source, result, min, median, median + 1, max);
}

int main(){

       vector < vector<double> >test (8, vector<double>(3));
       vector < int >result (8);
       vector < vector<double> >ttt;
    test[0][0]= 10;
    test[0][1]= 20;
    test[0][2]= 30;
    //(1,2,3)
    test[1][0]= 1;
    test[1][1]= 2;
    test[1][2]= 3;
    //(1000,2000,3000)
    test[2][0]= 1000;
    test[2][1]= 2000;
    test[2][2]= 3000;
    //(100,200,300)
    test[3][0]= 100;
    test[3][1]= 200;
    test[3][2]= 300;
    //(100,200,300)
    test[4][0]= 100;
    test[4][1]= 200;
    test[4][2]= 302;
    //(100,200,300)
    test[5][0]= 100;
    test[5][1]= 200;
    test[5][2]= 3030;
    //(100,200,300)
    test[6][0]= 1000000;
    test[6][1]= 2000000;
    test[6][2]= 3000000;
    test[7][0]= 10;
    test[7][1]= 20;
    test[7][2]= 30.5;
    merge_sort(test, result, 0 , 7);

    for (int i = 0; i < test.size(); i ++){
        for(int j = 0; j < test[i].size(); j ++){
            cout << test[i][j] << endl;
        }
    }

    for(int i = 0; i < result.size(); i ++)cout << result[i] << endl;
}
4

2 回答 2

1

好吧，对于初学者来说：

int median = (max - min) / 2;

应该

int median = (max + min) / 2;

您可能想从在 C 中实现合并排序开始

并让自己成为一个好的调试器。此外，如果您发布您收到的实际错误消息，您将来可能会得到更多有用的响应。

于 2013-05-03T14:51:28.380 回答
1

您绝对应该学习如何使用调试工具。一步一步去，看看哪里会发生意想不到的事情。如果您还不知道如何使用，请尝试cout在这里和那里插入 s。通过将变量打印到屏幕上来观察变量的值。我相信在这种情况下，您将手动调试 * :) 通过打印值，您可以逐步了解您的算法是如何工作的。这是一个很好的做法。

int median = (max - min) / 2;

我相信你应该找到像unsigned int median = (int)floor((max+min)/2);

说max = 3和min = 2。根据您的代码中位数将0是无关紧要的。此时，当您使用此参数调用合并排序时，(min=2, max=median=0) 下一个中位数将被计算为负索引。因此，使用unsigned int中值将帮助您发现问题。看，仔细选择类型实际上对你有帮助，这个案例就是一个很好的例子。

通过修复您的这个错误，您的程序将终止。

于 2013-05-03T14:46:32.737 回答