Напишите алгоритм вручную и запомните его: Сортировка подсчетом

внешний интерфейс JavaScript

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

Эта серия статей пытается решить эту проблему.

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

Например, сортировка подсчетом, так называемый «подсчет», заключается в подсчете количества повторных повторений каждого элемента.

Диаграмма выше демонстрирует общий поток алгоритма. Он разделен на два этапа: проверка и сортировка.

Сначала проверьте, сколько раз появляется каждый элемент, например, элемент 0 появляется один раз, элемент 1 появляется один раз, элемент 2 появляется 3 раза и т. д.

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

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

Проверяем, реализация такая:

let array = [3, 2, 1, 2, 3, 2, 0, 4]
let counts = []
for (let v of array) {
  counts[v] = (counts[v] || 0) + 1
}
console.log(counts) // [1, 1, 3, 2, 1]

Массив counts представляет собой статистический результат, а его нижний индекс представляет элемент массива, подлежащий сортировке. Его длина равна 5 (плюс 1 к максимальному значению сортируемого массива).

ряд, реализованный следующим образом:

let result = []
for (let i = 0; i < counts.length; i++) {
  let count = counts[i]
  while(count > 0) {
    result.push(i)
    count--
  }
}
console.log(result) // [0, 1, 2, 2, 2, 3, 3, 4]

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

Из конкретного процесса алгоритма видно, что сортировка подсчетом подходит для целочисленной сортировки. Вот вопрос, а что если в значениях есть отрицательные числа?

Решение также легко придумать: сначала мы проходим его, чтобы найти минимальное значение в массиве, и используем его в качестве смещения.

Если данные [-3, -2, -1, -2, -3, -2, 0, -4], минимальное значение массива в данных равно -4, а максимальное значение равно 0. Мы можем использовать 0-й индекс счетчиков для представления минимального значения.

let array = [-3, -2, -1, -2, -3, -2, 0, -4]
let counts = [], result = []
let min = Math.min(...array)
for (let v of array) {
  counts[v-min] = (counts[v-min] || 0) + 1
}
for (let i = 0; i < counts.length; i++) {
  let count = counts[i]
  while(count > 0) {
    result.push(i + min)
    count--
  }
}
console.log(result) // [-4, -3, -3, -2, -2, -2, -1, 0]

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

Эта реализация также позволяет избежать другой проблемы — пустой траты места в наборе данных. Например, если данные находятся в диапазоне от 900 до 1000, длина отсчетов должна быть только 101.

На данный момент принцип и реализация счетной сортировки закончены.

См. полный код:codepen.

Подводя итог, можно сказать, что сортировка подсчетом подходит для сортировки целых чисел, а временная сложность составляет O(n+k). Кратко объясните, почему это O (n + k). Здесь используются два слоя циклов, внешний слой определяется длиной counts — разницей между наибольшим количеством значений массива, подлежащего сортировке (записывается как k) — , а количество циклов while определяется count , а сумма всех счетчиков точно равна длине массива (обозначается как n). Кроме того, что касается использования пространства, объемная сложность открывающей реализации составляет O(n+k), а объемная сложность реализации в полном коде составляет O(k). Можно видеть, что когда k особенно велико, будет использовано много места.

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

Надеюсь, что это поможет, эта статья закончилась.


Статьи, опубликованные в этой серии:

Категории