在javascript中实现快速稳定的sortingalgorithm

我正在寻找sorting约200-300对象的数组，sorting一个特定的键和给定的顺序（asc / desc）。 结果顺序必须一致和稳定。

什么是最好的algorithm使用，你能提供一个在JavaScript实现的例子吗？

谢谢！

Answer 1

从非稳定的分类function可以得到稳定的分类。

在sorting之前，您将获得所有元素的位置。 在你的sorting条件中，如果两个元素是相等的，那么你按sortingsorting。

田田！ 你有一个稳定的sorting。

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

Answer 2

既然你正在寻找稳定的东西，合并sorting应该做的。

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

代码可以在上面的网站find：

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在一些实现中使用合并sorting。

Answer 3

我知道这个问题已经回答了一段时间了，但是碰巧在剪贴板中有一个很好的Array和jQuery的合并sorting实现，所以我会分享它，希望未来的某些search者可能会觉得它有用。

它允许你像正常的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

您可以使用下面的polyfill来实现一个稳定的sorting，不pipe原生实现如何，基于这个答案中的断言：

 // 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) + '%') 

Answer 5

这是一个稳定的实现。 它通过使用本地sorting工作，但在元素比较相等的情况下，使用原始索引位置断开连接。

 function stableSort(arr, cmpFunc) { //wrap the arr elements in wrapper objects, so we can associate them with their origional starting index position var arrOfWrapper = arr.map(function(elem, idx){ return {elem: elem, idx: idx}; }); //sort the wrappers, breaking sorting ties by using their elements orig index position arrOfWrapper.sort(function(wrapperA, wrapperB){ var cmpDiff = cmpFunc(wrapperA.elem, wrapperB.elem); return cmpDiff === 0 ? wrapperA.idx - wrapperB.idx : cmpDiff; }); //unwrap and return the elements return arrOfWrapper.map(function(wrapper){ return wrapper.elem; }); } 

一个不彻底的testing

 var res = stableSort([{a:1, b:4}, {a:1, b:5}], function(a, b){ return aa - ba; }); console.log(res); 

另一个答案暗示了这一点，但没有发表codez。

但是，根据我的基准 ，它并不快。 我修改了一个合并sortingimpl来接受自定义的比较函数，而且速度更快。

Answer 6

你也可以使用Timsort：

GPL 3的JavaScript实现 。 打包为Array.prototype.timsort。 似乎是Java代码的精确重写。

公有领域的实现作为一个教程，示例代码只显示了它与整数的用法。

Timsort是一种高度优化的mergesort和shufflesorting混合，是Python和Java（1.7+）中的默认sortingalgorithm。 这是一个复杂的algorithm，因为它在许多特殊情况下使用不同的algorithm。 但是，结果在各种各样的情况下都是非常快的。 请参阅： https ： //en.wikipedia.org/wiki/Timsort

Answer 7

计数sorting比合并sorting更快（它在O（n）时间执行），它的目的是用于整数。

 Math.counting_sort = function (m) { var i var j var k var step var start var Output var hash k = m.length Output = new Array () hash = new Array () // start at lowest possible value of m start = 0 step = 1 // hash all values i = 0 while ( i < k ) { var _m = m[i] hash [_m] = _m i = i + 1 } i = 0 j = start // find all elements within x while ( i < k ) { while ( j != hash[j] ) { j = j + step } Output [i] = j i = i + 1 j = j + step } return Output } 

例：

 var uArray = new Array ()<br/> var sArray = new Array ()<br/><br/> uArray = [ 10,1,9,2,8,3,7,4,6,5 ]<br/> sArray = Math.counting_sort ( uArray ) // returns a sorted array 

Answer 8

一个简单的mergeSort从http://www.stoimen.com/blog/2010/07/02/friday-algorithms-javascript-merge-sort/

 var a = [34, 203, 3, 746, 200, 984, 198, 764, 9]; 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; } console.log(mergeSort(a)); 

Answer 9

我必须由一个任意的列，然后由另一个sortingmultidimensional array。 我使用这个函数来sorting：

 function sortMDArrayByColumn(ary, sortColumn){ //Adds a sequential number to each row of the array //This is the part that adds stability to the sort for(var x=0; x<ary.length; x++){ary[x].index = x;} ary.sort(function(a,b){ if(a[sortColumn]>b[sortColumn]){return 1;} if(a[sortColumn]<b[sortColumn]){return -1;} if(a.index>b.index){ return 1; } return -1; }); } 

请注意，ary.sort永远不会返回零，这是“sort”函数的某些实现做出可能不正确的决定的地方。

这也相当快。

Answer 10

以下是如何使用MERGE SORT扩展JS默认Array对象的原型方法。 这个方法允许在一个特定的键（第一个参数）和一个给定的顺序（'asc'/'desc'作为第二个参数）

 Array.prototype.mergeSort = function(sortKey, direction){ var unsortedArray = this; if(unsortedArray.length < 2) return unsortedArray; var middle = Math.floor(unsortedArray.length/2); var leftSubArray = unsortedArray.slice(0,middle).mergeSort(sortKey, direction); var rightSubArray = unsortedArray.slice(middle).mergeSort(sortKey, direction); var sortedArray = merge(leftSubArray, rightSubArray); return sortedArray; function merge(left, right) { var combined = []; while(left.length>0 && right.length>0){ var leftValue = (sortKey ? left[0][sortKey] : left[0]); var rightValue = (sortKey ? right[0][sortKey] : right[0]); combined.push((direction === 'desc' ? leftValue > rightValue : leftValue < rightValue) ? left.shift() : right.shift()) } return combined.concat(left.length ? left : right) } } 

Answer 11

所以我需要一个稳定的sorting，我的React + Redux应用程序，Vjeux的答案在这里帮助我。 不过，我的（通用）解决scheme似乎与我目前在这里看到的其他解决scheme不同，所以我分享它以防其他人有匹配的用例：

• 我真的只是想有类似sort() API，我可以通过比较函数。
• 有时我可以就地sorting，有时我的数据是不可变的（因为Redux），我需要一个有序的副本。 所以我需要一个稳定的sortingfunction，每个用例。
• ES2015。

我的解决scheme是创build一个indicestypes的数组，然后使用比较函数来sorting这些索引基于待sorting的数组。 然后我们可以使用sorting后的indices来sorting原始数组或者一次性创build一个已sorting的副本。 如果这是令人困惑的，可以这样想：在哪里通常会传递一个比较函数，如：

 (a, b) => { /* some way to compare a and b, returning -1, 0, or 1 */ }; 

你现在改用：

 (i, j) => { let a = arrayToBeSorted[i], b = arrayToBeSorted[j]; /* some way to compare a and b, returning -1 or 1 */ return i - j; // fallback when a == b } 

速度不错; 它基本上是内置的sortingalgorithm，最后加上两个线性遍，还有一个额外的指针间接开销层。

很高兴收到关于这种方法的反馈。 这是我的全面实施它：

 /** * - `array`: array to be sorted * - `comparator`: closure that expects indices `i` and `j`, and then * compares `array[i]` to `array[j]` in some way. To force stability, * end with `i - j` as the last "comparison". * * Example: * ``` * let array = [{n: 1, s: "b"}, {n: 1, s: "a"}, {n:0, s: "a"}]; * const comparator = (i, j) => { * const ni = array[i].n, nj = array[j].n; * return ni < nj ? -1 : * ni > nj ? 1 : * i - j; * }; * stableSortInPlace(array, comparator); * // ==> [{n:0, s: "a"}, {n:1, s: "b"}, {n:1, s: "a"}] * ``` */ function stableSortInPlace(array, comparator) { return sortFromIndices(array, findIndices(array, comparator)); } function stableSortedCopy(array, comparator){ let indices = findIndices(array, comparator); let sortedArray = []; for (let i = 0; i < array.length; i++){ sortedArray.push(array[indices[i]]); } return sortedArray; } function findIndices(array, comparator){ // Assumes we don't have to worry about sorting more than // 4 billion elements; if you know the upper bounds of your // input you could replace it with a smaller typed array let indices = new Uint32Array(array.length); for (let i = 0; i < indices.length; i++) { indices[i] = i; } // after sorting, `indices[i]` gives the index from where // `array[i]` should take the value from, so to sort // move the value at at `array[indices[i]]` to `array[i]` return indices.sort(comparator); } // If I'm not mistaken this is O(2n) - each value is moved // only once (not counting the vacancy temporaries), and // we also walk through the whole array once more to check // for each cycle. function sortFromIndices(array, indices) { // there might be multiple cycles, so we must // walk through the whole array to check. for (let k = 0; k < array.length; k++) { // advance until we find a value in // the "wrong" position if (k !== indices[k]) { // create vacancy to use "half-swaps" trick, // props to Andrei Alexandrescu let v0 = array[k]; let i = k; let j = indices[k]; while (j !== k) { // half-swap next value array[i] = array[j]; // array[i] now contains the value it should have, // so we update indices[i] to reflect this indices[i] = i; // go to next index i = j; j = indices[j]; } // put original array[k] back in // and update indices array[i] = v0; indices[i] = i; } } return array; } 

Answer 12

内置的sortingfunction呢？ http://www.w3schools.com/jsref/jsref_sort.asp