**Супер подробные** 10 принципов алгоритма сортировки и реализация JS

Введение

В этой статье представлены 10 общих алгоритмов сортировки.принцип,Базовая реализацияа такжеОбщие оптимизациидостичь и иметь (лично думаю)Достаточно подробные комментарии кода.
~~Это действительно домашняя работа, а письменный тест на собеседовании — обязательное лекарство.~~

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

Достаточно подробно!~~Даже дураки поймут! Если вы не понимаете, прочтите еще несколько раз!~~

Я видел видео на Weibo несколько дней назад:15 алгоритмов сортировки, продемонстрированных со звуком, вы можете взглянуть

Все анимации взяты из«Сводка десяти лучших классических алгоритмов сортировки (описание JavaScript)»

Классификация

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

Другой способ классификации основан на том, «Сравнить сортировку".

Общие виды сравнения:
- Пузырьковая сортировка
- сортировка выбором
- Сортировка вставками
- быстрая сортировка
- Сортировка слиянием
Распространенные несравнительные сорта:
- сортировка по подсчету
- сортировка по основанию
- сортировка ведром

сложность и стабильность

	Средняя временная сложность	наиболее	худший	космическая сложность	стабильность
Пузырьковая сортировка	O(n^2)	O(n)	O(n^2)	O(1)	стабилизировать
сортировка выбором	O(n^2)	O(n^2)	O(n^2)	O(1)	нестабильный
сортировка кучей	O(n logn)	O(n logn)	O(n logn)	O(1)	нестабильный
Сортировка вставками	O(n^2)	O(n)	O(n^2)	O(1)	стабилизировать
Сортировка холмов	O(n logn)	O(n log^2 n)	O(n log^2 n)	O(1)	нестабильный
быстрая сортировка	O(n logn)	O(n logn)	O(n^2)	O(logn)	нестабильный
Сортировка слиянием	O(n logn)	O(n logn)	O(n logn)	O(n)	стабилизировать
сортировка по подсчету	O(n+k)	O(n+k)	O(n+k)	O(k)	стабилизировать
сортировка ведром	O(n+k)	O(n+k)	O(n^2)	O(n+k)	стабилизировать
сортировка по основанию	O(n*k)	O(n*k)	O(n*k)	O(n+k)	стабилизировать

Пузырьковая сортировка

Общая реализация

Отсортированные элементы будут помещены в конец массива

Грубый процесс:

Начиная с первого элемента, сравнить каждые два соседних элемента, и если первый больше, поменять местами местами
В конце каждого обхода можно найти максимальное значение пройденных элементов.
Если все еще есть несортированные элементы, продолжайте с 1

Демонстрационное изображение:

function bubbleSort(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    for (let j = 0; j < arr.length -1 - i; j++) {
      if (arr[j] > arr[j+1]) swap(arr, j ,j+1)
    }
  }
  return arr
}
// 后面还会多次用到，就不再写出来了
function swap(arr, n, m) {
  [arr[n], arr[m]] = [arr[m], arr[n]]
}

Возможности для оптимизации есть, в основном, в двух аспектах:

Уменьшить количество внешних обходов
Пусть каждый обход находит два крайних значения

Оптимизация 1

Проверка внутреннего обходапроисходит ли обмен.

Если обмен не происходит, сортировка завершена, даже если внешний цикл не был выполнен.length-1можно и напрямуюbreak.

function bubbleSort1(arr) {
  for (let i = 0; i < arr.length - 1; i++) {
    // 外层循环初始值为 false，没有发生交换
    let has_exchanged = false
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j ,j+1)
        has_exchanged = true
      }
    }
    // 内层循环结束判断一下是否发生了交换
    if (!has_exchanged) break
  }
  return arr
}

Оптимизация 2

Записи, где произошел последний обмен во внутреннем обходе, следующий внешний обход должен перейти только в эту позицию.

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

function bubbleSort2(arr) {
  // 遍历结束位置的初始值为数组尾，并逐渐向数组头部逼近
  let high = arr.length - 1
  while (high > 0) {
    // 本次内层遍历发生交换的位置的初始值
    let position = 0
    for (let j = 0; j < high; j++) {
      if (arr[j] > arr[j + 1]) {
        swap(arr, j, j + 1)
        // 如果发生了交换，更新 position
        position = j
      }
    }
    // 下次遍历只需要到 position 的位置即可
    high = position
  }
  return arr
}

Оптимизация 3

Двусторонний обход, каждый цикл находит максимум и минимум.

Установите индекс до и после каждого,Подход к несортированной части посередине.

function bubbleSort3(arr) {
  let low = 0, high = arr.length - 1
  while (low < high) {
    // 正向遍历找最大
    for (let i = low; i <= high; i++) if (arr[i] > arr[i + 1]) swap(arr, i, i + 1)
    high--
    // 反向遍历找最小
    for (let j = high; j >= low; j--) if (arr[j] < arr[j - 1]) swap(arr, j, j - 1)
    low++
  }
  return arr
}

Сортировка выбором Сортировка выбором

Выберите наименьший за проход.

Отсортированные элементы будут помещены в начало массива.

Грубый процесс:

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

Это не перевернутая пузырьковая сортировка. Пузырьковая сортировка — это сравнениедва соседних элемента

Демонстрационное изображение:

function selectionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    let min_index = i
    // 遍历后面的部分，寻找更小值
    for (let j = i + 1; j < arr.length; j++) {
      // 如果有，更新min_index
      if (arr[j] < arr[min_index]) min_index = j
    }
    swap(arr, i, min_index)
  }
  return arr
}

HeapSort

Сортировка выбором реализована с использованием концепции кучи.

Сначала о куче:

Куча - это тип дерева. Когда родительский узел кучиоба больше или оба меньшедочерние узлы, соответственно называемыемаксимальная кучаилимин куча
Дерево (куча) может быть представлено массивом. Начиная с 0, начиная с первогоindexelement — это родительский узел кучи, а его левый и правый дочерние узлы — это первый и второй элементы массива.2*index+1а также2*index+2элементы

Отсортированные элементы будут помещены в конец массива

Грубый процесс:

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

Уведомление:

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

Демонстрационное изображение:

// 排序
function heapSort(arr) {
  var arr_length = arr.length
  if (arr_length <= 1) return arr
  // 1. 建最大堆
  // 遍历一半元素就够了
  // 必须从中点开始向左遍历，这样才能保证把最大的元素移动到根节点
  for (var middle = Math.floor(arr_length / 2); middle >= 0; middle--) maxHeapify(arr, middle, arr_length)
  // 2. 排序，遍历所有元素
  for (var j = arr_length; j >= 1; j--) {
    // 2.1. 把最大的根元素与最后一个元素交换
    swap(arr, 0, j - 1)
    // 2.2. 剩余的元素继续建最大堆
    maxHeapify(arr, 0, j - 2)
  }
  return arr
}
// 建最大堆
function maxHeapify(arr, middle_index, length) {
  // 1. 假设父节点位置的值最大
  var largest_index = middle_index
  // 2. 计算左右节点位置
  var left_index = 2 * middle_index + 1,
    right_index = 2 * middle_index + 2
  // 3. 判断父节点是否最大
  // 如果没有超出数组长度，并且子节点比父节点大，那么修改最大节点的索引
  // 左边更大
  if (left_index <= length && arr[left_index] > arr[largest_index]) largest_index = left_index
  // 右边更大
  if (right_index <= length && arr[right_index] > arr[largest_index]) largest_index = right_index
  // 4. 如果 largest_index 发生了更新，那么交换父子位置，递归计算
  if (largest_index !== middle_index) {
    swap(arr, middle_index, largest_index)
    // 因为这时一个较大的元素提到了前面，一个较小的元素移到了后面
    // 小元素的新位置之后可能还有比它更大的，需要递归
    maxHeapify(arr, largest_index, length)
  }
}

Сортировка вставками

Общая реализация

Отсортированные элементы будут помещены в начало массива.

Грубый процесс:

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

Первый способ понимания - это общий принцип реализации:

На шаге 2 выше при обходе отсортированных элементов, если несортированный элемент все еще меньше, чем текущий сравниваемый отсортированный элемент, значение предыдущего отсортированного элемента присваивается элементу в последней позиции, то есть результатом является два соседних повторяющиеся элементы.
Таким образом, в конце сравнения, когда подходящая позиция будет найдена, используйте несортированный элемент, чтобы присвоить значение соответствующему одному из двух повторяющихся элементов, перезаписать один, и сортировка завершена.

Описание может быть недостаточно ясным, просто взгляните на код.~~Talk is hard, show you some codes~~.

Кажется, это чем-то похоже на сортировку выбором:

сортировка выбором,Найдите нужный элемент,Потомпрямо вОтсортированный раздел
сортировка вставками,первый по порядкуэлемент,еще разв отсортированном разделенайти правильное место

Второй способ понимания:

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

Но код, реализованный таким образом, нельзя оптимизировать с помощью дихотомии.

Значит ли это, что здесь можно использовать метод оптимизации пузырьковой сортировки?
Не совсем. Потому что пузырьковая сортировка в основном оптимизируется по двум аспектам:

Уменьшить количество внешних обходов
Увеличить количество экстремальных значений, найденных в каждом обходе

И бульканье здесь только один раз, и оно не ищет экстремальных значений.

Демонстрационное изображение:

// 按照第一种理解方式的实现，即一般的实现
function insertionSort(arr) {
  for (let index = 1; index < arr.length; index++) {
    // 取出一个未排序元素
    let current_ele = arr[index]
    // 已排序元素的最后一个的位置
    let ordered_index = index - 1
    // 前面的元素更大，并且还没遍历完
    while (arr[ordered_index] >= current_ele && ordered_index >= 0) {
      // 使用前面的值覆盖当前的值
      arr[ordered_index + 1] = arr[ordered_index]
      // 向前移动一个位置
      ordered_index--
    }
    // 遍历完成，前面的元素都比当前元素小，把未排序元素赋值进去
    arr[ordered_index + 1] = current_ele
  }
  return arr
}
// 按照第二种理解方式的实现
function insertionSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    // 对前面的已排序数组和新选出来的元素执行一趟冒泡排序
    for (let j = i + 1; j >= 0; j--) if (arr[j] < arr[j - 1]) swap(arr, j, j - 1)
  }
  return arr
}

Неожиданное открытие для умственно отсталых:while(a&&b){}а такжеwhile(a){ if(b){} }Не эквивалентно. . .

оптимизация

Используйте бинарный поиск.

При обходе отсортированной части вместо последовательного сравнения друг с другом сравниваются медианы.

function binaryInsertionSort(array) {
  for (let i = 1; i < array.length; i++) {
    // 未排序部分的第1个
    let current_ele = array[i]
    // 已排序部分的第1个和最后1个
    let left = 0, right = i - 1
    // 先找位置
    while (left <= right) {
      // 不再是从最后一个位置开始向前每个都比较，而是比较中间的元素
      let middle = parseInt((left + right) / 2)
      if (current_ele < array[middle]) right = middle - 1
      else left = middle + 1
    }
    // while结束，已经找到了一个大于或等于当前元素的位置 left
    // 再修改数组：把 left 到 i 之间的元素向后移动一个位置
    for (let j = i - 1; j >= left; j--) array[j + 1] = array[j]
    // 插入当前元素
    array[left] = current_ele
  }
  return array
}

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

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

Сортировка Шелл Сортировка Шелл

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

указать приращениеgap, сгруппируйте массивы так, чтобы каждое расстояниеgap-1Элементы представляют собой группу, разделенную наgapгруппы, выполните сортировку вставками для каждой группы. Шаг внизgapsize и продолжайте выполнять сортировку вставками, пока он не станет равным 1, то есть весь массив как группу, выполните сортировку вставками для всего массива.

Можно обнаружить, что независимо от приращенияgapНачальное значение установлено в what, и, наконец, весь массив всегда будет вставлен один раз, то естьgapНа результат сортировки это никак не влияет, а влияет только на эффективность алгоритма.
Что касаетсяgapКак получить наилучшее значение, не изучалось. Ждем ваших сообщений и обменов.~~(Просто говоря, я думаю, что это чисто для интервью..)~~

Грубый процесс:

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

Демонстрационное изображение:

function shellSort(arr) {
  // 外层循环逐步缩小增量 gap 的值
  for (let gap = 5; gap > 0; gap = Math.floor(gap / 2)) {
    // 中层和内层是插入排序
    // 普通插入排序从第1个元素开始，这里分组了，要看每一组的第1个元素
    // 共分成了 gap 组，第一组的第1个元素索引为 gap
    // 第一组元素索引为 0, 0+gap, 0+2*gap，...，第二组元素索引为 1, 1+gap, 2+2*gap，...
    for (let i = gap; i < arr.length; i++) {
      let current_ele = arr[i]
      // 普通插入排序时，j 每次减少1，即与前面的每个元素比较
      // 这里 j 每次减少 gap，只会与当前元素相隔 n*(gap-1) 的元素比较，也就是只会与同组的元素比较
      let ordered_index = i - gap
      while (ordered_index >= 0 && arr[ordered_index] > current_ele) {
        arr[ordered_index + gap] = arr[ordered_index]
        ordered_index -= gap
      }
      arr[ordered_index + gap] = current_ele
    }
  }
  return arr
}

Быстрая сортировка

Грубый процесс:

Выберите базовый элементpivot, например, первый элемент

Конечно, можно выбрать и другие элементы, но в итоге он будет рекурсивным, пока не останется только один элемент, поэтому надежнее выбрать первый элемент
пройтись по массиву, чемpivotМеньшие элементы создают массив, большие элементы создают массив, а равные элементы создают массив.
Рекурсивно определите размер двух массивов и продолжайте выполнять 1 до тех пор, пока в массиве не останется только 1 элемент; соедините эти три части во время рекурсии

Обычная быстрая сортировка не учитываетpivotВ случае равенства строятся только два массива меньшего и большего размера.
Как и выше, рассмотрим сpivotПри равенстве его также называютБыстрая гребля втроем.

Демонстрационное изображение:

function quickSort(arr) {
  // 只剩1个元素，不能再分割了
  if (arr.length <= 1) return arr
  // 取第1个元素为基准值
  let base = arr[0]
  // 分割为左小右大两个数组，以及包含元素本身的中间数组
  let left = [], middle = [base], right = []
  for (let index = 1; index < arr.length; index++) {
    // 如果有与本身一样大的元素，放入 middle 数组，解决重复元素的问题
    if (arr[index] === base) middle.push(arr[index])
    else if (arr[index] < base) left.push(arr[index])
    else right.push(arr[index])
  }
  // 递归并连接
  return quickSort(left).concat(middle, quickSort(right))
}

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

Это очень типичное приложение «Разделяй и властвуй».

Проще говоря, это уменьшение размера проблемы, а быстрая сортировка — это еще и метод «разделяй и властвуй».

Грубый процесс:

Рекурсивно разделить массив на два подмассива до и после,пока в массиве не будет только 1 элемент

Делим сразу на две половины без сортировки
При этом рекурсивно брать элементы из двух массивов один за другим, сравнивать размер и объединять

Демонстрационное изображение:

// 分割
function mergeSort2(arr) {
  // 如果只剩一个元素，分割结束
  if (arr.length < 2) return arr
  // 否则继续分成两部分
  let middle_index = Math.floor(arr.length / 2),
    left = arr.slice(0, middle_index),
    right = arr.slice(middle_index)
  return merge2(mergeSort2(left), mergeSort2(right))
}
// 合并
function merge2(left, right) {
  let result = []
  // 当左右两个数组都还没有取完的时候，比较大小然后合并
  while (left.length && right.length) {
    if (left[0] < right[0]) result.push(left.shift())
    else result.push(right.shift())
  }
  // 其中一个数组空了，另一个还剩下一些元素
  // 因为是已经排序过的，所以直接concat就好了
  // 注意 concat 不改变原数组
  if (left.length) result = result.concat(left)
  if (right.length) result = result.concat(right)
  return result
}

Сортировка подсчетом

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

Подсчитайте количество вхождений каждого элемента и создайте новый массивarr, индекс нового массива — это значение исходного элемента массива, а значение в каждой позиции — это количество вхождений исходного элемента массива.

Грубый процесс:

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

Демонстрационное изображение:

function countingSort(array) {
  let count_arr = [], result_arr = []
  // 统计出现次数
  for (let i = 0; i < array.length; i++) {
    count_arr[array[i]] = count_arr[array[i]] ? count_arr[array[i]] + 1 : 1
  }
  // 遍历统计数组，放入结果数组
  for (let i = 0; i < count_arr.length; i++) {
    while (count_arr[i] > 0) {
      result_arr.push(i)
      count_arr[i]--
    }
  }
  return result_arr
}

Ведро Сортировка

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

Количество интервалов обычно задается вручную.

Основной процесс:

Инициализировать указанное количество сегментов
Найдите максимальное и минимальное значения массива, возьмите разницу и разделите на количество ведер, чтобы получить диапазон значений в каждом ведреrange
Перебрать массив и разделить значение каждого элемента наrange, целая часть частного — это номер соответствующего ведра, положенного в ведро
При входе в ведро сортировка может выполняться сразу, а не простоpush(), например, используяСортировка вставками
В конце обхода элементы в каждом сегменте сортируются. А так как ведра тоже расставлены по порядку, то сразу все ведра расставить по порядкуconcatвставать

Разумеется, возможны и другие методы сортировки. Но сортировка вставками реализована ближе к цели «добавить элемент в отсортированный массив и сделать его отсортированным».

Демонстрационное изображение:

function bucketSort(array, num) {
  let buckets = [],
    min = Math.min(...array),
    max = Math.max(...array)
  // 初始化 num 个桶
  for (let i = 0; i < num; i++) buckets[i] = []
  // (最大值-最小值)/桶数，得到每个桶最小最大值的差，即区间
  // 比如 range 为10, 0号桶区间为0-10，1号桶10-20，...
  let range = (max - min + 1) / num
  for (let i = 0; i < array.length; i++) {
    // (元素-最小值)/区间，取整数部分，就是应该放入的桶的索引
    let bucket_index = Math.floor((array[i] - min) / range),
      bucket = buckets[bucket_index]
    // 空桶直接放入
    if (bucket.length) {
      bucket.push(array[i])
    }
    // 非空，插入排序
    else {
      let i = bucket.length - 1
      while (i >= 0 && bucket[i] > array[i]) {
        bucket[i + 1] = bucket[i]
        i--
      }
      bucket[i + 1] = array[i]
    }
  }
  // 合并所有桶
  let result = []
  buckets.forEach((bucket) => {
    result = result.concat(bucket)
  })
  return result
}

Отступление, оArrayизfill()метод.

При инициализации массива задумались, можно ли его использоватьlet arr = new Array(4).fill([]), одна строка кода может добавить начальные элементы в массив, поэтому вам не нужно сначала создавать массив, а затемforЭлементы добавляются в цикле.

Но проблема в том,fill()Добавлен элемент ссылочного типа - вот пустой массив[]--Oниуказывает на ту же ссылку. Если один из массивов изменяется, другие массивы также изменяются.

все еще быть честнымforЗадействуйте его.

Сортировка по основанию Сортировка по основанию

Требует, чтобы элементы были равны 0 или положительным целым числам.

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

По порядку сравнения они делятся на две категории:

Младшая значащая цифра, начните сравнение с цифры единиц
Самая значащая цифра, начните сравнение со старшей цифры

Что общего у обоих методов, так это:

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

LSD

Вставьте ЛСД:Lucy in the Sky with Diamonds

Основной процесс:

Сначала лучше посмотреть на демо

Найдите самый большой элемент и получите его количество битов (длину)max_len
внешний цикл сmax_lenПо количеству обходов, начиная с единиц, внутренний цикл обходит массив
Каждый раз, когда внешний цикл сравнивает число на бите элемента
В начале каждого внешнего цикла инициализируются 10 массивов или сегментов, что указывает на то, что число в этом бите является одним из 0-9.
Внутренний обход помещается в соответствующее ведро в соответствии со значением текущего бита каждого элемента.
Каждый раз, когда внешний цикл заканчивается, удаляйте элементы в 10 сегментах по порядку и покрывайте исходный массив, чтобы получить ранжированный массив.

Демонстрационное изображение:

function radixSortLSD(arr) {
  // 找出最大元素
  let max_num = Math.max(...arr),
    // 获取其位数
    max_len = getLengthOfNum(max_num)
  console.log(`最大元素是 ${max_num}，长度 ${max_len}`)
  // 外层遍历位数，内层遍历数组
  // 外层循环以最大元素的位数作为遍历次数
  for (let digit = 1; digit <= max_len; digit++) {
    // 初始化0-9 10个数组，这里暂且叫做桶
    let buckets = []
    for (let i = 0; i < 10; i++) buckets[i] = []
    // 遍历数组
    for (let i = 0; i < arr.length; i++) {
      // 取出一个元素
      let ele = arr[i]
      // 获取当前元素该位上的值
      let value_of_this_digit = getSpecifiedValue(ele, digit)
      // 根据该值，决定当前元素要放到哪个桶里
      buckets[value_of_this_digit].push(ele)
      console.log(buckets)
    }
    // 每次内层遍历结束，把所有桶里的元素依次取出来，覆盖原数组
    let result = []
    buckets.toString().split(',').forEach((val) => {
      if (val) result.push(parseInt(val))
    })
    // 得到了一个排过序的新数组，继续下一轮外层循环，比较下一位
    arr = result
    console.log(arr)
  }
}

function getLengthOfNum(num) { return (num += '').length }

// 获取一个数字指定位数上的值，超长时返回0
// 个位的位数是1，十位的位数是2 ...
function getSpecifiedValue(num, position) { return (num += '').split('').reverse().join('')[position - 1] || 0 }

MSD

У этого нет изображения, но это проще и не требует изображения.

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

Основной процесс:

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

Возьмите два каштана.

Без повторяющихся элементов:

// 原始数组
[110, 24, 27, 56, 9]
// 原数组相当于
[110, 024, 027, 056, 009]
// 第一次入桶，比较最高位百位
[[024, 027, 056, 009], [110]]
// 当桶中有多个元素时，递归。这里就是递归第一个桶
// 第二次入桶，比较十位
[[[009], [024, 027], [056]], [110]]
// 第二个桶中还有元素，继续递归
// 第三次入桶，比较个位
[[[009], [[024], [027]], [056]], [110]]
// 结果就是
[009, 024, 027, 056, 110]

То есть в случае отсутствия повторяющихся элементов конечным результатом рекурсии является только один элемент в каждом сегменте.

С повторяющимися элементами:

[110, 024, 024, 056, 009]
// 第一次入桶，比较百位
[[009, 024, 024, 056], [110]]
// 第二次入桶，比较十位
[[[009], [024, 024], [056]], [110]]
// 第三次入桶，比较个位
[[[009], [[024, 024]], [056]], [110]]

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

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

function radixSortMSD(arr) {
  // 最大元素
  let max_num = Math.max(...arr),
    // 获取其位数作为初始值，最小值为1，也就是个位
    digit = getLengthOfNum(max_num)
  return msd(arr, digit)
}
function msd(arr, digit) {
  // 建10个桶
  let buckets = []
  for (let i = 0; i < 10; i++) buckets[i] = []
  // 遍历数组，入桶。这里跟 LSD 一样
  for (let i = 0; i < arr.length; i++) {
    let ele = arr[i]
    let value_of_this_digit = getSpecifiedValue(ele, digit)
    buckets[value_of_this_digit].push(ele)
  }
  // 结果数组
  let result = []
  // 遍历每个桶
  for (let i = 0; i < buckets.length; i++) {
    // 只剩一个元素，直接加入结果数组
    if (buckets[i].length === 1) result = result.concat(buckets[i])
    // 还有多个元素，但是已经比较到个位了
    // 说明是重复元素的情况，也直接加入结果数组
    else if (buckets[i].length && digit === 1) result = result.concat(buckets[i])
    // 还有多个元素，并且还没有比较结束，递归比较下一位
    else if (buckets[i].length && digit !== 1) result = result.concat(msd(buckets[i], digit - 1))
    // 空桶就不作处理了
  }
  return result
}

Ссылка на ссылку

Краткое изложение 10 лучших классических алгоритмов сортировки (описание JavaScript) Develop Paper
Краткое описание алгоритма сортировки переднего плана — segmentfault
Быстрая сортировка JS и трехсторонняя быстрая сортировка
Графический алгоритм сортировки (2) Сортировка по холму
Сортировка подсчетом, сортировка ведра и сортировка по основанию - segmentfault
Сложность времени — Вики
Сравнительная сортировка — Вики

Рекламировать

Другие мои статьи:

«Углубленный JavaScript, часто используемые 8 схем наследования»
«Добавьте SSL-сертификат на свой сайт бесплатно»
"Подробное объяснение имитационного внедрения new/bind/apply/call"