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

Question

我正在寻找一个大约200-300个对象的数组,对特定的键和给定的顺序(asc/desc)进行排序.结果的顺序必须一致且稳定.

什么是最好的算法,你能提供一个在javascript中实现它的例子吗？

谢谢!

Answer 1

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

在排序之前,您将获得所有元素的位置.在排序条件下,如果两个元素相等,则按位置排序.

田田!你有一个稳定的排序.

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

Answer 2

由于您正在寻找稳定的东西,合并排序应该这样做.

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在一些实现中使用合并排序.

Answer 3

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

Answer 4

使用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使用不稳定的QuickSort用于具有10个以上元素的阵列.现在,我们使用稳定的TimSort算法.

资源

Answer 5

根据本答案中的断言,您可以使用以下polyfill实现稳定排序,而不管本机实现如何:

// ECMAScript 5 polyfill
Object.defineProperty(Array.prototype, 'stableSort', {
  configurable: true,
  writable: true,
  value: function stableSort (compareFunction) {
    'use strict'

    var length = this.length
    var entries = Array(length)
    var index

    // wrap values with initial indices
    for (index = 0; index < length; index++) {
      entries[index] = [index, this[index]]
    }

    // sort with fallback based on initial indices
    entries.sort(function (a, b) {
      var comparison = Number(this(a[1], b[1]))
      return comparison || a[0] - b[0]
    }.bind(compareFunction))

    // re-map original array to stable sorted values
    for (index = 0; index < length; index++) {
      this[index] = entries[index][1]
    }
    
    return this
  }
})

// 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
console.log('sort() stable?', array
  .slice()
  .sort(alwaysEqual)
  .every(isUnmoved)
)
// guaranteed to be stable
console.log('stableSort() stable?', array
  .slice()
  .stableSort(alwaysEqual)
  .every(isUnmoved)
)

// performance using realistic scenario with unsorted big data
function time(arrayCopy, algorithm, compare) {
  var start
  var stop
  
  start = performance.now()
  algorithm.call(arrayCopy, compare)
  stop = performance.now()
  
  return stop - start
}

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

const msSort = time(array.slice(), Array.prototype.sort, ascending)
const msStableSort = time(array.slice(), Array.prototype.stableSort, 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()Chrome版本59-61的57%的速度运行.

使用.bind(compareFunction)包装的匿名函数通过将每个调用分配给上下文而stableSort()避免compareFunction对每个调用执行不必要的范围引用,从而将相对性能提高了约38%.

更新

将三元运算符更改为逻辑短路,这通常会在平均情况下表现更好(似乎效率会产生2-3%的差异).

Answer 6

下面通过应用提供的compare函数对提供的数组进行排序,当compare函数返回0时返回原始索引比较:

function stableSort(arr, compare) {
    var original = arr.slice(0);

    arr.sort(function(a, b){
        var result = compare(a, b);
        return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
    });

    return arr;
}

以下示例按姓氏对名称数组进行排序,保留相同姓氏的顺序:

var names = [
	{ surname: "Williams", firstname: "Mary" },
	{ surname: "Doe", firstname: "Mary" }, 
	{ surname: "Johnson", firstname: "Alan" }, 
	{ surname: "Doe", firstname: "John" }, 
	{ surname: "White", firstname: "John" }, 
	{ surname: "Doe", firstname: "Sam" }
]

function stableSort(arr, compare) {
    var original = arr.slice(0);

    arr.sort(function(a, b){
        var result = compare(a, b);
        return result === 0 ? original.indexOf(a) - original.indexOf(b) : result;
    });
	
    return arr;
}

stableSort(names, function(a, b) { 
	return a.surname > b.surname ? 1 : a.surname < b.surname ? -1 : 0;
})

names.forEach(function(name) {
	console.log(name.surname + ', ' + name.firstname);
});