javascript中快速稳定的排序算法实现

Question

javascript中快速稳定的排序算法实现我正在寻找一个大约200-300个对象的数组，对特定的键和给定的顺序（asc / desc）进行排序。结果的顺序必须一致且稳定。什么是最好的算法，你能提供一个在javascript中实现它的例子吗？谢谢！

Answer 1

我知道这个问题已经回答了一段时间，但我碰巧在我的剪贴板中有一个很好的稳定合并排序实现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"];