Механизм сортировки в JavaScript — это модель простоты, но пузырьки под поверхностью — это невероятно гибкая и мощная функциональность. Используя sort , можно организовать массивы не только в алфавитном или числовом порядке, но и в любой другой заказ, который мы можем выразить в условной логике.
Как работает функция сортировки
→ Если вы уже знаете основы, то можете пропустить это .
Если метод sort() вызывается без аргумента, то массив сортируется лексикографически — в порядке словаря, когда каждое значение рассматривается как строка:
var letters = ["R","O","F","L"]; letters.sort(); alert(letters); //produces ["F","L","O","R"]
В противном случае аргумент для sort является функцией сравнения , которая определяет поведение сортировки в соответствии с тем, как оно возвращается. Сама функция сравнения принимает два аргумента, обычно называемые a и b b , которые представляют два значения, сравниваемые в каждой операции. Потом:
- если функция возвращает меньше нуля , сортировать
aдоb - если функция возвращает больше нуля , сортировать
bbдоa - если функция возвращает ноль , оставьте
aиbbбез изменений по отношению друг к другу
Спецификация JavaScript ссылается на первое условие сортировки
как на сортировку
b b до более низкого индекса, чем a
. Но что это на самом деле означает, «сортировать a b b ниже по списку, чем a a » , что с точки зрения числовой индексации является более высоким , а не более низким индексом. Он использует слово «индекс» в очень запутанной форме; как я выразил вышеизложенные условия, надеюсь, будет намного понятнее.
Таким образом, обычный способ использования функции сравнения — выполнить и вернуть простую оценку, которая производит желаемый вид. Например, если функция возвращает (a - b) , то это произведет числовую сортировку :
var numbers = [8,5]; numbers.sort(function(a, b) { return a - b; }); alert(numbers); //produces [5,8]
Мы можем работать с этим на примерах значений: так как a = 8 и b = 5 , то (a - b) == 3 ; три больше нуля, так b b будет отсортирован раньше a a , производя заказ [5,8] .
Таким образом, обратный числовой порядок может быть получен просто путем обращения уравнения:
var numbers = [4,3,5,9]; numbers.sort(function(a, b) { return b - a; }); alert(numbers); //produces [9,5,4,3]
Мы также можем создать функцию сравнения, которая производит сортировку по словарю, определяя три сравнения для оценки каждой пары строк — в вычислительном выражении "a" меньше, чем "b" , поэтому мы можем напрямую сравнивать строки, подобные этим, чтобы затем вернуть одно из трех значений сортировки:
var letters = ["R","O","F","L"]; letters.sort(function(a, b) { var x = a.toLowerCase(), y = b.toLowerCase(); return x < y ? -1 : x > y ? 1 : 0; });
Обратите внимание, как мы предварительно конвертируем каждую из строк в нижний регистр, что гарантирует, что мы получим сортировку без учета регистра (если мы этого не сделали, тогда строчные и прописные буквы будут отсортированы отдельно). Мы также присваиваем результаты этих операций новым переменным, потому что некоторые браузеры возражают против перезаписи аргументов.
Многомерная сортировка
Если a и b b сами являются массивами, ну, прямое сравнение массивов с использованием математической оценки не даст желаемых результатов; но мы можем сравнить их внутренние ценности и сделать с ними сортировку. Вот как мы сортируем многомерные массивы, используя значение из каждого внутреннего массива в качестве критерия сортировки. Все остальные внутренние значения просто «приходят вместе», и таким образом мы можем сортировать массивы, содержащие смесь значений. В следующем примере будет отсортирована матрица по количеству сторон на каждой фигуре:
var shapes = [ [5, "Pentagon"], [3, "Triangle"], [8, "Octagon"], [4, "Rectangle"] ]; shapes.sort(function(a, b) { return a[0] - b[0]; });
Многокритериальная сортировка
Если мы можем отсортировать многомерные массивы, используя только одно из значений, не могли бы мы также отсортировать их, используя оба их значения в качестве независимых критериев? Ответ, конечно, да, мы можем, просто добавив дополнительные условия к логике внутри функции сравнения. Например, используйте значение [0] для первичной сортировки, но если два значения равны, то используйте значение [1] для вторичной сортировки. В следующем примере снова используются фигуры, которые сначала сортируются по количеству сторон, а затем по алфавитному имени фигуры, если число сторон равно:
var shapes = [ [4, "Trapezium"], [5, "Pentagon"], [3, "Triangle"], [4, "Rectangle"], [4, "Square"] ]; shapes.sort(function(a, b) { if(a[0] === b[0]) { var x = a[1].toLowerCase(), y = b[1].toLowerCase(); return x < y ? -1 : x > y ? 1 : 0; } return a[0] - b[0]; });
Принципал может быть расширен до необходимого уровня — если первичный тест равен, то сортировать по вторичному тесту; если вторичный тест равен, тогда сортируйте по третичному тесту; и так далее, для такого количества точек сравнения, как у нас.
Сортировка массивов объектов
Поскольку сравнения становятся более сложными, лучше отказаться от использования многомерных массивов и отдать предпочтение использованию массивов объектных литералов . Это облегчает понимание того, что происходит в функции сравнения, просто потому, что у нас есть интуитивно понятные имена для критериев. Прекрасный пример этого можно увидеть в библиотеке CSSUtilities , которая анализирует документ CSS для создания собственной коллекции объектов правил.
Общая коллекция правил хранится в виде массива, и каждый из его членов является объектом со свойствами, такими как specificity («сила» правила, определяемая его селектором и контекстом наследования), index (общая позиция правила в пределах набор правил) и depth (числовое значение для унаследованных правил, которое указывает глубину цепочки наследования, т. е. правило, унаследованное от <html> будет иметь значение, которое больше (на единицу), чем правило, унаследованное от <body> ) , Сама specificity также представляет собой массив из четырех независимых значений, по одному для каждой из категорий специфики (подробности см. В разделе Расчет специфичности селектора в спецификации CSS3 ).
Итак, как нам отсортировать объекты-правила, учитывая все эти значения, чтобы получить массив, который попадает в абсолютный порядок специфичности? Прежде всего, конечно, нужно иметь четкое представление о правилах, которые мы пытаемся реализовать:
- отсортировать по конкретности, если значения не равны:
- сортировать по первой категории, если значения не равны
- еще сортировать по второй категории, если значения не равны
- еще сортировать по третьей категории, если значения не равны
- еще сортировать по четвертой и последней категории
- еще сортировать по индексу, если значения не равны
- еще сортировка по глубине наследования
И тогда это просто случай выражения этого в коде:
rules.sort(function(a, b) { if(a.specificity.toString() === b.specificity.toString()) { if(a.index === b.index) { return b.depth - a.depth; } return a.index - b.index; } if(a.specificity[0] !== b.specificity[0]) { return a.specificity[0] - b.specificity[0]; } if(a.specificity[1] !== b.specificity[1]) { return a.specificity[1] - b.specificity[1]; } if(a.specificity[2] !== b.specificity[2]) { return a.specificity[2] - b.specificity[2]; } return a.specificity[3] - b.specificity[3]; });
Логика немного колебалась, поэтому некоторые правила выражаются в виде обратных условий; это должно повысить эффективность функции, поэтому для ее реализации требуется меньше кода, и он возвращается как можно скорее . Вероятно, есть несколько разных способов кодирования одних и тех же условий.
Заметка о стабильной сортировке
Единственная реальная проблема с этой техникой — это вопрос стабильной сортировки , что означает — если a и b b одинаковы, то они не меняются по отношению друг к другу. Проблема в том, что стабильная сортировка предназначена для самих сортируемых значений ; но в этих примерах a и b b сами по себе не являются значениями, которые мы оцениваем для сортировки, а просто являются контейнерами для значений. Следовательно, стабильная сортировка не может быть гарантирована, и то, что происходит на самом деле, будет отличаться в разных браузерах (некоторые их покинут, некоторые переместят)
Лично я никогда не встречал ситуации, в которой это значимо. Но если вы это сделаете, способ предотвратить это — убедиться, что два сортируемых объекта никогда не будут одинаковыми . Например, вы можете назначить свойство числового индекса каждому из объектов, которые вы сортируете, отражая их начальный порядок в массиве. Затем в вашей функции сравнения добавьте конечное условие, когда все остальные равны, что сортирует по значению этих индексов. Так как они отражают исходный порядок и являются уникальными, они будут эффективно поддерживать порядок всякий раз, когда не происходит никакой другой сортировки.
Сортировка!
Важно помнить, что функция сравнения сортировки не является чем-то особенным или необычным , это просто другая функция, которая выполняет какие -то действия, а затем возвращает их. Вы можете загружать внешние данные, создавать элементы для тестового рендеринга или выполнять любое количество сложных операций. Пока функция возвращает корректно — меньше нуля, больше нуля или нуля — нет никаких особых ограничений на то, что вы можете сделать, чтобы попасть туда!
Миниатюра кредит: [Сорен]