c++ - 如何按特定单元格对二维数组进行快速排序？

Question

我有一个二维数组，我想用 C++ 中给定的 qsort() 函数对其进行快速排序:

unsigned work[N][3];

我想按第三个索引对“工作”数组进行排序...所以如果 work[i] 在 work[j] 之前 如果 工作[i][2]>工作[j][2]。

我知道我需要使用一个函数来比较它，但我不知道该怎么做。

编辑: 如果我执行以下操作，会有帮助吗:

unsigned work[3][N];
qsort(work[2], N, sizeof(unsigned), compare);

比较如下:

int compare(const void* a, const void* b)
{
    return(*(unsigned*)a-*(unsigned*)b);
}

?

Answer 1

嗯，简短的回答是不使用 std::qsort 完全没有，但是 std::sort .但不幸的是，后者不起作用，因为 unsigned int[3]不可分配。所以这是最简单的 std::qsort解决方案。

首先我们定义一个自定义比较函数:

// return -1 if a before b, 1 if after, 0 if equal
int compare(const void *a, const void *b)
{
    const unsigned int *arg1 = reinterpret_cast<const unsigned int*>(a);
    const unsigned int *arg2 = reinterpret_cast<const unsigned int*>(b);
    if(arg1[2] > arg2[2])
        return -1;
    if(arg1[2] < arg2[2])
        return 1;
    return 0;
}

然后我们使用它来对数组进行排序。请记住 work是数组的数组，因此 work[0]是 3 unsigned int 的数组s，没有以任何方式涉及指针间接寻址。所以它非常适合按 std::qsort 排序:

std::qsort(work, sizeof(work)/sizeof(work[0]), sizeof(work[0]), compare);

顺便说一下，第三个元素的索引是2 ，因为我们通常从 0 开始计数在 C++(和许多其他编程语言)中。

编辑:尽管如此，最好的解决方案确实是放弃这个数组数组并使用更适合 C++ 的东西，比如 std::vector的 std::array<unsigned int,3> s(或更适合实际上下文的任何其他数据结构):

typedef std::array<unsigned int,3> uint3;
std::vector<uint3> work(N);

然后可以用一个简单的排序:

std::sort(std::begin(work), std::end(work), 
          [](const uint3 &a, const uint3 &b) { return a[2] > b[2]; });

或者，如果您没有 C++11(尽管在这种情况下您也不会有 std::array，并且需要开始考虑一个合理的数据结构，而不仅仅是一个 3 数组):

struct compare
{
    bool operator()(const uint3 &a, const uint3 &b) const
    {
        return a[2] > b[2];
    }
};

std::sort(work.begin(), work.end(), compare());

作为更清晰代码的奖励，您也很可能获得轻微的性能提升 std::sort在 std::qsort .