Что на самом деле происходит в Javascript Sort

Question

Я видел, как эта функция сортировки работает нормально:

var arr = [1,5,3,7,8,6,4,3,2,3,3,4,5,56,7,8,8];


console.log(arr.sort(
    function(a,b) {
        return a - b;
    }
    ));

Но я не совсем понимаю механику этой маленькой функции.Когда он сравнивает a и b, какие числа в массиве он сравнивает?Если, скажем, он подобрал первые два числа 1 и 5, функция вернет -4.Что это значит для порядка сортировки?Или это просто отрицательное логическое значение?Даже если это так, как это происходит на самом деле?

Answer 1

По сути, сортировка работает путем сравнения двух элементов одновременно. Сравнение больше, чем логическое - у вас есть три варианта: меньше, равно и больше, чем. В JavaScript эти три значения представлены n <0, 0 и n> 0 соответственно.

Другими словами, отрицательные числа означают a < b; 0 означает a = b, а положительное означает a > b.

Чтобы ответить на более широкий вопрос: существует несколько относительно быстрых алгоритмов сортировки списка путем сравнения его элементов. Наиболее популярным является Quicksort ; однако Quicksort не стабилен, поэтому некоторые движки (Firefox наверняка) используют другой алгоритм. Простая стабильная сортировка - Mergesort .

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

Слегка случайный в стороне:

Вы могли бы также представить использование специального типа (например, enum) для такого рода вещей. Например, функция сравнения может возвращать LT, GT или EQ в зависимости от ситуации. Однако в динамическом языке, таком как JavaScript, гораздо проще просто использовать числа. В языках, более одержимых типами (например, Haskell :)), использование специального типа порядка имеет больше смысла.

Answer 2

У вас есть 3 варианта минус (-), равно (==) и плюс (+):

• минус : если a - b < 0, то a до b
• равно : не имеет значения
• плюс : если a - b > 0, то b до a

См. Эту ветку для получения дополнительной информации: Реализация Javascript Array.sort?

Answer 3

При передаче функции в Array.sort она будет использоваться для сравнения a и b.Как они будут отсортированы, зависит от того, что возвращает функция:

• Если result < 0, то a предшествует b;
• Если result == 0, то a и b уже в правильном порядке;
• Если result > 0, то a следует после b.

Если sort вызывается безВ качестве аргумента, элементы преобразуются в строки и сравниваются в алфавитном порядке.

Между прочим, какой алгоритм sort использует, полностью зависит от реализации браузера.Это может быть быстрая сортировка, сортировка слиянием или что-то еще.Стандарт ECMAScript не устанавливает каких-либо требований в этом отношении.