Реализация алгоритма быстрой стабильной сортировки в javascript - PullRequest
Новая
       53

Реализация алгоритма быстрой стабильной сортировки в javascript

93 голосов
/ 15 сентября 2009

Я хочу отсортировать массив из 200-300 объектов, сортируя по определенному ключу и заданному порядку (asc / desc). Порядок результатов должен быть последовательным и стабильным.

Какой алгоритм лучше всего использовать, и не могли бы вы привести пример его реализации в javascript?

Спасибо!

Ответы [ 13 ]

0 голосов
/ 13 июля 2016

Вот как вы можете расширить объект Array по умолчанию в JS с помощью метода-прототипа, используя MERGE SORT . Этот метод позволяет сортировать по определенному ключу (первый параметр) и заданному порядку («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');
0 голосов
/ 25 июня 2014

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

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" принимают решения, которые могут быть неправильными.

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

0 голосов
/ 25 июля 2011

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