Финишная обработка алгоритма и перепечатка

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

Пузырьковая сортировка требует двух вложенных циклов.外层循环переместить курсор;内层循环Перемещайтесь по курсору и элементам после (или до) и только убедитесь, что конечная позиция внутреннего цикла каждый раз правильно сортируется, заменяя их парами, а затем内层循环Конец цикла, сдать外层循环Переместите курсор назад (или вперед), чтобы начать следующий раунд.内层循环, и так до конца цикла.

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

Поскольку существует два слоя циклов, возможны четыре реализации.

строить планы	внешний цикл	внутренняя петля
1	положительная последовательность	положительная последовательность
2	положительная последовательность	обратный порядок
3	обратный порядок	положительная последовательность
4	обратный порядок	обратный порядок

Четыре разных направления циркуляции имеют немного разные реализации.

Ниже приведен эффект анимации (соответствует схеме 1: все внутренние/внешние циклы проходят в положительном порядке.

Ниже приведен алгоритм реализации приведенного выше рисунка (соответствующийВариант первый: оба внутренних/внешних цикла проходят в положительном порядке).

//先将交换元素部分抽象出来
function swap(i,j,array){
  var temp = array[j];
  array[j] = array[i];
  array[i] = temp;
}

function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = 0; i < length; i++) {            //正序
    isSwap = false;
    for (var j = 0; j < length - 1 - i; j++) {     //正序
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

Выше приведены характеристики сортировки: сначала определяется положение более позднего элемента.

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

function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = 0; i < length; i++) {            //正序
    isSwap = false;
    for (var j = length - 1; j >= i+1; j--) {     //逆序
      array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

Выше сначала определяется положение переднего элемента.

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

function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = length - 1; i >= 0; i--) {     //逆序
    isSwap = false;
    for (var j = 0; j < i; j++) {            //正序
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

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

Вариант 4: внешний цикл проходится в обратном порядке, а внутренний цикл проходится в обратном порядке Код выглядит следующим образом:

function bubbleSort(array) {
  var length = array.length, isSwap;
  for (var i = length - 1; i >= 0; i--) {                //逆序
    isSwap = false;
    for (var j = length - 1; j >= length - 1 - i; j--) { //逆序
      array[j] < array[j-1] && (isSwap = true) && swap(j,j-1,array);
    }
    if(!isSwap)
      break;
  }
  return array;
}

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

Ниже приводится его алгоритмическая сложность:

Средняя временная сложность	лучший случай	худший случай	космическая сложность
O(n²)	O(n)	O(n²)	O(1)

Пузырьковую сортировку проще всего реализовать. В худшем случае ее нужно менять местами каждый раз. Ее нужно пройти и поменять местами почти n²/2 раза, а временная сложность равна O(n²). В лучшем случае это внутренний цикл пройден один раз Обнаружено, что сортировка верна, поэтому сложность времени составляет O (n) для выхода из цикла. В среднем сложность времени составляет O (n²). Поскольку только кешированная временная переменная требует места в памяти в пузырьковой сортировке пространство комплексное Степень постоянна O (1).

Двусторонняя пузырьковая сортировка

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

Ниже приведена реализация алгоритма:

function bothwayBubbleSort(array){
  var tail = array.length-1, i, isSwap = false;
  for(i = 0; i < tail; tail--){
    for(var j = tail; j > i; j--){    //第一轮, 先将最小的数据冒泡到前面
      array[j-1] > array[j] && (isSwap = true) && swap(j,j-1,array);
    }
    i++;
    for(j = i; j < tail; j++){        //第二轮, 将最大的数据冒泡到后面
      array[j] > array[j+1] && (isSwap = true) && swap(j,j+1,array);
    }
  }
  return array;
}

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

С точки зрения логики алгоритма сортировка выбором — это простой и интуитивно понятный алгоритм сортировки, а также двухслойный цикл.内层循环Как рабочий, он действительно делает вещи,内层循环Каждый раз, когда он выполняется, наименьший (или самый большой) один из элементов, подлежащих сортировке, на этот раз будет выбран и сохранен в начальной позиции массива.外层循环то как босс, это говорит内层循环Вам нужно продолжать работать до тех пор, пока работа не будет выполнена (то есть все элементы не будут отсортированы).

: Элементы, обмениваемые каждый раз при сортировке выбором, могут быть не соседними, поэтому может нарушиться порядок между элементами с одинаковым исходным значением.Например, в массиве [2,2,1,3] при сортировке вперед первый Число 2 будет заменено числом 1, тогда порядок между двумя числами 2 будет несовместим с первоначальным порядком,Хотя их значения одинаковы, их относительный порядок изменился, Мы называем это явление不稳定性 .

Ниже приведен эффект анимации:

Ниже приведен алгоритм реализации приведенного выше рисунка:

function selectSort(array) {
  var length = array.length, min;
  for (var i = 0; i < length - 1; i++) {
    min = i;
    for (var j = i + 1; j < length; j++) {
      array[j] < array[min] && (min = j); //记住最小数的下标
    }
    min!=i && swap(i,min,array);
  }
  return array;
}

Ниже приводится его алгоритмическая сложность:

Средняя временная сложность	лучший случай	худший случай	космическая сложность
O(n²)	O(n²)	O(n²)	O(1)

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

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

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

Из-за различных операций сортировку вставками можно разделить на直接插入排序 , 折半插入排序(иначе двоичная сортировка вставками),链表插入排序 , 希尔排序 .

сортировка прямой вставкой

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

Ниже приведен эффект анимации:

Ниже приведен алгоритм реализации приведенного выше рисунка:

function directInsertionSort(array) {
  var length = array.length, index, current;
  for (var i = 1; i < length; i++) {
    index = i - 1;         //待比较元素的下标
    current = array[i];     //当前元素
    while(index >= 0 && array[index] > current) { //前置条件之一:待比较元素比当前元素大
      array[index+1] = array[index];    //将待比较元素后移一位
      index--;                           //游标前移一位
      //console.log(array);
    }
    if(index+1 != i){                   //避免同一个元素赋值给自身
      array[index+1] = current;            //将当前元素插入预留空位
      //console.log(array);
    }        
  }
  return array;
}

Чтобы лучше наблюдать за процессом реализации прямой сортировки вставками, мы можем добавить комментарии к приведенному выше коду.В качестве примера рассмотрим массив [5,4,3,2,1]. исходный массив.

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

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

сортировка с половинной вставкой

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

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

Основная идея алгоритма такова:

1. Возьмем среднюю точку 0 ~ i-1 (m = (i-1)>>1), array[i] сравнивается с array[m], если array[i]
2. Повторяйте шаг 1, каждый раз сужая диапазон поиска вдвое, пока не будет найдена позиция вставки.
3. Сдвигает все элементы в массиве после позиции вставки назад на единицу.
4. Вставляет i-й элемент в указанную позицию.

Примечание:x>>1Это операция сдвига вправо в битовой операции, что означает сдвиг на один бит вправо, что эквивалентно делению x на 2 с последующим округлением, то естьx>>1 == Math.floor(x/2) .

Ниже приведена реализация алгоритма:

function binaryInsertionSort(array){
  var current, i, j, low, high, m;
  for(i = 1; i < array.length; i++){
    low = 0;
    high = i - 1;
    current = array[i];

    while(low <= high){            //步骤1&2:折半查找
      m = (low + high)>>1;
      if(array[i] >= array[m]){//值相同时, 切换到高半区，保证稳定性
        low = m + 1;        //插入点在高半区
      }else{
        high = m - 1;        //插入点在低半区
      }
    }
    for(j = i; j > low; j--){     //步骤3:插入位置之后的元素全部后移一位
      array[j] = array[j-1];
    }
    array[low] = current;         //步骤4:插入该元素
  }
  return array;
}

Для удобства сравнения в качестве примера также взят массив [5,4,3,2,1]🌰 Процесс эволюции исходного массива выглядит следующим образом (такой же, как и выше):

Хотя половинная сортировка вставками значительно сокращает количество запросов, количество перемещений элементов массива не меняется, их временная сложность составляет O(n²).

Сортировка холмов

Сортировка Хилла, также известная как инкрементная сортировка с сокращением, является еще одной усовершенствованной версией сортировки с прямым вставкой, которая по существу представляет собой групповую сортировку вставками.Сортировка Хилла названа в честь ее разработчика Дональда Шелла и была анонсирована в 1959 году.

Основная идея алгоритма:

1. Разбить массив на несколько подгрупп, каждая из которых состоит из элементов, разделенных определенным «шагом», например, разделить Массив разбит на группы с «шагом» 5, тогда подгруппы равны [0,5 ], [1,6], [2,7], [3,8], [4,9] и [5], 10].
2. Затем примените встроенную сортировку вставками к каждой подгруппе.
3. Постепенно уменьшайте «приращение», повторяя шаги 1, 2.
4. Пока «приращение» не равно 1, это последняя сортировка, и сортировка в это время заключается в выполнении прямой сортировки вставкой для всего массива.

Ниже представлена ​​схема сортировки:

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

Мы пытаемся абстрагироваться от общих моментов, и нетрудно обнаружить, что четвертый шаг вышеупомянутой сортировки Хилла является прямой сортировкой вставкой, а сортировка Хилла первоначально начинается с «приращения» n до «приращения " равен 1, а циклы Инкапсуляция применения сортировки прямым вставками. Следовательно, сортировку прямым вставками можно рассматривать как сортировку Хилла с размером шага 1. По этой причине мы сначала инкапсулируем сортировку прямыми вставками.

//形参增加步数gap(实际上就相当于gap替换了原来的数字1)
function directInsertionSort(array, gap) {
  gap = (gap == undefined) ? 1 : gap;       //默认从下标为1的元素开始遍历
  var length = array.length, index, current;
  for (var i = gap; i < length; i++) {
    index = i - gap;    //待比较元素的下标
    current = array[i];    //当前元素
    while(index >= 0 && array[index] > current) { //前置条件之一:待比较元素比当前元素大
      array[index + gap] = array[index];    //将待比较元素后移gap位
      index -= gap;                           //游标前移gap位
    }
    if(index + gap != i){                   //避免同一个元素赋值给自身
      array[index + gap] = current;            //将当前元素插入预留空位
    }
  }
  return array;
}

Тогда алгоритм сортировки Хилла реализуется следующим образом:

function shellSort(array){
  var length = array.length, gap = length>>1, current, i, j;
  while(gap > 0){
    directInsertionSort(array, gap); //按指定步长进行直接插入排序
    gap = gap>>1;
  }
  return array;
}

Также возьмем в качестве примера массив [5,4,3,2,1]🌰 Процесс эволюции исходного массива выглядит следующим образом:

По сравнению с упомянутыми выше сортировкой прямым вставкой и сортировкой с половинным вставкой количество перемещений элементов массива сокращается с 14 раз до 7. За счет разбиения исходного массива на подмассивы с меньшей степенью детализации сортировка Хилла дополнительно улучшает сортировку. эффективность.

Мало того, указанные выше шаги установлены на {N/2, (N/2)/2, ..., 1}.Приращение холма, другие инкрементные последовательности включают Хиббарда: {1, 3, ..., 2 ^ k-1}. Разумно регулируя размер шага, эффективность сортировки может быть дополнительно улучшена. Фактически, наиболее известная последовательность размера шага предложена Sedgewick (1, 5, 19, 41, 109,…). Члены этой последовательности: 9*4^i - 9*2^i + 1 или 4^i - 3*2^i + 1. Пожалуйста, нажмите подробностиСортировка по холмам — Википедия .

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

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

Сортировка слиянием основана на операции слияния, она принимает идею «разделяй и властвуй», которая делит массив на два подмассива, сортирует их отдельно и, наконец, объединяет два подмассива; два подмассива разбиваются , а затем продолжить рекурсивное разбиение на более мелкие. , а затем отсортировать их по отдельности, пока длина массива не станет равной 1, и вернуть массив напрямую.

: сортировка слиянием объединяет подмассивы в строгом порядке слева направо (или справа налево), она не меняет относительный порядок между одними и теми же элементами, поэтому это также стабильный алгоритм сортировки.

Ниже приведен эффект анимации:

Сортировка слиянием может быть реализована двумя способами:

1. рекурсия сверху вниз
2. восходящая итерация

Ниже приведена реализация алгоритма (режим 1: рекурсия):

function mergeSort(array) {  //采用自上而下的递归方法
  var length = array.length;
  if(length < 2) {
    return array;
  }
  var m = (length >> 1),
      left = array.slice(0, m),
      right = array.slice(m); //拆分为两个子数组
  return merge(mergeSort(left), mergeSort(right));//子数组继续递归拆分,然后再合并
}
function merge(left, right){ //合并两个子数组
  var result = [];
  while (left.length && right.length) {
    var item = left[0] <= right[0] ? left.shift() : right.shift();//注意:判断的条件是小于或等于,如果只是小于,那么排序将不稳定.
    result.push(item);
  }
  return result.concat(left.length ? left : right);
}

Сверху массив длины n в конечном итоге вызовет функцию mergeSort 2n-1 раз Сортировка слиянием, реализованная с помощью рекурсии сверху вниз, будет иметь риск переполнения стека Проверьте рекурсию, необходимую для переполнения стека каждого браузера Количество звонки примерно:

• Chrome v55: 15670
• Firefox v50: 44488
• Safari v9.1.2: 50755

Вот тестовый код:

function computeMaxCallStackSize() {
  try {
    return 1 + computeMaxCallStackSize();
  } catch (e) {
    // Call stack overflow
    return 1;
  }
}
var time = computeMaxCallStackSize();
console.log(time);

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

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

Ниже приводится его алгоритмическая сложность:

Средняя временная сложность	лучший случай	худший случай	космическая сложность
О(nlog₂n)	О(nlog₂n)	О(nlog₂n)	O(n)

С точки зрения эффективности сортировку слиянием можно считать «отличной» среди алгоритмов сортировки.Если предположить, что длина массива равна n, то для разделения массива требуется logn шагов, и каждый шаг представляет собой обычный процесс слияния подмассивов. Временная сложность O (n), поэтому его комплексная временная сложность O (nlogn), С другой стороны, подмассивы, разделенные в рекурсивном процессе сортировки слиянием, должны храниться в пространстве памяти, а его пространственная сложность O ( н).

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

Быстрая сортировка заимствует идею "разделяй и властвуй" и совершенствует ее на основе пузырьковой сортировки. Она была предложена К. А. Хоаром в 1962 г. Она разбивает массив на два подмассива, один из которых содержит больше элементов, чем другой. Элементы маленькие, а затем повторять описанную выше операцию для этих двух подмассивов до тех пор, пока массив нельзя будет разделить и сортировка не будет завершена.

Ниже приведен эффект анимации:

Ниже приведена реализация алгоритма:

function quickSort(array, left, right) {
  var partitionIndex,
      left = typeof left == 'number' ? left : 0,
      right = typeof right == 'number' ? right : array.length-1;
  if (left < right) {
    partitionIndex = partition(array, left, right);//切分的基准值
    quickSort(array, left, partitionIndex-1);
    quickSort(array, partitionIndex+1, right);
  }
  return array;
}
function partition(array, left ,right) {   //分区操作
  for (var i = left+1, j = left; i <= right; i++) {//j是较小值存储位置的游标
    array[i] < array[left] && swap(i, ++j, array);//以第一个元素为基准
  }
  swap(left, j, array);            //将第一个元素移至中间
  return j;
}

Ниже приводится его алгоритмическая сложность:

Средняя временная сложность	лучший случай	худший случай	космическая сложность
О(nlog₂n)	О(nlog₂n)	O(n²)	О(nlog₂n)

Быстрая сортировка очень эффективна, хотя в худшем случае она достигает временной сложности O(n²), в целом в среднем ее временная сложность составляет O(nlogn), что сложнее, чем такая же временная сложность O(nlogn) Сортировка слиянием степени даже быстрее.Быстрая сортировка, кажется, предпочитает неупорядоченную последовательность, чем более неупорядоченная последовательность, тем она относительно более эффективна, чем другие сортировки.Взгляните на массив JSВ статье упоминаются:Для эффективной сортировки движок Chrome v8 использует быструю сортировку, когда отсортированных данных больше 10. Сортировка вставками используется для данных, содержащих 10 или менее элементов.

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

сортировка кучей

Лауреаты премии Computer Pioneer Award 1991 года и профессора компьютерных наук Стэнфордского университета Роберт У. Флойд (Robert W. Floyd) и Уильямс (J. Williams) совместно изобрели знаменитый алгоритм Heap Sort в 1964 году.

Сортировка кучей — это алгоритм сортировки, разработанный с использованием структуры данных кучи. Это тип сортировки выбором. Куча делится на большую корневую кучу и маленькую корневую кучу. Большая корневая куча требует, чтобы значение каждого дочернего узла не больше, чем у его родительского узла.значение, то есть array[childIndex]

Не все последовательности являются кучами.Для последовательностей k1,k2,…kn должны выполняться следующие условия:

• ki =, тогда это большая корневая куча. можно заменить Куча здесь рассматривается как полное бинарное дерево, k(i) эквивалентно нелистовому узлу бинарного дерева, k(2i) — левый дочерний узел, а k(2i+1) — правый дочерний узел.

Основная идея алгоритма (в качестве примера возьмем большую корневую кучу):

1. Во-первых, встройте исходную последовательность K[1..n] в большую кучу корней, которая является исходной неупорядоченной областью.
2. Затем запишите K с самым большим ключевым словом1(то есть вершина кучи) и последняя запись K[n] неупорядоченной области меняются местами, в результате чего получается новая неупорядоченная область K[1..n-1] и упорядоченная область K[n], и удовлетворить K[1 ..n-1].keys≤K[n].key
3. обмен К1После и K[n] вершина кучи может нарушить свойство кучи, поэтому необходимо настроить K[1..n-1] на кучу.Затем повторять шаг 2, пока неупорядоченная область не будет иметь только один элемент и остановись.

Ниже приведен эффект анимации:

Ниже приведена реализация алгоритма:

function heapAdjust(array, i, length) {//堆调整
  var left = 2 * i + 1,
      right = 2 * i + 2,
      largest = i;
  if (left < length && array[largest] < array[left]) {
    largest = left;
  }
  if (right < length && array[largest] < array[right]) {
    largest = right;
  }
  if (largest != i) {
    swap(i, largest, array);
    heapAdjust(array, largest, length);
  }
}
function heapSort(array) {
  //建立大顶堆
  length = array.length;
  for (var i = length>>1; i >= 0; i--) {
    heapAdjust(array, i, length);
  }
  //调换第一个与最后一个元素,重新调整为大顶堆
  for (var i = length - 1; i > 0; i--) {
    swap(0, i, array);
    heapAdjust(array, 0, --length);
  }
  return array;
}

Выше ① процесс построения кучи от length/2 до 0 имеет временную сложность O(n);

② Процесс настройки кучи заключается в настройке по родительскому и дочернему узлам кучи, количество выполнений - это глубина кучи, а временная сложность - O (lgn);

③Процесс сортировки кучи завершается вторым шагом n раз, а временная сложность равна O(nlgn).

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

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

Сортировка подсчетом — чуть ли не единственный алгоритм сортировки, не основанный на сравнении.Алгоритм был предложен Гарольдом Х. Сьюардом в 1954 г. Когда он используется для обработки целочисленной сортировки в определенном диапазоне, временная сложность составляет O(n+k). , где k — целочисленный диапазон, он быстрее почти любого алгоритма сортировки на основе сравнения (только когда O(k)>O(n*log(n)), он не так эффективен, как сортировка на основе сравнения, например слияние сортировка и сортировка кучи).

Для сортировки по количеству необходимо выполнение следующих условий:

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

Основная идея алгоритма:

Сортировка подсчетом использует функцию: для элемента массива, когда вы знаете, сколько других элементов меньше его (при условии, что m), вы можете определить правильное положение элемента (m + 1-й бит)

1. Получить максимальное и минимальное значения массива A для сортировки.
2. Создайте новый массив счетчиков B с разницей между максимальным значением и минимальным значением + 1 в качестве длины и сохраните количество тех же элементов в качестве значения в массиве счетчиков.
3. Подсчитайте массив счетчиков B и сохраните начальные индексы разных значений.
4. Берем значения из исходного массива A одно за другим, присваиваем их соответствующим индексам нового массива C и, наконец, возвращаем массив C.

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

Ниже приведен эффект анимации:

Ниже приведена реализация алгоритма:

function countSort(array, keyName){
  var length = array.length,
      output = new Array(length),
      max,
      min,
      simpleArray = keyName ? array.map(function(v){
        return v[keyName];
      }) : array; // 如果keyName是存在的，那么就创建一个只有keyValue的简单数组

  // 获取最大最小值
  max = min = simpleArray[0];
  simpleArray.forEach(function(v){
    v > max && (max = v);
    v < min && (min = v);
  });
  // 获取计数数组的长度
  var k = max - min + 1;
  // 新建并初始化计数数组
  var countArray = new Array(k);
  simpleArray.forEach(function(v){
    countArray[v - min]= (countArray[v - min] || 0) + 1;
  });
  // 累加计数，存储不同值的初始下标
  countArray.reduce(function(prev, current, i, arr){
    arr[i] = prev;
    return prev + current;
  }, 0);
  // 从原数组挨个取值(因取的是原数组的相应值，只能通过遍历原数组来实现)
  simpleArray.forEach(function(v, i){
    var j = countArray[v - min]++;
    output[j] = array[i];
  });
  return output;
}

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

var a = [2, 1, 1, 3, 2, 1, 4, 2],
    b = [
      {id: 2, s:'a'}, 
      {id: 1, s: 'b'}, 
      {id: 1, s: 'c'}, 
      {id: 3, s: 'd'}, 
      {id: 2, s: 'e'}, 
      {id: 1, s: 'f'}, 
      {id: 4, s: 'g'}, 
      {id: 2, s: 'h'}
    ];
countSort(a); // [1, 1, 1, 2, 2, 2, 3, 4]
countSort(b, 'id'); // [{id:1,s:'b'},{id:1,s:'c'},{id:1,s:'f'},{id:2,s:'a'},{id:2,s:'e'},{id:2,s:'h'},{id:3,s:'d'},{id:4,s:'g'}]

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

сортировка ведром

Bucket sort – это так называемая бинарная сортировка, при которой массив распределяется по конечному числу сегментов. Затем каждый сегмент сортируется отдельно (поэтому можно использовать другой алгоритм сортировки или рекурсивно продолжить сортировку сегмента). Когда сортируется каждый сегмент Когда количество элементов в корзине остается одинаковым, сортировка корзины занимает всего O(n) времени Сортировка корзины повышает эффективность за счет замены пространства на время, поэтому для нее требуется дополнительное пространство для хранения (то есть место в корзине).

Основная идея алгоритма:

Суть сортировки ведрами заключается в том, как равномерно распределить элементы в каждом ведре, а разумное распределение значительно повысит эффективность сортировки.

Ниже приведена реализация алгоритма:

function bucketSort(array, bucketSize) {
  if (array.length === 0) {
    return array;
  }

  var i = 1,
      min = array[0],
      max = min;
  while (i++ < array.length) {
    if (array[i] < min) {
      min = array[i];                //输入数据的最小值
    } else if (array[i] > max) {
      max = array[i];                //输入数据的最大值
    }
  }

  //桶的初始化
  bucketSize = bucketSize || 5; //设置桶的默认大小为5
  var bucketCount = ~~((max - min) / bucketSize) + 1, //桶的个数
      buckets = new Array(bucketCount); //创建桶
  for (i = 0; i < buckets.length; i++) {
    buckets[i] = []; //初始化桶
  }

  //将数据分配到各个桶中,这里直接按照数据值的分布来分配,一定范围内均匀分布的数据效率最为高效
  for (i = 0; i < array.length; i++) {
    buckets[~~((array[i] - min) / bucketSize)].push(array[i]);
  }

  array.length = 0;
  for (i = 0; i < buckets.length; i++) {
    quickSort(buckets[i]); //对每个桶进行排序，这里使用了快速排序
    for (var j = 0; j < buckets[i].length; j++) {
      array.push(buckets[i][j]); //将已排序的数据写回数组中
    }
  }
  return array;
}

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

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

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

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

Существует две реализации сортировки по высокому или низкому приоритету:

• MSD: На основе старшего порядка, сначала отсортируйте и сгруппируйте по k1, запишите в той же группе, код ключа k1 равен, а затем отсортируйте каждую группу на подгруппы в соответствии с k2, а затем продолжите сортировку и группировку следующих кодов ключей таким образом до самого После того, как подгруппы отсортированы по вторичному ключу kd, затем группы соединяются для получения упорядоченной последовательности.Метод MSD подходит для последовательностей с большим количеством цифр.
• LSD: начиная с младшего порядка в качестве базы, сначала сортируйте от kd, затем сортируйте kd-1 и повторяйте до тех пор, пока не будет отсортировано k1, чтобы получить упорядоченную последовательность.Метод LSD подходит для последовательностей с меньшим количеством цифр.

Ниже приведен анимационный эффект ЛСД:

)

Ниже приведена реализация алгоритма:

function radixSort(array, max) {
    var buckets = [],
        unit = 10,
        base = 1;
    for (var i = 0; i < max; i++, base *= 10, unit *= 10) {
        for(var j = 0; j < array.length; j++) {
            var index = ~~((array[j] % unit) / base);//依次过滤出个位,十位等等数字
            if(buckets[index] == null) {
                buckets[index] = []; //初始化桶
            }
            buckets[index].push(array[j]);//往不同桶里添加数据
        }
        var pos = 0,
            value;
        for(var j = 0, length = buckets.length; j < length; j++) {
            if(buckets[j] != null) {
                while ((value = buckets[j].shift()) != null) {
                      array[pos++] = value; //将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
                }
            }
        }
    }
    return array;
}

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

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

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

резюме

Ниже приведены различные сравнения производительности сортировки:

Тип сортировки	Средняя ситуация	лучший случай	худший случай	вспомогательное пространство	стабильность
Пузырьковая сортировка	O(n²)	O(n)	O(n²)	O(1)	стабилизировать
сортировка выбором	O(n²)	O(n²)	O(n²)	O(1)	нестабильный
сортировка прямой вставкой	O(n²)	O(n)	O(n²)	O(1)	стабилизировать
сортировка с половинной вставкой	O(n²)	O(n)	O(n²)	O(1)	стабилизировать
Сортировка холмов	O(n^1.3)	O(nlogn)	O(n²)	O(1)	нестабильный
Сортировка слиянием	О(nlog₂n)	О(nlog₂n)	О(nlog₂n)	O(n)	стабилизировать
быстрая сортировка	О(nlog₂n)	О(nlog₂n)	O(n²)	О(nlog₂n)	нестабильный
сортировка кучей	О(nlog₂n)	О(nlog₂n)	О(nlog₂n)	O(1)	нестабильный
сортировка по подсчету	O(n+k)	O(n+k)	O(n+k)	O(k)	стабилизировать
сортировка ведром	O(n+k)	O(n+k)	O(n²)	O(n+k)	(не)стабильный
сортировка по основанию	O(d(n+k))	O(d(n+k))	O(d(n+kd))	O(n+kd)	стабилизировать

Примечание. Стабильность сортировки ведра зависит от стабильности сортировки в ведре, поэтому ее стабильность сомнительна.При сортировке по основанию k представляет мощность ключевого слова, d представляет длину, а n представляет количество ключевых слов.

Я надеюсь, что эта статья пропустит мой давний курс алгоритмов.

Продолжение следует...