模糊排序算法合并稳定性

Question

背景

我正在实现一种心理测试，用户需要选择他们喜欢的一组图片中哪一个更好。他们可以通过按A或L键来表达他们的偏好。如果图片数量很大，则比较所有可能的图片对将对个人造成相当大的负担（O(n ^ 2)）。

问题

我已经修改了归并排序算法（在这里），以显著减少比较次数。结果如下：

function mergeSort(arr)
{
    if (arr.length < 2)
        return arr;

    var middle = parseInt(arr.length / 2);
    var left   = arr.slice(0, middle);
    var right  = arr.slice(middle, arr.length);

    return merge(mergeSort(left), mergeSort(right));
}


function merge(left, right)
{
    var result = [];

    while (left.length && right.length) {
        if (getUserPreference(left[0],right[0])) {
            result.push(left.shift());
        } else {
            result.push(right.shift());
        }
    }

    while (left.length)
        result.push(left.shift());

    while (right.length)
        result.push(right.shift());

    return result;
}

函数getUserPreference将委托给用户。我运行了多次模拟（其中响应可能会意外出现“错误”，约1/3的时间，我的意思是通过按下错误的键而没有输入他们的真实偏好），根据以下标准，排序似乎表现良好：

• 输出结果与用户偏好（模拟）足够接近。
• 算法停止的时间很好。对于10个项目的列表，大约需要20个步骤。

我想知道的是，算法专家是否能告诉我这个算法有没有完全失败的可能性，无论是停止还是逼近输入解决方案。

- Joe

---

你想要的输出是什么？-- 一个排序过的列表，前N个，第一个，还是其他什么？ - eh9

不要在数字上使用 parseInt。请改用 Math.floor。 - Bergi

这个问题没有明确表述。你没有一个具有传递性的比较，而是一个任意的关系矩阵。你没有定义“近似排序”的含义。如果没有这些的数学模型，很难知道什么可能有效。并且，是的，对于任何假设总排序的排序算法，在某些情况下都会失败以终止。 - eh9

你有证据证明如果没有完全排序，归并排序将无法终止吗？我没有观察到这一点，但很想知道是否属实。 - Joe

在这种情况下，“近似排序”意味着基于位置的距离测量。 - Joe

Answer 1

这个算法完全失效的可能性有多大？

没有。无论比较有多糟糕/错误/不幸，该算法始终会停止。

该算法在很短的时间内停止。对于一个包含10个项目的列表，需要约20步。

对于10个项目，最好的情况是15次比较，最坏的情况是25次比较。一般而言，归并排序平均需要O(n log n)步骤。

这个算法完全失败以逼近输入解决方案的可能性有多大？

这取决于您对“接近用户偏好”的定义。而且，假设用户偏好是可传递关系的一个重要错误。

- Bergi