JavaScript快速排序 [英] JavaScript quicksort

问题描述

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

I have been looking around the web for a while and I am wondering if there is a 'stable' defacto implementation of quicksort that is generally used? I can write my own but why reinvent the wheel...

推荐答案

你可以使用装饰轻松稳定不稳定的排序-sort-undecorate模式

You can easily "stabilize" an unstable sort using a decorate-sort-undecorate pattern

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];
    }
}

想法是将索引添加为最后一个排序术语所以没有两个元素现在相同，如果其他一切都相同，原始索引将成为区别因素。

the idea is to add the index as last sorting term so that no two elements are now "the same" and if everything else is the same the original index will be the discriminating factor.

这篇关于JavaScript快速排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！