<p>я знаю, что на этот вопрос уже был дан ответ, но у меня в буфере обмена есть хорошая стабильная реализация сортировки слиянием для array и jquery, поэтому я поделюсь ею в надежде, что некоторые будущие поисковики могут найти ее полезной.</p><p>это позволяет вам указать свою собственную функцию сравнения, как в обычной реализации <code>array.sort</code>.</p><h2>реализация</h2><pre><code>// 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; } })(); </code></pre><h2>пример использования</h2><pre><code>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"]; </code></pre>

<p>вы можете использовать следующий polyfill для реализации стабильной сортировки независимо от нативной реализации, основываясь на утверждении <a href="https://stackoverflow.com/a/2085225/1541563">в этом ответе</a> :</p><p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false"> <div class="snippet-code"> <pre class="snippet-code-js lang-js prettyprint-override"><code>// 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) + '%')</code></pre> </div> </div> </p><p>при выполнении тестов производительности, реализованных выше, <code>stablesort()</code> работает на 57% скорости <code>sort()</code> в chrome версии 59-61.</p><p>использование <code>.bind(comparefunction)</code> в обернутой анонимной функции в <code>stablesort()</code> повысило эту относительную производительность примерно с 38%, избегая ненужной ссылки на область действия на <code>comparefunction</code> при каждом вызове, вместо этого назначив ее контексту.</p><h3>обновление</h3><p>заменен троичный оператор на логическое короткое замыкание, которое, как правило, работает лучше в среднем (по-видимому, разница в эффективности составляет 2-3%).</p>

<p>следующее сортирует предоставленный массив, применяя предоставленную функцию сравнения, возвращая исходное сравнение индекса, когда функция сравнения возвращает 0:</p><pre><code>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; } </code></pre><p>в приведенном ниже примере сортировка массива имен по фамилии с сохранением порядка одинаковых фамилий:</p><p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false"> <div class="snippet-code"> <pre class="snippet-code-js lang-js prettyprint-override"><code>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); });</code></pre> </div> </div> </p>

<p>я должен сортировать многомерные массивы по произвольному столбцу, а затем по другому. я использую эту функцию для сортировки:</p><pre><code>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; }); } </code></pre><p>обратите внимание, что ary.sort никогда не возвращает ноль, поэтому некоторые реализации функции «sort» принимают решения, которые могут быть неверными. </p><p>это тоже чертовски быстро.</p>

<p>поэтому мне понадобилась стабильная сортировка для моего приложения react + redux, и ответ vjeux здесь помог мне. тем не менее, мое (общее) решение кажется отличным от других, которые я вижу здесь до сих пор, поэтому я делюсь им на случай, если у кого-то еще есть соответствующий вариант использования:</p><ul> <li>я действительно хочу иметь что-то похожее на api <code>sort()</code>, где я могу передать функцию компаратора.</li> <li>иногда я<em> могу </em>сортировать на месте, а иногда мои данные неизменны (потому что redux), и вместо этого мне нужна отсортированная копия. поэтому мне нужна стабильная функция сортировки для каждого варианта использования.</li> <li>es2015.</li> </ul><p>мое решение состоит в том, чтобы создать типизированный массив <code>indices</code>, а затем использовать функцию сравнения для сортировки этих<em> индексов </em>на основе сортируемого массива. затем мы можем использовать отсортированный <code>indices</code> для сортировки исходного массива или создания отсортированной копии за один проход. если это сбивает с толку, подумайте об этом следующим образом: где вы обычно передаете функцию сравнения, например:</p><pre><code>(a, b) => { /* some way to compare a and b, returning -1, 0, or 1 */ }; </code></pre><p>теперь вы вместо этого используете:</p><pre><code>(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 } </code></pre><p>скорость это хорошо; это в основном встроенный алгоритм сортировки, плюс два линейных прохода в конце и один дополнительный уровень косвенных косвенных указателей.</p><p>рад получить отзывы об этом подходе. вот моя полная реализация этого:</p><pre><code>/** * - `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; } </code></pre>

<p>вот как можно расширить объект array по умолчанию в js с помощью метода-прототипа, использующего <strong> <a href="https://en.wikipedia.org/wiki/merge\_sort">merge sort</a> </strong>. этот метод позволяет сортировать по определенному ключу (первый параметр) и заданному порядку («asc»/«desc» в качестве второго параметра)</p><p><div class="snippet" data-lang="js" data-hide="false" data-console="true" data-babel="false"> <div class="snippet-code"> <pre class="snippet-code-js lang-js prettyprint-override"><code>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) } }</code></pre> </div> </div> </p><p>вы можете проверить это самостоятельно, поместив приведенный выше фрагмент в консоль браузера, а затем попытайтесь:</p><pre class="lang-js prettyprint-override"><code>var x = [2,76,23,545,67,-9,12]; x.mergesort(); //[-9, 2, 12, 23, 67, 76, 545] x.mergesort(undefined, 'desc'); //[545, 76, 67, 23, 12, 2, -9] </code></pre><p>или порядок на основе определенного поля в массиве объектов:</p><pre class="lang-js prettyprint-override"><code>var y = [ {starttime: 100, value: 'cat'}, {starttime: 5, value: 'dog'}, {starttime: 23, value: 'fish'}, {starttime: 288, value: 'pikachu'} ] y.mergesort('starttime'); y.mergesort('starttime', 'desc'); </code></pre>

<p>подсчет сортировки выполняется быстрее, чем сортировка слиянием (она выполняется за время o(n)) и предназначена для использования с целыми числами.</p><pre><code>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 } </code></pre><p>пример:</p><pre><code>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 </code></pre>