按成对差异排序数组

Question

例如,我们有数组X[n] = {X0, X1, X2, ... Xn} 目标是对此数组进行排序,使每对之间的差异按升序排列.

例如 X[] = {10, 2, 7, 4}

答案是:

2 7 10 4
4 10 7 2

我有一些代码,但它是蛮力的:)

#include <stdio.h>

int main(int argc, char **argv)
{
    int array[] = { 10, 2, 7, 4 };
    int a[4];

    for(int i = 0; i < 4; i++){
        a[0] = array[i];

        for(int j = 0; j < 4; j++){
            a[1] = array[j];
            if(a[0] == a[1])
               continue;

            for(int k = 0; k < 4; k++){
                a[2] = array[k];
                if(a[0] == a[2] || a[1] == a[2])
                    continue;

            for(int l = 0; l < 4; l++){
                a[3] = array[l];
                if(a[0] == a[3] || a[1] == a[3] || a[2] == a[3])
                    continue;
                if(a[0] - a[1] < a[1] - a[2] && a[1] - a[2] < a[2] - a[3])  
                    printf("%d %d %d %d\n", a[0], a[1], a[2], a[3]);
             }
         }
     }
   }
    return 0;
 }

任何"漂亮"算法的想法？:)

Answer 1

该问题的解决方案并不总是可行。例如，数组X[] = {0, 0, 0}无法按要求“排序”，因为两个差值始终相等。

如果此问题有解决方案，则应按左图所示对数组值进行“排序”：按升序排列的值的某些子集应形成结果数组的前缀，然后按降序排列的所有剩余值应形成其后缀。并且“排序”数组应该是凸的。

这给出了算法的提示：对数组进行排序，然后将其值分成两个凸子集，然后提取这些子集之一并将其附加到末尾（以相反的顺序）。

一个简单的（部分）实现是：对数组进行排序，找到属于凸包的值的子集，然后检查所有剩余的值，如果它们是凸包，则将它们附加在末尾。仅当其中一个子集完全位于另一个子集之下时，该算法才有效。

如果结果子集相交（如右图所示），则可以使用该算法的改进版本：将已排序的数组分割成段，其中一个子集完全位于另一个子集（AB、BC）下方，然后对于其中的每一个段找到凸包并检查剩余子集的凸性。请注意，右图的 X 轴以特殊方式对应于数组索引：对于子集交集（A、B、C），X 对应于升序数组中的索引；交叉点之间的值的 X 坐标根据它们在结果数组中的位置进行缩放。

算法草图

1. 按升序对数组进行排序。
2. 从最大值开始，尝试将凸包值添加到“顶部”子集（以类似于格雷厄姆扫描算法的方式）。还将所有不属于凸包的值放入“底部”子集并检查其凸性。当所有值都正确适合“顶部”或“底部”子集时继续。当处理最小值时，从数组中删除这些子集之一，反转子集，并在数组的 和 处追加。
3. 如果在向“顶部”子集添加一些值后，“底部”子集不再是凸的，则回滚最后的添加并检查该值是否可以正确添加到“底部”子集。如果不是，则停止，因为输入数组无法按要求“排序”。否则，交换“顶部”和“底部”子集并继续步骤 2（已处理的值不应在子集之间移动，任何移动它们的尝试都应导致转到步骤 3）。

换句话说，我们可以从最大到最小处理排序数组的每个值，尝试将该值附加到两个子集之一，以使两个子集都保持凸形。首先，我们尝试将新值放置到添加了先前值的子集中。这可能会使之前添加的多个值不适合该子集 - 然后我们检查它们是否都适合其他子集。如果他们这样做 - 将它们移动到其他子集，如果没有 - 将它们保留在“顶部”子集中，但将当前值移动到其他子集。

时间复杂度

每个值最多可以从“顶部”子集中添加或删除一次，也可以最多添加到“底部”子集中一次。对于元素上的每个操作，我们只需要检查其最近的两个前任元素。这意味着步骤 2 和 3 最坏情况的时间复杂度为 O(N)。因此总体时间复杂度由步骤 1 的排序算法决定。