c - 基于 C 中 4 个索引的元组对数组进行排序

Question

我有一个有趣的问题，过去 2 天我一直在努力解决这个问题，但没有具体的解决方案。我正在尝试用 C 编写一个程序，该程序采用以下输入数组：

step1：根据第 3 列对上述数组进行分组（对 4 个元素的元组（即每一行）进行桶排序，基于第 3 列的值：

第 2 步：最后根据每个桶中的第 4 列对元素进行排序，如下所示：

最终输出数组：

第 1 列和第 2 列的元素在上述排序过程中不起任何作用。

我尝试了各种技术，使用快速排序或桶排序，然后是随后的快速排序。没有什么是完全正确的。任何人都可以建议使用适当的数据结构在 C 中执行此操作的方法。

score 5 · Accepted Answer

问题是，您实际上并不需要进行多种排序；您可以根据元组的两个字段进行单次排序。

只需使用现有的排序算法，但使用如下所示的比较函数：

if (val[2] != otherval[2])
    return val[2] < otherval[2];
else
    return val[3] < otherval[3];

这将使用第三列进行排序，除非值相等，在这种情况下它将使用第四列。

或者，如果您想做两个单独的排序，首先按第四列排序，然后按第三列排序。

score 4 · Accepted Answer

#include <stdio.h>
#include <stdlib.h>

int cmp(const void *x, const void *y){
    int (*a)[4] = (int(*)[4])x;
    int (*b)[4] = (int(*)[4])y;
    if((*a)[2]==(*b)[2])
        return (*a)[3] - (*b)[3];
    else
        return (*a)[2] - (*b)[2];
}

int main(void){
    int data[][4] = {
        {1,1,5,5},
        {1,1,5,9},
        {2,2,6,2},
        {1,2,5,5},
        {1,3,6,6},
        {1,4,5,1},
        {4,1,5,6},
        {5,2,7,1},
        {1,1,6,0},
        {2,2,5,0}
    };
    int size = sizeof(data)/sizeof(data[0]);
    int i,j;
    qsort(data, size, sizeof(data[0]), cmp);
    //result print
    for(i=0;i<size;++i){
        for(j=0;j<4;++j)
            printf("%d ", data[i][j]);
        printf("\n");
    }
    return 0;
}

score 2 · Accepted Answer

这实际上应该很简单。标准 qsort 函数接受一个比较两个元素的回调。只需编写回调以期望元素是子数组并首先使用第三个元素进行比较。如果第三个元素相等，则使用第四个元素进行比较。

c - 基于 C 中 4 个索引的元组对数组进行排序

3 回答 3

Related

Reference