Сортировка Javascript нестабильна - как мне обойти это?

Согласно функции MDN spec, функция sort() Javascript является «нестабильной» (не поддерживает порядок ввода для идентичных элементов).Сортировка Javascript нестабильна - как мне обойти это?

По иронии судьбы, похоже, что Firefox в настоящее время не реализует это, но Chrome появляется.

Это оставляет мне немного проблемы. У меня есть набор элементов для сортировки - после сортировки я хотел бы отметить их как «отсортированные», чтобы последующие попытки сортировки не тратили много времени на обнаружение, что они уже отсортированы (я могу развязать их, если что-то изменится) ,

Проблема в том, что мое решение для этого возвращает «0» в моей функции сравнения, но это означает, что я просто возвращаю «эквивалентность» для каждого элемента, и они могут (и будут) перетасовываться.

Это демонстрирует проблему (fiddle here)

<head> 
    <script> 
     var firsttime=true; 
     function test() { 
      debugger; 
      var elements = document.getElementById('test').children; 
      var sortMe = []; 
      for (var i=0; i<elements.length; i++) 
       sortMe.push(elements[i]); 
      sortMe.sort(function(a, b) { 
       if (firsttime) { 
        if (a.innerText < b.innerText) return -1; 
        else if (a.innerText > b.innerText) return 1; 
        else return 0; 
       } else { 
        return 0; 
       } 
      }); 
      var parent = document.getElementById('test'); 
      parent.innerHTML = ""; 
      for(var i = 0, l = sortMe.length; i < l; i++) { 
       parent.appendChild(sortMe[i]); 
      } 
      firsttime=false; 
     } 
    </script> 
</head> 
<body> 
<div id=test> 
    <div>B</div> 
    <div>D</div> 
    <div>A</div> 
    <div>C</div> 
    <div>E</div> 
    <div>B</div> 
    <div>D</div> 
    <div>A</div> 
    <div>C</div> 
    <div>E</div> 
    <div>B</div> 
    <div>D</div> 
    <div>A</div> 
    <div>C</div> 
    <div>E</div> 
</div> 
<input type=button onclick=test()> 
</body>

Run на Chrome вы увидите, средний элемент множества перемещаться на последующих видов - это не происходит на Mozilla (по крайней мере, не вариант I есть здесь).

Любые идеи о том, как я могу обойти это без необходимости использовать КАЖДОЕ время? Фактический вид намного сложнее и содержит 100 элементов для проверки, поэтому требуется много времени, которое я не хочу повторять без необходимости?

Редактировано для добавления: Я даже попытался использовать индекс массива, чтобы заставить сортировать массив в порядке, но даже это не работает в Chrome. Chrome, похоже, использует вариант Quicksort, который меняет элементы в массиве «только для ада»

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

источник

2013-09-02 shrewdlogarithm

Есть ли у вас дополнительный ключ сортировки, который даст вам уникальный заказ? –

В реальном приложении сортировка представляет собой сложный алгоритм, который рассматривает содержимое DIV, поэтому поиск вторичного сорта будет одинаково медленным. Я начинаю думать, что я просто отмечаю все это как «чистое» или «грязное», и просто не пытаюсь сортировать, если только это не «грязно». Я просто так думал, что могу сортировать только биты, которые Изменено ... – shrewdlogarithm

Если ... Я добавляю позицию сортировки к элементам и вместо этого использую это - это может работать, но это все еще «некоторая работа», а не «нет работы». Нестабильная вещь означает, что вам нужно делать «какую-то работу», на мой взгляд? – shrewdlogarithm

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

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

<script type="text/javascript"> 

// Return the text content of an element depending on 
// whether the textContent or innerText property is supported 
function getText(el) { 
    if (typeof el.textContent == 'string') { 
    return el.textContent; 
    } else if (typeof el.innerText == 'string') { 
    return el.innerText; 
    } else { 
    // gather text nodes and concatenate values 
    // trimmed as almost never used now 
    } 
} 


function sortEm(){ 

    // Get the elements to sort 
    var container = document.getElementById('container'); 
    var divs = container.getElementsByTagName('div'); 
    var els = []; 

    // Convert collection to an array, add the current index for the element 
    // as a data- property 
    for (var i=0, iLen=divs.length; i<iLen; i++) { 
    divs[i].setAttribute('data-sortIndex', i); 
    els[i] = divs[i]; 
    } 

    // Sort the array. If the textContent is equal, use 
    // the original index 
    els.sort(function(a, b) { 
    var aText = getText(a); 
    var bText = getText(b); 

    if (aText < bText) return -1; 
    if (aText > bText) return 1; 
    return a.getAttribute('data-SortIndex') - b.getAttribute('data-sortIndex'); 
    }) 

    // Modify the content 
    for (var j=0, jLen=els.length; j<jLen; j++) { 
    container.appendChild(els[j]); 
    } 
} 

</script> 

<div id="container"> 
    <div style="background-color: red;">0</div> 
    <div style="background-color: red;">2</div> 
    <div style="background-color: blue;">0</div> 
</div> 
<button onclick="sortEm()">Sort divs</button>

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

источник

2013-09-03 02:41:51 RobG

О, альтернатива вышесказанному - создать объект и использовать индекс textContent + как имена свойств и элементы как значения. Сортировка имен свойств (функция сортировки должна будет разбить индекс, чтобы он сравнивался как число, если все остальное равно), а затем используйте отсортированный массив, чтобы поместить элементы в правильном порядке. Этот метод позволяет избежать добавления и удаления атрибутов и свойств непосредственно на элементах (что очень важно для некоторых). – RobG

Сортировка Javascript нестабильна - как мне обойти это?

ответ

Смежные вопросы