如何根據以下標準進行排序？

Question

我有一個（x，y）對值列表。值在0，xmax和0，ymax之間浮動。我需要對它們進行排序，通過平衡x值和更偏向於x。

這是我計劃如何進行排序的圖片展示。

中的數字1,2,3 ....和箭頭表示其中我想成爲第一所選值的順序（和方向）。 。 對於例如，在這種情況下，我想要的值對被歸類爲： 1. X1，Y1 2. X2，Y2 3. X3，Y3 4. X4，Y4 5. X5，Y5

我不知道如何開始實現這個，因爲值是浮動的。首先對算法進行粗略概述會很有幫助。

編輯：更詳細的解釋

1. 如果x VAL和y的值都接近最大值，這意味着我想，在我的列表的頂部（最可取的）。 （x = xmax，y = lim）優於（x = xmax-1，y = ymax），所以我想明確給出'x'更優先。 - （用淺藍色箭頭表示）

2. 如果x和y的值低於'限制標記'，那麼我需要有一個x關閉平衡，其中y的「輕微」優先級。

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則減少y在區域A中，並且通過減少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 

當限制（mpoint_sort_limit或）是5。