Стабильная сортировка с использованием массивов JavaScript

Введение

В этом лабе мы будем изучать концепцию стабильной сортировки в JavaScript. Стабильная сортировка - это техника, которая сохраняет порядок элементов в массиве, когда их значения совпадают. Мы будем использовать функцию, которая использует методы Array.prototype.map() и Array.prototype.sort(), чтобы реализовать стабильную сортировку массива.

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

Для выполнения стабильной сортировки массива и сохранения исходных индексов элементов с одинаковыми значениями следуйте шагам:

1. Откройте Терминал/SSH и введите node, чтобы начать практиковать программирование.
2. Используйте Array.prototype.map(), чтобы сопоставить каждый элемент входного массива с его соответствующим индексом.
3. Используйте Array.prototype.sort() вместе с функцией compare, чтобы отсортировать список, сохраняя исходный порядок, если сравниваемые элементы равны.
4. Используйте Array.prototype.map() снова, чтобы преобразовать элементы массива обратно в их исходную форму.
5. Исходный массив не изменяется, вместо этого возвращается новый массив.

Вот реализация функции stableSort на JavaScript:

const stableSort = (arr, compare) =>
  arr
    .map((item, index) => ({ item, index }))
    .sort((a, b) => compare(a.item, b.item) || a.index - b.index)
    .map(({ item }) => item);

Вы можете вызвать функцию stableSort с массивом и функцией compare, чтобы получить новый массив с отсортированными элементами, как показано ниже:

const arr = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10];
const stable = stableSort(arr, () => 0); // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

Резюме

Поздравляем! Вы завершили лабу по Стабильной сортировке. Вы можете практиковать в LabEx более лаб, чтобы улучшить свои навыки.