如何按特定单元格对二维数组进行快速排序?

Question

我有一个2d数组，我想快速排序它与给定的qsort()函数在c++:

unsigned work[N][3];

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

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

编辑:

如果我这样做，会有帮助吗?

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

和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的数组，这里没有间接的指针。所以它非常适合按std::qsort:

排序

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

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

EDIT:不过，最好的解决方案确实是放弃这个数组的数组，并使用更适合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-array):

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略微提高的性能。

Answer 2

是的，你可以qsort()这个。qsort()的工作原理是:获取所需的线性"东西"块，将其划分为统一大小的块，其中您指定大小(以字节为单位)，并为您提供每个块分区的基址以进行比较。

首先，确定你需要的尺寸。很明显，您正在排序的"事物"是数组行三个元素宽。其次，编写一个比较器，它可以接受两个指针的基址，在我们的例子中，一个简单的指针就可以工作，因为它很好地剥离了外部数组维度。最后，实际比较将在给定的每个指针p的三个元素深度(准确地说是p[2])上进行:

那么让我们充实一下代码:

#include <stdlib.h>
#include <stdio.h>
#include <memory.h>
#include <time.h>
static const size_t ROWSIZE = 3;
static void print_array(int rows, int ar[rows][ROWSIZE])
{
    int i,j;
    for (i=0;i<rows;++i)
    {
        for (j=0; j<ROWSIZE; printf("%d ", ar[i][j++]));
        printf("n");
    }
    printf("n");
}
// compare function
static int compare_row(const void* left, const void* right)
{
    const int *ileft = left, *iright = right;
    return ileft[ROWSIZE-1] - iright[ROWSIZE-1];
}
int main()
{
    int ar[10][ROWSIZE] = {0}, i;
    // fill with random junk from 10 to 99
    srand((unsigned)time(0));
    for (i=0;i<ROWSIZE * sizeof(ar)/sizeof(ar[0]); ++i)
        ar[i/ROWSIZE][i%ROWSIZE] = 10 + (rand() % 90);
    // print prior to sort.
    print_array(sizeof(ar)/sizeof(ar[0]), ar);
    // send to qsort
    qsort(ar, sizeof(ar)/sizeof(ar[0]), sizeof(ar[0]), compare_row);
    // print again after sort.
    print_array(sizeof(ar)/sizeof(ar[0]), ar);
    return EXIT_SUCCESS;
}

50 14 23 
69 81 93 
30 72 18 
26 49 29 
51 87 58 
18 74 40 
26 61 26 
43 80 27 
27 61 34 
13 66 89 
30 72 18 
50 14 23 
26 61 26 
43 80 27 
26 49 29 
27 61 34 
18 74 40 
51 87 58 
13 66 89 
69 81 93