JavaScript сортировка по номерам

Question

Следующая программа (взята из учебника) печатает числа в массиве в порядке от самого низкого до самого высокого. В этом случае результат будет 2,4,5,13,31

Мой вопрос касается параметров "a" и "b" для функции compareNumbers. Когда функция вызывается в numArray.sort(compareNumbers), какие числа будут параметрами a и b для функции. Это просто двигаться по массиву. Например, начать с a=13 и b=2? После этого функция запускается снова, сравнивая a = 2 и b = 31? или будет ли сравнивать a=31 и b=4?

Может кто-нибудь объяснить, как работает эта часть, а также как ей удается сортировать их по возрастанию? Я не вижу, как функции удается выполнить необходимые вычисления над числами в массиве.

function compareNumbers(a,b) {
  return a - b;
}

var numArray = [13,2,31,4,5];
alert(numArray.sort(compareNumbers));

Answer 1

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

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

Интересно, что на самом деле вы можете использовать функцию сравнения, чтобы визуализировать, как работает сортировка, или перепроектировать алгоритм сортировки! Веб-сайт sortviz.org содержит множество визуализаций алгоритмов сортировки, сгенерированных путем передачи пользовательских компараторов в функции сортировки, которые отслеживают позиции каждого элемента. Если вы посмотрите, то увидите, как по-разному каждый алгоритм перемещает свои элементы.

Еще интереснее то, что вы можете использовать функции сравнения в качестве наступательного оружия! Некоторые алгоритмы сортировки, а именно быстрая сортировка, имеют определенные входные данные, которые могут заставить их работать намного медленнее, чем обычно. В «Убийца-убийца для быстрой сортировки» автор подробно описывает, как использовать собственный компаратор для преднамеренного создания неверного ввода для алгоритма сортировки.

Надеюсь, это поможет!

Answer 2

Два параметра будут элементами вашего массива. Система сравнит достаточно пар, чтобы правильно их отсортировать. Больше ничего не гарантируется.

Есть много вещей, которые метод сортировки мог бы делать под капотом; см., например, http://en.wikipedia.org/wiki/Sorting_algorithm для некоторых из них. Большинство реализаций Javascript, вероятно, используют какой-либо вариант быстрой сортировки или слияния.

(Вот очень краткое их описание. Быстрая сортировка: выберите элемент в массиве, переставьте массив так, чтобы все было меньше, чем перед большим, а затем отсортировали «меньшие» и «большие» биты. Mergesort: сортировать первую половину массива, сортировать вторую половину массива, а затем объединять две отсортированные половины.В обоих случаях вам нужно сортировать меньшие массивы, что вы делаете с помощью того же алгоритма, пока не доберетесь до массивов так, мало что сортировка их тривиальна. В обоих случаях хорошие практические реализации делают все умные вещи, которые я не упомянул.)

Answer 3

Когда вы передаете функцию в Array.sort(), она ожидает два параметра и возвращает числовое значение.

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

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

Если вы вернете 0 , они останутся в своем текущем положении.

Делая return a - b;, вы возвращаете отрицательное число, если a меньше, чем b (2 - 13 = -11), положительное число, если b меньше, чем (13 - 2 = 11), и ноль, если они даже (13 - 13 = 0). * 1024. *

Насколько числа сравниваются в каком порядке, я считаю, что это зависит от движка JavaScript, чтобы определить.

Ознакомьтесь с документацией по сортировке массивов JavaScript в Doc Center для получения более подробной информации. https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/sort

(Кстати, я всегда проверяю MDC Doc Center на любые вопросы о том, как работает javascript, у них самая лучшая информация о языке AFAIK.)

Answer 4

Будет вызвано для всех пар a, b, что алгоритм сортировки должен сортировать весь массив. Проверьте http://en.wikipedia.org/wiki/Sorting_algorithm для краткого списка алгоритмов сортировки.