可以从非稳定排序函数中获得稳定排序。

在排序之前，您会获得所有元素的位置。在您的排序条件中，如果两个元素相等，则按位置排序。

多田！你有一个稳定的排序。

如果你想了解更多关于这种技术以及如何实现它，我在我的博客上写了一篇关于它的文章：http : //blog.vjeux.com/2010/javascript/javascript-sorting-table.html

由于您正在寻找稳定的东西，因此应该使用归并排序。

http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

代码可以在上面的网站上找到：

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

编辑：

根据这篇文章，看起来 Array.Sort 在某些实现中使用了归并排序。

使用 ES2017 功能（如箭头函数和解构）的同一事物的更短版本：

功能

var stableSort = (arr, compare) => arr
  .map((item, index) => ({item, index}))
  .sort((a, b) => compare(a.item, b.item) || a.index - b.index)
  .map(({item}) => item)

它接受输入数组和比较函数：

stableSort([5,6,3,2,1], (a, b) => a - b)

它还返回新数组，而不是像内置的Array.sort()函数那样进行就地排序。

测试

如果我们采用以下input数组，最初按以下排序weight：

// sorted by weight
var input = [
  { height: 100, weight: 80 },
  { height: 90, weight: 90 },
  { height: 70, weight: 95 },
  { height: 100, weight: 100 },
  { height: 80, weight: 110 },
  { height: 110, weight: 115 },
  { height: 100, weight: 120 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 100, weight: 135 },
  { height: 75, weight: 140 },
  { height: 70, weight: 140 }
]

然后height使用stableSort以下方法对其进行排序：

stableSort(input, (a, b) => a.height - b.height)

结果是：

// Items with the same height are still sorted by weight 
// which means they preserved their relative order.
var stable = [
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 70, weight: 140 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 80 },
  { height: 100, weight: 100 },
  { height: 100, weight: 120 },
  { height: 100, weight: 135 },
  { height: 110, weight: 115 }
]

但是input使用内置Array.sort()（在 Chrome/NodeJS 中）对相同的数组进行排序：

input.sort((a, b) => a.height - b.height)

返回：

var unstable = [
  { height: 70, weight: 140 },
  { height: 70, weight: 95 },
  { height: 70, weight: 125 },
  { height: 70, weight: 130 },
  { height: 75, weight: 140 },
  { height: 80, weight: 110 },
  { height: 90, weight: 90 },
  { height: 100, weight: 100 },
  { height: 100, weight: 80 },
  { height: 100, weight: 135 },
  { height: 100, weight: 120 },
  { height: 110, weight: 115 }
]

资源

• 维基百科
• MDN
• JSFiddle

更新

Array.prototype.sort 现在稳定在 V8 v7.0 / Chrome 70！

以前，V8 对超过 10 个元素的数组使用不稳定的 QuickSort。现在，我们使用稳定的 TimSort 算法。

来源

我知道这个问题已经回答了一段时间，但我的剪贴板中碰巧有一个很好的稳定的 Array 和 jQuery 合并排序实现，所以我会分享它，希望未来的搜索者可能会发现它有用。

它允许您像正常Array.sort实现一样指定自己的比较函数。

执行

// Add stable merge sort to Array and jQuery prototypes
// Note: We wrap it in a closure so it doesn't pollute the global
//       namespace, but we don't put it in $(document).ready, since it's
//       not dependent on the DOM
(function() {

  // expose to Array and jQuery
  Array.prototype.mergeSort = jQuery.fn.mergeSort = mergeSort;

  function mergeSort(compare) {

    var length = this.length,
        middle = Math.floor(length / 2);

    if (!compare) {
      compare = function(left, right) {
        if (left < right)
          return -1;
        if (left == right)
          return 0;
        else
          return 1;
      };
    }

    if (length < 2)
      return this;

    return merge(
      this.slice(0, middle).mergeSort(compare),
      this.slice(middle, length).mergeSort(compare),
      compare
    );
  }

  function merge(left, right, compare) {

    var result = [];

    while (left.length > 0 || right.length > 0) {
      if (left.length > 0 && right.length > 0) {
        if (compare(left[0], right[0]) <= 0) {
          result.push(left[0]);
          left = left.slice(1);
        }
        else {
          result.push(right[0]);
          right = right.slice(1);
        }
      }
      else if (left.length > 0) {
        result.push(left[0]);
        left = left.slice(1);
      }
      else if (right.length > 0) {
        result.push(right[0]);
        right = right.slice(1);
      }
    }
    return result;
  }
})();

示例用法

var sorted = [
  'Finger',
  'Sandwich',
  'sandwich',
  '5 pork rinds',
  'a guy named Steve',
  'some noodles',
  'mops and brooms',
  'Potato Chip Brand® chips'
].mergeSort(function(left, right) {
  lval = left.toLowerCase();
  rval = right.toLowerCase();

  console.log(lval, rval);
  if (lval < rval)
    return -1;
  else if (lval == rval)
    return 0;
  else
    return 1;
});

sorted == ["5 pork rinds", "a guy named Steve", "Finger", "mops and brooms", "Potato Chip Brand® chips", "Sandwich", "sandwich", "some noodles"];

无论本机实现如何，您都可以使用以下函数执行稳定的排序，基于此答案中的断言。

请注意，从 ECMAScript 2019 开始，规范要求内置sort()方法执行稳定的排序。考虑到这一点，如果您需要支持不符合规范的旧浏览器，则如下所示的显式稳定排序功能仍然适用。

// ECMAScript 5 implementation
function stableSort(array, compareFunction) {
  'use strict';

  var length = array.length;
  var indices = new Uint32Array(length);
  var i;
  var slice;

  // reference values by indices
  for (i = 0; i < length; ++i) {
    indices[i] = i;
  }

  // sort with fallback based on indices
  indices.sort(function stableCompareFunction(compareFunction, a, b) {
    var order = Number(compareFunction(this[a], this[b]));
    return order || a - b;
  }.bind(array, compareFunction));

  slice = array.slice();

  // re-order original array to stable sorted values
  for (i = 0; i < length; ++i) {
    array[i] = slice[indices[i]];
  }

  return array;
}

// usage
const array = Array(500000).fill().map(() => Number(Math.random().toFixed(4)));

const alwaysEqual = () => 0;
const isUnmoved = (value, index) => value === array[index];

// not guaranteed to be stable before ES2019
console.log(
  'sort() stable?',
  array.slice().sort(alwaysEqual).every(isUnmoved)
);
// guaranteed to be stable
console.log(
  'stableSort() stable?',
  stableSort(array.slice(), alwaysEqual).every(isUnmoved)
);

// performance using realistic scenario with unsorted big data
function time(arraySlice, algorithm, compare) {
  var start;
  var stop;

  start = performance.now();
  algorithm(arraySlice, compare);
  stop = performance.now();

  return stop - start;
}

const ascending = (a, b) => a - b;

const msSort = time(array.slice(), (array, compare) => array.sort(compare), ascending);
const msStableSort = time(array.slice(), (array, compare) => stableSort(array, compare), ascending);

console.log('sort()', msSort.toFixed(3), 'ms');
console.log('stableSort()', msStableSort.toFixed(3), 'ms');
console.log('sort() / stableSort()', (100 * msSort / msStableSort).toFixed(3) + '%');

运行上面实现的性能测试，stableSort()运行速度似乎sort()是 Google Chrome 和 Microsoft Edge 88 版的速度的 72% 。

使用.bind()内联函数中stableSort()用来避免在每次调用不必要的作用域引用显著提高相对性能。

在实践中，这不再有什么不同，因为现代引擎现在会自动执行此优化，但无论如何它仍留在实现中，以便继续提高未附带此优化的旧浏览器的性能。