Как работает функция сортировки в JavaScript, а также функция сравнения

Как уже спрашивали: как функция сортировки работает в JavaScript, а также функция compare? Если у меня есть массив, и я делаю array.sort(compare), то теперь в книге было записано, что если функция compare возвращает a-b (два индекса массива), то она работает на основании того, что результат больше чем 0, меньше 0 или равно 0. Но как именно он работает? Я не мог это решить.

Ответ 1

Функция "compare" должна принимать два аргумента, часто называемых a и b. Затем вы делаете функцию сравнения return 0, больше 0 или меньше 0, на основе этих значений a и b.

Возвращает больше 0, если a больше b
Возвращает 0, если a равно b
Возвращает меньше 0, если a меньше b

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

Затем, когда вы вызываете sort(), с вашей пользовательской функцией сравнения, функция сравнения вызывается пар в вашем отсортированном списке, чтобы определить правильный порядок.

Давайте рассмотрим простой пример... Предположим, вы только сортируете некоторые числа, поэтому у нас есть очень простая функция сравнения:

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

Просто вычитание b из a всегда будет возвращать больше нуля, если a больше b, 0, если они равны или меньше нуля, если a меньше b. Таким образом, он отвечает требованиям для функции сравнения.

Теперь давайте предположим, что это наш список чисел для сортировки:

var numbers = [1,5,3.14];

Когда вы вызываете numbers.sort(compare), внутри он фактически выполняет:

compare(1,5);     // Returns -4, a is less than b
compare(1,3.14);  // Return -2.14, a is less than b
compare(5,3.14);  // returns 1.86, a is greater than b

Если вы когда-либо делали ручную сортировку или сортировку по алфавиту, вы делали то же самое, возможно, не осознавая этого. Даже если у вас могут быть десятки или сотни предметов для сравнения, вы постоянно сравниваете только два числа (или фамилии автора или что-то еще) за раз. Пройдя через короткий список из трех чисел, вы начнете с сравнения первых двух чисел:

Является ли 1 больше или меньше 5? Меньше, поэтому поместите эти два числа в наш список: 1,5
Это 3.14 больше или меньше 1? Больше, так что он идет после 1 в новом списке
Является ли 3.14 больше или меньше 5 в нашем новом списке? Меньше, чем раньше 5. Наш новый список теперь [1,3.14,5]

Поскольку вы можете предоставить свою собственную функцию compare(), можно отсортировать произвольно сложные данные, а не только числа.

Ответ 2

По умолчанию метод массива sort() сортируется по алфавиту по возрастанию. Если вы хотите отсортировать в каком-то другом порядке, потому что ваш массив содержит числа или объекты, вы можете передать функцию в sort().

Функция, которую вы передаете, принимает два параметра, часто называемых a и b, и возвращает: отрицательное число, если первый аргумент должен быть отсортирован перед вторым (a < b) 0, если аргументы равны (a == b) положительное число, если первый аргумент должен быть отсортирован после второго (a > b)

Теперь здесь бит ключа: функция, которую вы передаете как параметр sort(), будет повторно вызываться sort(), поскольку она обрабатывает весь массив. sort() не знает и не заботится о типе данных вещей в массиве: каждый раз, когда ему нужно знать "Возможен ли элемент A перед элементом B?" он просто вызывает вашу функцию. Вам не нужно беспокоиться о том, какой тип алгоритма сортировки используется внутри sort(), действительно, один браузер может использовать другой алгоритм для другого, но это нормально, потому что вам просто нужно дать ему возможность сравнить любые два элемента из вашего массива.

У вашей функции может быть структура if / else if / else, чтобы решить, какой результат будет возвращен, но для чисел, просто возвращающихся (ab), достигнет этого для вас, потому что результат вычитания будет -ve, 0 или + ve и правильно установлен числа в порядке возрастания. Возврат (b-a) приведет к их уменьшению:

  var sortedArray = myArray.sort(function(a,b){
                                    return (a-b);
                                });

Если у вас есть массив объектов и вы хотите отсортировать по определенному свойству или свойствам объектов, вы тоже можете это сделать. Предполагая, например, объекты в этом формате:

{ id : 1,
  name : "Fred",
  address : "12 Smith St",
  phone : "0262626262" }

Затем вы можете отсортировать массив таких объектов по их атрибуту "id" следующим образом:

var sortedArray = myArray.sort(function(a,b){
                                  return (a.id - b.id);
                              });

Или вы можете отсортировать массив таких объектов по их атрибуту "name" (в алфавитном порядке) следующим образом:

var sortedArray = myArray.sort(function(a,b){
                                   if (a.name < b.name)
                                      return -1;
                                   else if (a.name == b.name)
                                      return 0;
                                   else
                                      return 1;
                               });

Обратите внимание, что в моем последнем примере я поместил полную структуру if / else if / else, о которой я упоминал ранее.

В примере, в котором вы сортируете объекты с несколькими свойствами, вы можете расширять это, чтобы добавить вторичный сорт, то есть (в моем примере), если свойства имени равны, вы можете вернуть сравнение, скажем, телефона.

Ответ 3

Этот метод использует синтаксис и параметры порядка Array.sort(compareFunction the sortOptions), параметры которого определены следующим образом:

compareFunction - функция сравнения, используемая для определения порядка сортировки элементов массива. Этот параметр является необязательным. Функция сравнения должна использоваться для сравнения двух параметров. A и B данного элемента, результат compareFunction может иметь отрицательное значение, 0 или положительное значение:

Если возвращаемое значение отрицательное, это означает, что A появляется перед B в отсортированной последовательности. Если возвращаемое значение равно 0, то A и B имеют одинаковый порядок сортировки. Если возвращаемое значение положительное, это означает, что A появляется после B в отсортированной последовательности.

Ответ 4

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

ex1: строки

var animals = ["Horse", "Cat", "Tiger", "Lion"];  
animals.sort();

ex2: числа

var marks = [70, 90, 60, 80 ];  
marks.sort(function(a, b){return a > b}); //ascending , a < b descending .

Ответ 5

Я думаю, это может быть так (ну, я не уверен в этом.):

предположим, что функция compare(a,b) является функцией сравнения. Он возвращает c. предположим, что мы собираемся сортировать записи в массиве N, чтобы получить массив результатов сортировки M.

Я не знаю точного алгоритма сортировки, и разные браузеры даже возвращают разные результаты, если c не является ни (a-b), ни (b-a) (скажем, если c - "b-2", "a+b" или некоторая другие выражения).

Но согласно ECMA-262 результат сортировки должен быть таким:

a, b может быть любым из двух индексов. это означает, что мы фактически передали упорядоченную пару функции сравнения. eg: (0,1),(1,4), or even (2,0) , (2,1).

Спецификация языка ECMAScript говорит, что результат должен иметь следующее свойство: (a,b) - это упорядоченная пара, переданная функции сравнения.

if c (то, что возвращает функция) меньше нуля, тогда M(a)< M(b) должно быть выполнено.

И спецификация ничего не говорит о том, что произойдет, если c равно нулю или больше нуля.

Я не уверен, правильно ли это. По крайней мере, это может легко объяснить, почему, когда c "a-b", записи сортируются как численные и восходящие, и почему, когда c является "b-a", записи сортируются в обратную сторону.

Являются ли js-движки браузеров на самом деле не разработаны строго в соответствии с "ECMA-262" или я совершенно не прав?

Ссылка:

Пятое издание ECMA-262 (Проверка страницы 129-130)