Array.prototype.sort()

Метод sort() экземпляров Array сортирует элементы массива на месте и возвращает ссылку на тот же массив, теперь отсортированный. Порядок сортировки по умолчанию — по возрастанию, основанный на преобразовании элементов в строки, а затем на сравнении их последовательностей значений кодов единиц UTF-16.

Временная и пространственная сложность сортировки не могут быть гарантированы, так как они зависят от реализации.

Чтобы отсортировать элементы массива, не изменяя исходный массив, используйте toSorted().

Попробуйте

const months = ["March", "Jan", "Feb", "Dec"];
months.sort();
console.log(months);
// Expected output: Array ["Dec", "Feb", "Jan", "March"]

const array = [1, 30, 4, 21, 100000];
array.sort();
console.log(array);
// Expected output: Array [1, 100000, 21, 30, 4]

Синтаксис

sort()
sort(compareFn)

Параметры

compareFn Необязательный

Функция, определяющая порядок элементов. Функция вызывается со следующими аргументами:

a

Первый элемент для сравнения. Никогда не будет undefined.

b

Второй элемент для сравнения. Никогда не будет undefined.

Он должен возвращать число, где:

• Отрицательное значение указывает, что a должен идти перед b.
• Положительное значение указывает, что a должен идти после b.
• Ноль или NaN указывает, что a и b считаются равными.

Чтобы запомнить это, помните, что (a, b) => a - b сортирует числа в порядке возрастания.

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

Возвращаемое значение

Ссылка на исходный массив, теперь отсортированный. Обратите внимание, что массив сортируется на месте, и копия не создается.

Описание

Если compareFn не указан, все не-undefined элементы массива сортируются путем преобразования их в строки и сравнения строк в порядке кодов единиц UTF-16. Например, "banana" идет перед "cherry". При числовой сортировке 9 идет перед 80, но поскольку числа преобразуются в строки, "80" идет перед "9" в порядке Unicode. Все undefined элементы сортируются в конец массива.

Метод sort() сохраняет пустые слоты. Если исходный массив разреженный, пустые слоты перемещаются в конец массива и всегда идут после всех undefined.

Если указана compareFn, все не-undefined элементы массива сортируются в соответствии с возвращаемым значением функции сравнения (все undefined элементы сортируются в конец массива, без вызова compareFn).

Таким образом, функция сравнения имеет следующую форму:

function compareFn(a, b) {
  if (a is less than b by some ordering criterion) {
    return -1;
  } else if (a is greater than b by the ordering criterion) {
    return 1;
  }
  // a must be equal to b
  return 0;
}

Более формально, ожидается, что компаратор будет обладать следующими свойствами для обеспечения корректного поведения сортировки:

• Чистый: Компаратор не изменяет сравниваемые объекты или внешнее состояние. (Это важно, поскольку нет гарантии, *когда* и *как* будет вызван компаратор, поэтому любой конкретный вызов не должен оказывать видимых внешних эффектов.)
• Стабильный: Компаратор возвращает одинаковый результат для одной и той же пары входных данных.
• Рефлексивный: compareFn(a, a) === 0.
• Антисимметричный: compareFn(a, b) и compareFn(b, a) должны быть оба 0 или иметь противоположные знаки.
• Транзитивный: Если compareFn(a, b) и compareFn(b, c) оба положительные, нулевые или отрицательные, то compareFn(a, c) имеет ту же позитивность, что и предыдущие два.

Компаратор, соответствующий приведенным выше ограничениям, всегда сможет вернуть любое из 1, 0 и -1, или последовательно возвращать 0. Например, если компаратор возвращает только 1 и 0, или только 0 и -1, он не сможет надежно сортировать, поскольку нарушена *антисимметрия*. Компаратор, который всегда возвращает 0, приведет к тому, что массив вообще не изменится, но все равно будет надежным.

Стандартный лексикографический компаратор удовлетворяет всем вышеперечисленным ограничениям.

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

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

Метод sort() является общим. Он ожидает, что значение this будет иметь свойство length и целочисленные свойства. Хотя строки также являются подобными массивам, этот метод не подходит для их применения, поскольку строки неизменяемы.

Примеры

Создание, отображение и сортировка массива

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

const stringArray = ["Blue", "Humpback", "Beluga"];
const numberArray = [40, 1, 5, 200];
const numericStringArray = ["80", "9", "700"];
const mixedNumericArray = ["80", "9", "700", 40, 1, 5, 200];

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

stringArray.join(); // 'Blue,Humpback,Beluga'
stringArray.sort(); // ['Beluga', 'Blue', 'Humpback']

numberArray.join(); // '40,1,5,200'
numberArray.sort(); // [1, 200, 40, 5]
numberArray.sort(compareNumbers); // [1, 5, 40, 200]

numericStringArray.join(); // '80,9,700'
numericStringArray.sort(); // ['700', '80', '9']
numericStringArray.sort(compareNumbers); // ['9', '80', '700']

mixedNumericArray.join(); // '80,9,700,40,1,5,200'
mixedNumericArray.sort(); // [1, 200, 40, 5, '700', '80', '9']
mixedNumericArray.sort(compareNumbers); // [1, 5, '9', 40, '80', 200, '700']

Сортировка массива объектов

Массивы объектов можно сортировать, сравнивая значение одного из их свойств.

const items = [
  { name: "Edward", value: 21 },
  { name: "Sharpe", value: 37 },
  { name: "And", value: 45 },
  { name: "The", value: -12 },
  { name: "Magnetic", value: 13 },
  { name: "Zeros", value: 37 },
];

// sort by value
items.sort((a, b) => a.value - b.value);

// sort by name
items.sort((a, b) => {
  const nameA = a.name.toUpperCase(); // ignore upper and lowercase
  const nameB = b.name.toUpperCase(); // ignore upper and lowercase
  if (nameA < nameB) {
    return -1;
  }
  if (nameA > nameB) {
    return 1;
  }

  // names must be equal
  return 0;
});

Сортировка не-ASCII символов

Для сортировки строк с не-ASCII символами, т.е. строк с акцентированными символами (e, é, è, a, ä и т.д.), строк на языках, отличных от английского, используйте String.prototype.localeCompare(). Эта функция может сравнивать эти символы так, чтобы они располагались в правильном порядке.

const items = ["réservé", "premier", "communiqué", "café", "adieu", "éclair"];
items.sort((a, b) => a.localeCompare(b));

// items is ['adieu', 'café', 'communiqué', 'éclair', 'premier', 'réservé']

Сортировка с помощью map

compareFn может вызываться несколько раз для каждого элемента в массиве. В зависимости от природы compareFn, это может привести к высоким накладным расходам. Чем больше работы выполняет compareFn и чем больше элементов для сортировки, тем эффективнее может быть использование map() для сортировки. Идея состоит в том, чтобы один раз пройти по массиву, чтобы извлечь фактические значения, используемые для сортировки, во временный массив, отсортировать временный массив, а затем пройти по временному массиву, чтобы получить правильный порядок.

// the array to be sorted
const data = ["delta", "alpha", "charlie", "bravo"];

// temporary array holds objects with position and sort-value
const mapped = data.map((v, i) => ({ i, value: someSlowOperation(v) }));

// sorting the mapped array containing the reduced values
mapped.sort((a, b) => {
  if (a.value > b.value) {
    return 1;
  }
  if (a.value < b.value) {
    return -1;
  }
  return 0;
});

const result = mapped.map((v) => data[v.i]);

Существует библиотека с открытым исходным кодом под названием mapsort, которая применяет этот подход.

sort() возвращает ссылку на тот же массив

Метод sort() возвращает ссылку на исходный массив, поэтому изменение возвращаемого массива также изменит исходный массив.

const numbers = [3, 1, 4, 1, 5];
const sorted = numbers.sort((a, b) => a - b);
// numbers and sorted are both [1, 1, 3, 4, 5]
sorted[0] = 10;
console.log(numbers[0]); // 10

Если вы хотите, чтобы sort() не изменял исходный массив, а возвращал поверхностно скопированный массив, как и другие методы массива (например, map()), используйте метод toSorted(). В качестве альтернативы вы можете сделать поверхностную копию перед вызовом sort(), используя оператор расширения или Array.from().

const numbers = [3, 1, 4, 1, 5];
// [...numbers] creates a shallow copy, so sort() does not mutate the original
const sorted = [...numbers].sort((a, b) => a - b);
sorted[0] = 10;
console.log(numbers[0]); // 3

Стабильность сортировки

Начиная с версии 10 (или ECMAScript 2019), спецификация предписывает, что Array.prototype.sort является стабильной.

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

const students = [
  { name: "Alex", grade: 15 },
  { name: "Devlin", grade: 15 },
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
];

После сортировки этого массива по grade в порядке возрастания:

students.sort((firstItem, secondItem) => firstItem.grade - secondItem.grade);

Переменная students будет иметь следующее значение:

[
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
  { name: "Alex", grade: 15 }, // original maintained for similar grade (stable sorting)
  { name: "Devlin", grade: 15 }, // original maintained for similar grade (stable sorting)
];

Важно отметить, что студенты, имеющие одинаковую оценку (например, Alex и Devlin), останутся в том же порядке, что и до вызова сортировки. Это именно то, что гарантирует стабильный алгоритм сортировки.

До версии 10 (или ECMAScript 2019) стабильность сортировки не гарантировалась, что означало, что вы могли получить следующее:

[
  { name: "Eagle", grade: 13 },
  { name: "Sam", grade: 14 },
  { name: "Devlin", grade: 15 }, // original order not maintained
  { name: "Alex", grade: 15 }, // original order not maintained
];

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

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

Например, рассмотрим следующий код:

const arr = [3, 1, 4, 1, 5, 9];
const compareFn = (a, b) => (a > b ? 1 : 0);
arr.sort(compareFn);

Функция compareFn здесь некорректна, поскольку она не удовлетворяет антисимметрии: если a > b, она возвращает 1; но меняя местами a и b, она возвращает 0 вместо отрицательного значения. Следовательно, результирующий массив будет отличаться в разных движках. Например, V8 (используемый Chrome, Node.js и т.д.) и JavaScriptCore (используемый Safari) вообще не будут сортировать массив и вернут [3, 1, 4, 1, 5, 9], тогда как SpiderMonkey (используемый Firefox) вернет массив, отсортированный по возрастанию, как [1, 1, 3, 4, 5, 9].

Однако, если функция compareFn немного изменена так, что она возвращает -1 или 0:

const arr = [3, 1, 4, 1, 5, 9];
const compareFn = (a, b) => (a > b ? -1 : 0);
arr.sort(compareFn);

Тогда V8 и JavaScriptCore отсортируют его по убыванию, как [9, 5, 4, 3, 1, 1], а SpiderMonkey вернет его без изменений: [3, 1, 4, 1, 5, 9].

Из-за этой несогласованности реализаций всегда рекомендуется делать ваш компаратор корректным, следуя пяти ограничениям.

Использование sort() на разреженных массивах

Пустые слоты перемещаются в конец массива.

console.log(["a", "c", , "b"].sort()); // ['a', 'b', 'c', empty]
console.log([, undefined, "a", "b"].sort()); // ["a", "b", undefined, empty]

Вызов sort() на не-массивных объектах

Метод sort() считывает свойство length объекта this. Затем он собирает все существующие целочисленные свойства в диапазоне от 0 до length - 1, сортирует их и записывает обратно. Если в диапазоне отсутствуют свойства, соответствующие конечные свойства удаляются, как если бы несуществующие свойства сортировались в конец.

const arrayLike = {
  length: 3,
  unrelated: "foo",
  0: 5,
  2: 4,
};
console.log(Array.prototype.sort.call(arrayLike));
// { '0': 4, '1': 5, length: 3, unrelated: 'foo' }

Спецификации

Совместимость с браузерами

См. также

• Polyfill Array.prototype.sort с современным поведением, таким как стабильная сортировка в core-js
• Руководство по индексированным коллекциям
• Array
• Array.prototype.reverse()
• Array.prototype.toSorted()
• String.prototype.localeCompare()
• TypedArray.prototype.sort()
• Getting things sorted in V8 на v8.dev (2018)
• Stable Array.prototype.sort на v8.dev (2019)
• Array.prototype.sort stability от Mathias Bynens