javascript - JavaScript快速排序

我已经在网上浏览了一段时间，我想知道是否存在通常使用的“稳定”的快速排序事实上的实现？我可以自己写，但为什么要重新发明轮子呢？

最佳答案

您可以使用decorate-sort-unecorate模式轻松地“稳定”不稳定的排序

function stableSort(v, f)
{
    if (f === undefined) {
        f = function(a, b) {
            a = ""+a; b = ""+b;
            return a < b ? -1 : (a > b ? 1 : 0);
        }
    }
    var dv = [];
    for (var i=0; i<v.length; i++) {
        dv[i] = [v[i], i];
    }
    dv.sort(function(a, b){
              return f(a[0], b[0]) || (a[1] - b[1]);
            });
    for (var i=0; i<v.length; i++) {
        v[i] = dv[i][0];
    }
}

想法是将索引添加为最后一个排序项，以使现在没有两个元素“相同”，并且如果其他所有元素都相同，则原始索引将成为区分因素。