c - 如何根据以下标准进行排序？

Question

我有一个 (x,y) 对值列表。这些值在 0,xmax 和 0,ymax 之间 float 。我需要通过平衡 x 和 y 值来对它们进行排序，更偏向于 x。

这是我计划如何进行分类的图示。

数字 1,2,3.... 和箭头代表我希望首先选择值的顺序(和方向)。例如，在这种情况下，我希望将值对排序为: 1. x1,y1 2. x2,y2 3. x3,y3 4. x4,y4 5. x5,y5

我不知道如何开始实现它，因为值是 float 。从粗略的算法概述开始会很有帮助。

编辑:更详细的解释

1. 如果 x val 和 y 值接近最大值，这意味着我希望它位于我的列表的顶部(最理想的)。

2. 在一定限度 (lim) 之前，我想明确地赋予 'x' 更高的优先级，因此 (x=xmax , y=lim) 优于 (x=xmax-1, y=ymax)。 --(用浅蓝色箭头表示)

3. 如果 x 和 y 值低于“极限标记”，那么我需要对 x 和 y 进行紧密平衡，并“略”优先于 x。

Answer 1

每个点 (x,y) 都属于以下四个区域之一:

    y ^
      │ B │ A    Region definitions:
      │   │      A) (x >= m) || (y >= m)
    m ┼   ┼──    B) (x < m && y < m) && (y > x)
      │  ╱       C) (x < m && y < m) && (x > y)
      │ D   C    D) (x < m && y < m) && (x == y)
      │╱      
      ┼───┼──>x
          m

在我看来，如果您通过减少 x 然后减少区域 A 中的 y 并通过减少 min( x,y) 然后减少其他区域的 max(x,y)；区域 A 排在区域 B、C 或 D 之前，区域 中的其他点相等B、C 和D 首先被C 排序，您实现了OP 所需的排序顺序。有关在 (0..9, 0..9) 中排序且限制为 5 的示例，请参阅此答案的底部。

即:

Sort A first
   In A, sort decreasing by x, then decreasing by y

Sort decreasing by min(x,y), then decreasing by max(x,y)
If tied, the point with the largest x goes first

如果我们有

typedef struct {
    double  x;
    double  y;
} point;

我们可以使用例如对 point 的数组进行排序。

#include <stdlib.h>

static __thread double  point_sort_limit;

static int point_sort_cmp(const void *ptr1, const void *ptr2)
{
    const point p1 = *(const point *)ptr1;
    const point p2 = *(const point *)ptr2;
    const int   a1 = (p1.x >= point_sort_limit) && (p1.y >= point_sort_limit);
    const int   a2 = (p2.x >= point_sort_limit) && (p2.y >= point_sort_limit);

    if (a1 && !a2)
        return -1;
    if (!a1 && a2)
        return +1;

    if (a1 && a2) {
        /* Both points in the region above the limits */
        if (p1.x > p2.x)
            return -1;
        if (p1.x < p2.x)
            return +1;
        if (p1.y > p2.y)
            return -1;
        if (p1.y < p2.y)
            return +1;

        /* p1 == p2. */
        return 0;
    } else {
        const double min1 = (p1.x <= p1.y) ? p1.x : p1.y;
        const double max1 = (p1.x <= p1.y) ? p1.y : p1.x;
        const double min2 = (p2.x <= p2.y) ? p2.x : p2.y;
        const double max2 = (p2.x <= p2.y) ? p2.y : p2.x;

        if (min1 > min2)
            return -1;
        if (min1 < min2)
            return +1;
        if (max1 > max2)
            return -1;
        if (max1 < max2)
            return +1;

        /* Sort points below the diagonal first. */
        if (p1.x > p2.x)
            return -1;
        if (p1.x < p2.x)
            return +1;

        /* p1 == p2. */
        return 0;
    }
}

void point_sort(point *array, const size_t count, const double limit)
{
    if (count > 1 && array != NULL) {
        point_sort_limit = limit;
        qsort(array, count, sizeof array[0], point_sort_cmp);
    }
}

C99 __thread 关键字使 point_sort_limit 变量特定于每个线程；也就是说，每个线程都有自己的变量副本。如果您不在程序中使用线程，则可以安全地省略 __thread 关键字。

你看，我们需要在某处保存限制，因为标准 C qsort() 不允许我们将任何额外参数传递给比较函数。如果我们在多线程程序中使用一个普通的全局变量，如果多个线程同时使用point_sort()函数，那么point_sort_limit在大多数线程中都会有不正确的值。将全局变量设置为线程局部变量可以避免这种情况。

如果我们查看常规 10×10 网格中的 100 个点，即 x = [0, 9]，y = [0, 9]，它们将被上述函数排序的顺序是

    y ^
    9 │  81  64  49  36  25  20  15  10   5   0
    8 │  83  66  51  38  27  21  16  11   6   1
    7 │  85  68  53  40  29  22  17  12   7   2
    6 │  87  70  55  42  31  23  18  13   8   3
   _5_│_ 89  72  57  44  33_|24_ 19  14   9   4
    4 │  91  74  59  46  35 |34  32  30  28  26
    3 │  93  76  61  48  47  45  43  41  39  37
    2 │  95  78  63  62  60  58  56  54  52  50
    1 │  97  80  79  77  75  73  71  69  67  65
    0 │  99  98  96  94  92  90  88  86  84  82
        ────────────────────┼───────────────────> x
         0   1   2   3   4   5   6   7   8   9

当限制(m 或 point_sort_limit)为 5 时。