Так как вы ищете что-то стабильное, сортировка слиянием следует делать.

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

EDIT:

по этому post, похоже на массив.Вроде в некоторых реализациях используется сортировка слиянием.

Я знаю, что на этот вопрос был дан ответ в течение некоторого времени, но у меня есть хорошая стабильная реализация сортировки слиянием для массива и 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 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() Кажется, работает примерно на 57% от скорости sort() на Chrome версии 59-61.

используя .bind(compareFunction) на обернутой анонимной функции внутри stableSort() повысил эту относительную производительность примерно на 38% избегая ненужной ссылки на область compareFunction при каждом вызове, назначая его контексту вместо этого.

обновление

изменен тернарный оператор на логическое короткое замыкание, которое имеет тенденцию работать лучше в среднем (по-видимому, разница в эффективности составляет 2-3%).

несколько более короткая версия того же самого, используя функции 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)

он также возвращает новый массив вместо того, чтобы делать сортировку на месте, как встроенный массив.сортировка ()

следующий сортирует поставляемый массив, применяя поставляемую функцию сравнения, возвращая исходное сравнение индекса, когда функция сравнения возвращает 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);
});

вот стабильная реализация. Он работает с использованием собственной сортировки, но в случаях, когда элементы сравниваются как равные, вы разрываете связи, используя исходную позицию индекса.

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

не тщательный тест

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

еще один ответ намекнул на это, но не опубликовал кодез.

но, его не быстро в соответствии с моим benchmark. Я изменил merge sort impl принять пользовательскую функцию компаратора, и он был гораздо быстрее.

вы также можете использовать Timsort. Это действительно сложный алгоритм (400 + строк, поэтому здесь нет исходного кода), поэтому см. Википедии или использовать одну из существующих реализаций JavaScript:

реализация GPL 3. Упаковано как массив.прототип.timsort. Похоже, это точная перепись кода Java.

реализация общественного достояния подразумевается как учебник, пример кода показывает только его использование с целые.

Timsort - это высокооптимизированный гибрид сортировки mergesort и shuffle и является алгоритмом сортировки по умолчанию в Python и Java (1.7+). Это сложный алгоритм, так как он использует различные алгоритмы для многих специальных случаях. Но в результате это очень быстро при самых разных обстоятельствах.

простой один 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));

Счетная сортировка выполняется быстрее, чем сортировка слиянием (она выполняется за 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

Я должен отсортировать многомерные массивы по произвольному столбцу, а затем по другому. Я использую эту функцию для сортировки:

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

обратите внимание, что Ары.сортировка никогда не возвращает ноль, поэтому некоторые реализации функции "сортировка" принимают решения, которые могут быть неправильными.

Это тоже чертовски быстро.

вот как вы можете расширить объект массива JS по умолчанию с помощью метода прототипа, использующего ОБЪЕДИНИТЬ СОРТИРОВКУ. Этот метод позволяет сортировать по определенному ключу (первый параметр) и заданному порядку ('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)
  }
}

вы можете проверить это самостоятельно, опустив приведенный выше фрагмент в консоль браузера, а затем попробовать:

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]

или порядок на основе определенного поля в массиве объекты:

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');

поэтому мне нужна была стабильная сортировка для моего приложения React+Redux, и ответ Vjeux здесь помог мне. Однако мое (общее) решение кажется отличным от других, которые я вижу здесь до сих пор, поэтому я делюсь им, если у кого-то еще есть соответствующий прецедент:

• Я просто хочу иметь что-то похожее на sort() API, где я могу передать функцию компаратора.
• Иногда можете сортировать на месте, и иногда мои данные неизменяемы (потому что Redux) и я нужна отсортированная копия вместо этого. Поэтому мне нужна стабильная функция сортировки для каждого варианта использования.
• ES2015.

мое решение-создать типизированный массив indices, затем используйте функцию сравнения для сортировки этих показатели на основе массива для сортировки. Тогда мы можем использовать сортированный indices для сортировки исходного массива или создания отсортированной копии за один проход. Если это сбивает с толку, подумайте об этом так: где вы обычно передаете функцию сравнения например:

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

скорость хорошая; это в основном встроенный алгоритм сортировки, плюс два линейных прохода в конце и один дополнительный слой косвенных накладных расходов указателя.

рад получить обратную связь по этому подходу. Вот моя полная реализация этого:

/**
 * - `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;
}