3

我正在做一个小实验来增加我的知识，我已经达到了我觉得我可以真正优化它的部分，但我不太确定如何做到这一点。

我有很多数字数组。（为简单起见，假设每个数组有 4 个数字：1、2、3 和 4）

  • 目标是让所有数字按升序排列（即 1-2-3-4），但这些数字都在不同的数组中打乱。

  • 较高的权重放在较大的数字上。

  • 我需要按照它们与目标的接近程度对所有这些数组进行排序。

即，4-3-2-1 将是最坏的情况。

一些示例案例：

3-4-2-1 is better than 4-3-2-1
2-3-4-1 is better than 1-4-3-2 (even though two numbers match (1 and 3). 
                                the biggest number is closer to its spot.)

因此，大数字总是优先于较小的数字。这是我的尝试：

        var tmp = from m in moves
                  let mx = m.Max()
                  let ranking = m.IndexOf(s => s == mx)
                  orderby ranking descending
                  select m;

        return tmp.ToArray();

PS IndexOf 在上面的例子中，是我写的一个扩展，它接受一个数组和表达式，并返回满足表达式的元素的索引。它是必需的，因为情况确实有点复杂，我用我的例子来简化它。

不过，我在这里尝试的问题在于，它只会按最大的数字排序，而忘记所有其他数字。它应该按最大的数字排名第一，然后是第二大，然后是第三。

此外，由于它会一遍又一遍地执行此操作几分钟，因此它应该尽可能高效。

4

2 回答 2

1

您可以实现冒泡排序，并计算必须移动数据的次数。在远离排序理想的数组上，数据移动的数量会很大。

int GetUnorderedness<T>(T[] data) where T : IComparable<T>
{
    data = (T[])data.Clone(); // don't modify the input data, 
                              // we weren't asked to actually sort.
    int swapCount = 0;
    bool isSorted;
    do
    {
        isSorted = true;
        for(int i = 1; i < data.Length; i++)
        {
            if(data[i-1].CompareTo(data[i]) > 0)
            {
                T temp = data[i];
                data[i] = data[i-1];
                data[i-1] = temp;
                swapCount++;
                isSorted = false;
            }
        }
    } while(!isSorted);
}

根据您的样本数据，这将给出与您指定的结果略有不同的结果。

一些示例案例：
3-4-2-1 优于 4-3-2-1
2-3-4-1 优于 1-4-3-2

3-4-2-1将需要 5 次交换来排序，4-3-2-1需要 6 次，这样就可以了。
2-3-4-1将需要 3，1-4-3-2也需要 3，因此这与您的预期结果不符。

该算法不会将最大的数字视为最重要的数字，这似乎是您想要的；所有数字都一视同仁。根据您的描述，您认为2-1-3-4比 好得多1-2-4-3，因为第一个在适当的位置同时具有最大和第二大数字。该算法会认为这两个相等，因为每个只需要 1 次交换来对数组进行排序。

这个算法确实有一个优点，它不仅仅是一个比较算法，每个输入都有一个离散的输出，所以你只需要为每个输入数组运行一次​​算法。

于 2012-10-07T18:48:45.210 回答
0

我希望这有帮助

var i = 0;
var temp = (from m in moves select m).ToArray();
do
{
  temp = (from m in temp
         orderby m[i] descending
         select m).ToArray();
}
while (++i < moves[0].Length);
于 2012-10-07T06:29:48.243 回答