Как работает функция сортировки в JavaScript вместе с функцией сравнения - PullRequest
55 голосов
/ 04 июля 2011

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

Ответы [ 5 ]

131 голосов
/ 04 июля 2011

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

  1. Возвращает больше 0, если a больше b
  2. Возвращает 0, если a равно b
  3. Возвращает меньше 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. 1 больше или меньше 5? Меньше чем, поэтому внесите эти два числа в наш список: 1,5
  2. 3,14 больше или меньше 1? Больше чем, так оно идет после 1 в новом списке
  3. 3,14 больше или меньше 5 в нашем новом списке? Меньше чем, поэтому он идет раньше 5. Наш новый список теперь [1,3.14,5]

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

29 голосов
/ 04 июля 2011

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

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

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

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

  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, о которой я упоминал ранее.

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

5 голосов
/ 05 декабря 2012

В этом методе используются синтаксис и параметры порядка Array.sort (функция сравнения sortOptions), параметры которого определены следующим образом:

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

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

1 голос
/ 25 августа 2016

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

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 . 
0 голосов
/ 27 января 2012

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

предположим, что функция 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) - упорядоченная пара, переданная в функцию сравнения.

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

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

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

Действительно ли движки js браузеров не разработаны строго в соответствии с `ECMA-262 или я совершенно не прав?

Справка:

Пятое издание ECMA-262 (см. Стр. 129-130)

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