1

我目前正在研究一种算法，该算法要求我的多维数组（当前为 3 维）按第一项和第二项的总和值进行排序。具体来说：

（交换项目 i 和 j 的条件）

if ((Array[i][1]+Array[i][2]) > (Array[j][1]+Array[j][2])) return 1;

出于测试目的，我决定使用选择排序。但是，我的算法需要在 5 秒内完成所有魔法。如果它有大约 200 000 个项目，则选择排序本身需要大约 10 秒来对这样的数组进行排序。

我决定使用更好的算法，因为我对我的程序的其余部分非常有信心。我知道 unix 系统包含一个内置的快速排序功能，qsort（可通过终端中的man qsort获得）。但是，我不知道如何实现它。

我的想法是创建另一个数组，一维（1D），长度相同，包含主数组中的项目索引。通过这一点，我可能只能对二级一维数组进行排序，其中第一项将在主数组中具有最小总和的项索引，第二项将具有第二小的项，依此类推。

但是，我该怎么做呢？Qsort函数需要提供比较函数，来决定是否交换。如果我确实制作了自己的比较函数（就像我在问题开始时所说的那样），当主数组仅在main中指定时，我该如何使用 (Array[SeconArray[i]][0])该函数，因此不能通过同一文件中的另一个函数访问？

我会很高兴有任何提示或技巧来解决这个问题。我也不热衷于使用 qsort。如果您认为另一种排序算法可以做得更好，请告诉我。

非常感谢

4

1 回答 1

1

我只有有限的时间来发布这个，但希望这个想法很清楚。这是 qsort 可以设置为执行您要查找的操作的一种方式。这是一个二维数组 Nx3，我用 [0.0,500) 中的随机值填充了它。这个想法可以扩展到 3D 和超越阵列。

诀窍是让行宽正确（或者在 3D 平板、4D 立方体等的情况下......）

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

int cmp_row(const void* arg1, const void* arg2)
{
    const double *ar1 = arg1;
    const double *ar2 = arg2;

    double diff = (ar1[1] + ar1[2] - ar2[1] - ar2[2]);
    return (diff < 0.0) ? -1 : (0.0 < diff);
}

int main(int argc, char *argv[])
{
    static const int N = 50;
    double (*ar)[3] = NULL;
    int i=0;

    // see prng
    srand((unsigned)time(NULL));

    // allocat space for Nx3 2D array.
    ar = calloc(N, sizeof(*ar));

    // since I've no test data, random fill with values
    //  from [0..500)
    for (i=0;i<N;++i)
    {
        ar[i][1] = ((double)rand()/(double)RAND_MAX)*500.0;
        ar[i][2] = ((double)rand()/(double)RAND_MAX)*500.0;
    }

    // sort by elements 1+2
    qsort(ar, N, sizeof(*ar), cmp_row);

    for (i=0;i<N;++i)
    {
        printf("%3d : %7.3f + %7.3f  = %7.3f\n",
               i+1, ar[i][1], ar[i][2], ar[i][1]+ar[i][2]);
    }

    // release allocation
    free(ar);

    return 0;
}

注意：在处理我所说的纯语法 2D+ 数组时，这会变得有点复杂。这些将是我实际上是指针向量的“数组”。int **ar等等。然而，前提几乎相同，只有比较器必须改变。如果我有时间，如果输入允许，我会添加这样一个野兽作为额外的样本。

最后说明：这不能防止浮点值的潜在上溢或下溢。一个相当复杂的纯布尔逻辑比较器可以做到这一点，但除非你的数据对这种极端情况非常敏感，否则对于这个例子来说几乎不值得。

输出（显然你的会有所不同）

我已经将 的总和ar[i][1] + ar[i][2]作为排序顺序的证据包含在内，我认为这是你想要的。我希望这有帮助。

  1 :  47.986 +   1.471  =  49.457
  2 : 114.418 +  26.848  = 141.267
  3 : 148.183 +  12.145  = 160.328
  4 :  46.925 + 161.231  = 208.155
  5 : 102.405 + 116.097  = 218.502
  6 :  58.676 + 172.490  = 231.167
  7 : 144.797 +  99.977  = 244.774
  8 :   8.914 + 314.920  = 323.833
  9 :  68.885 + 255.924  = 324.809
 10 : 107.825 + 220.631  = 328.457
 11 : 287.056 +  44.610  = 331.665
 12 : 217.505 + 114.799  = 332.304
 13 : 240.620 + 104.506  = 345.127
 14 : 242.288 + 133.509  = 375.797
 15 : 381.538 +   4.073  = 385.611
 16 :   4.991 + 383.519  = 388.510
 17 : 257.611 + 163.872  = 421.483
 18 :  43.278 + 380.951  = 424.230
 19 : 300.775 + 129.879  = 430.654
 20 : 134.814 + 314.688  = 449.502
 21 : 103.281 + 346.874  = 450.155
 22 : 197.761 + 263.668  = 461.429
 23 : 303.872 + 173.430  = 477.302
 24 : 466.265 +  11.400  = 477.665
 25 : 108.817 + 391.995  = 500.812
 26 : 467.992 +  40.985  = 508.977
 27 : 353.493 + 160.398  = 513.891
 28 : 406.446 + 130.214  = 536.659
 29 : 244.678 + 303.989  = 548.667
 30 : 303.282 + 260.434  = 563.716
 31 : 254.139 + 317.150  = 571.290
 32 : 368.311 + 203.118  = 571.429
 33 : 372.654 + 201.597  = 574.251
 34 : 143.985 + 454.796  = 598.781
 35 : 254.561 + 402.038  = 656.598
 36 : 309.922 + 363.872  = 673.795
 37 : 196.554 + 478.447  = 675.000
 38 : 493.585 + 185.749  = 679.334
 39 : 438.196 + 257.858  = 696.054
 40 : 347.198 + 360.908  = 708.107
 41 : 262.210 + 456.034  = 718.244
 42 : 389.174 + 339.315  = 728.489
 43 : 300.199 + 446.422  = 746.621
 44 : 344.346 + 427.167  = 771.513
 45 : 317.604 + 470.313  = 787.917
 46 : 312.785 + 475.855  = 788.640
 47 : 334.682 + 492.928  = 827.609
 48 : 399.056 + 430.449  = 829.505
 49 : 460.128 + 373.025  = 833.154
 50 : 419.137 + 440.745  = 859.882
于 2013-11-14T09:27:39.183 回答