Как отсортировать массив как элементы, добавленные в Javascript?

Question

У меня есть массив объектов, элементы которых отображаются с помощью ng-repeat от AngularJS. Каждый объект имеет priority_int целого значения, и я знаю, что я могу сортировать массив порядка убывания с:

array.sort(function(a,b){ 
    return b.priority_int - a.priority_int; 
} 

В настоящее время я добавляю все в массив, перед сортировкой по priority_int в порядке убывания, а затем отображение с помощью ng-repeat.

Из любопытства, как я могу сортировать каждый раз, когда я нажимаю объект в массив?

Answer 1

Резервирование массива каждый раз, когда вы добавляете элемент, будет стоить тяжелого штрафа за выполнение, тем более что некоторые реализации по умолчанию array.sort имеют O (n^2) время выполнения для почти сортированного массива.

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

Проверить это связано ответ для получения дополнительной помощи:

Efficient way to insert a number into a sorted array of numbers?

Answer 2

Самый простой способ сделать это было бы сначала найти индекс, где новый элемент должен быть помещен. Затем вы должны добавить туда элемент.

var addToReverseSortedArray = function (arr, item) { 
    // our function to find the index of an element 
    // (or where it should be placed) 
    var search = function (a, i) { 
     var low = 0, high = a.length - 1; 
     while (low <= high) { 
      var mid = (low + high) >> 1; 
      if (a[mid] > i) low = mid + 1; 
      else if (a[mid] < i) high = mid - 1; 
      else return mid; 
     } 
     return low; 
    } 
    // Array.splice can actually splice 0 items 
    // here, we splice 0 items at index search(arr, item) 
    // and add `item` 
    arr.splice(search(arr, item), 0, item); 
    return arr; 
} 

Помните, что вышеуказанная функция основана на массиве в обратном порядке сортировки.

Примеры:

addToReverseSortedArray([5,4,3], 6); // [6,5,4,3] 
addToReverseSortedArray([1,0,0,0], 10); // [10,1,0,0,0]