1

我有一个唯一整数列表，我想对它们进行排序，以便下一个整数总是与其余整数尽可能远，这是可能的。

例如，{1,2,3,4,5,6,7,8,9} => {1,9,6,2,8,3,7,4,5}

而且我需要做得非常快。

目前，我正在这样做：

    static double GetDistanceIndex(int value, List<int> others)
    {
        double result=0;
        foreach (var other in others)
        {
            result += Math.Sqrt(Math.Abs(other - value));
        }

        return result;
    }

    static List<int> Sort(List<int> items, int initialValue)
    {
        items = items.ToList();
        List<int> result=new List<int>();


        lock (rnd)
        {
            while (true)
            {
                result.Add(initialValue);
                items.Remove(initialValue);
                if (items.Count == 0)
                {
                    break;
                }
                Dictionary<double, List<int>> distances = new Dictionary<double, List<int>>();
                foreach (var item in items)
                {
                    var d = GetDistanceIndex(item, result);
                    if (!distances.ContainsKey(d))
                    {
                        distances[d] = new List<int>();
                    }
                    distances[d].Add(item);
                }

                var max = distances.Keys.Max();
                var l = distances[max];
                //if (l.Count == 1)
                //{
                //    initialValue = l[0];
                //}
                //else
                //{
                initialValue = l[rnd.Next(l.Count)];
                //} 
            } 
        }

        return result;
    }

但问题是，像这样实现的算法对于大型数组的运行速度非常慢。

任何人都可以向我建议一个更好的方法吗？

更新

这是一个更好的描述做了什么：

{1,2,3,4,5,6,7,8,9}=>

  1. 初始种子：1。真的，它可以是任何数字。我们可以选择 5，得到类似 {5,9,1,2,8,3,7,6,4}
  2. 从提供的数组中，9 是距离 1 最远的距离
  3. 因为在列表中，所有数字都与 1 和 9 等距，我们可以选择其中任何一个。我用rand来选择6。
  4. 现在我们正在寻找离 {1,9,6} 最远的数字。选择 2 是因为abs(2-1)+abs(2-9)+abs(2-6)=12and 大于abs(3-1)+abs(3-9)+abs(3-6)=11or abs(4-1)+abs(4-9)+abs(4-6)=10or abs(8-1)+abs(8-9)+abs(8-6)=10 or or abs(7-1)+abs(7-9)+abs(7-6)=9orabs(5-1)+abs(5-9)+abs(5-6)=9
  5. ETC

更新 1

我正在使用此算法从固定数量的备选方案中选择尽可能不同的数字

更新 2

Dukeling 在他的回答中向我指出，{1,9,2,8,3,7,4,6​​,5} 也符合我的要求。这是真的，这是我的错误。我希望数字尽可能地间隔开，而 3d 数字非常接近第一个数字并不是我想要的。所以我正在更新距离函数以反映这一点

4

2 回答 2

1

{1,9,2,8,3,7,4,6,5}似乎符合您的要求，并且很容易生成。

只需按升序/降序对数字进行排序（如果尚未完成）。

然后从后面和前面迭代，在它们之间交替，直到我们到达中间。此步骤以线性时间运行。

于 2013-10-06T12:28:26.483 回答
1

[编辑以符合新的距离函数]

重复调用 GetDistanceIndex() 是在做不必要的工作。请注意，您不需要每次都从头开始总结所有内容。如果你有这样的数组：

[a，b，c，d，…………，x]

其中a、b、c、d已经排序，那么，当你插入一个新元素'e'时，未排序集合中任意位置'x'与排序集合中所有其他数字的距离函数之和仅增加 sqrt(abs(xe))。您不必从头开始重新计算整个总和。

所以这里是你可以如何优化它：使用某种方法来存储一对（数字，距离）。例如，如果您使用 C，您可以创建一个结构数组，其中包含两个整数、值本身以及到排序集的距离。在每一步，您都会遍历不在排序集中的每一对（数字，距离）并更新其距离属性。您可以同时跟踪最大值。一些伪代码：

  • 创建一个辅助缓冲区 S，用于保存 (number, distance) 对；

  • 在 S 中插入与 initialValue 不同的每个数字 x，距离 = sqrt(abs(initialValue - x))。同时跟踪最大值 m；

  • 在每个步骤中，选择 m 并将其移动到数组的排序部分。从 S 中删除它。然后，转到 S 中的每个元素 y 并将 sqrt(abs(y.number-m.number)) 添加到 y 的距离。同样，您需要在执行此操作时跟踪最大值。不断重复，直到每个元素都被排序。

这不是一个绝妙的解决方案。它在 O(n^2) 中运行，但您当前的算法在 O(n^3) 中运行，因为 GetDistanceIndex() 总是从头开始。另外，我不会使用列表和字典，尝试使用简单的数组，以便您可以在恒定时间内访问和删除元素。从列表中删除可能效率低下，它永远不会比 O(log(n)) 更好。

目前，这是我能想到的唯一优化，也许有人会有更好的主意。

于 2013-10-06T12:42:07.890 回答