предисловие

Алгоритм сортировки может быть первым алгоритмом, который вы научитесь программировать.Помните всплытие?

Конечно, алгоритмы сортировки и поиска — популярные варианты интервью. Если вы программист, который может написать быструю сортировку, интервьюер выберет вас первым, сравнивая вас с кем-то, кто даже не может написать быструю сортировку. Итак, переднюю часть нужно сортировать? Ответ бесспорный, так и должно быть. Нынешний фронтенд предъявляет все более высокие требования к компьютерным основам, и если эти алгоритмы нельзя будет даже разобрать, то перспективы развития будут ограничены. В этой статье будут обобщены некоторые алгоритмы сортировки во внешнем интерфейсе. Если вам понравилась моя статья, добро пожаловать в комментарии, добро пожаловать в Star~. Добро пожаловать, чтобы следовать за мнойблог на гитхабе

текст

Прежде всего, мы можем взглянуть на алгоритм сортировки sort() самого js.

Array.sort

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

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

console.log(arr.sort());   //[ 1, 10, 100, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88 ]

console.log(arr.sort((item1, item2) => item1 - item2)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

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

Производительность функции сортировки. Считается, что временная сложность является решающим фактором для производительности алгоритма сортировки. Итак, какова алгоритмическая производительность функции сортировки? Через двигатель v8исходный кодВидно, что Array.sort реализован javascript, а используемый алгоритм — быстрая сортировка, но с точки зрения исходного кода реализация явно сложнее используемой нами быстрой сортировки, в основном для оптимизации производительности. Итак, мы можем безопасно использовать sort() для сортировки.

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

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

Вспомнил вышеприведенный алгоритм, с++ или первокурсник. Или свой собственный офис, чтобы добиться его на доске!

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

легенда:

Код:

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function bubbleSort(arr){
  for(let i = 0; i < arr.length - 1; i++){
    for(let j = 0; j < arr.length - i - 1; j++){
      if(arr[j] > arr[j + 1]){
        swap(arr, j, j+1);
      }
    }
  }
  return arr;
}

function swap(arr, i, j){
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}
console.log(arr);

кодовый адрес

представление:

• Временная сложность: средняя временная сложность составляет O (n ^ 2)
• Сложность пространства: поскольку вспомогательное пространство постоянно, сложность пространства равна O (1);

Улучшать:

Мы можем улучшить пузырьковую сортировку, чтобы в большинстве случаев ее временная сложность уменьшилась до O(n);

1. Добавляем флаговый бит, если обмена нет, устанавливаем флаговый бит в false, указывая на то, что сортировка завершена.

кодовый адрес

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function swap(arr, i, j){
  const temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

for(let i = 0; i < arr.length - 1; i++){
  let flag = false;
  for(let j = 0; j < arr.length - 1 - i; j++){
    if(arr[j] > arr[j+1]){
      swap(arr, j, j+1);
      flag = true;
    }
  }

  if(!flag){
    break;
  }
}

console.log(arr);  //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

1. Запишите позицию последней биржи, потому что номер последней биржи является наибольшим числом в этой сортировке, а последующие номера больше его. В лучшем случае временная сложность также уменьшится до O(n);

кодовый адрес

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50 ,112];

function swap(arr, i, j){
  let temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp
}

function improveBubble(arr, len){
  for(let i = len - 1; i >= 0; i--){
    let pos = 0;
    for(let j = 0; j < i; j++){
      if(arr[j] > arr[j+1]){
        swap(arr, j, j+1);
        pos = j + 1;
      }
    }
    len = pos + 1;
  }
  return arr;
}

console.log(improveBubble(arr, arr.length));  //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]

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

Сортировка выбором, то есть каждый раз выбирать наименьшее, а потом менять местами

Идеи:

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

легенда:

Код:

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 31, 88, 12, 100, 50];

function swap(arr, i, j){
  var temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

function selectionSort(arr){
  for(let i = 0; i < arr.length - 1; i++){
    let index = i;
    for(let j = i+1; j < arr.length; j++){
      if(arr[index] > arr[j]){
        index = j;
      }
    }
    swap(arr, i, index);
  }
  return arr;
}

console.log(selectionSort(arr)); //[ 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100 ]

кодовый адрес

представление:

• Временная сложность: средняя временная сложность составляет O (n ^ 2), что является нестабильным алгоритмом, поскольку после каждого обмена он меняет порядок последующих массивов.

• Пространственная сложность: вспомогательное пространство постоянно, а пространственная сложность равна O(1);

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

Сортировка вставками, вставка элементов в отсортированный массив

Идеи:

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

легенда:

Код:

const arr = [1, 20, 10, 30, 22, 11, 55, 24, 0, 31, 88, 12, 100, 50 ,112];

function insertSort(arr){
  for(let i = 0; i < arr.length; i++){
    let temp = arr[i];
    for(let j = 0; j < i; j++){
      if(temp < arr[j] && j === 0){
        arr.splice(i, 1);
        arr.unshift(temp);
        break;
      }else if(temp > arr[j] && temp < arr[j+1] && j < i - 1){
        arr.splice(i, 1);
        arr.splice(j+1, 0, temp);
        break;
      }
    }
  }
  return arr;
}

console.log(insertSort(arr));  //[ 0, 1, 10, 11, 12, 20, 22, 24, 30, 31, 50, 55, 88, 100, 112 ]

кодовый адрес

представление:

• Временная сложность: средняя сложность алгоритма составляет O (n ^ 2)
• Сложность пространства: вспомогательное пространство постоянно, а сложность пространства равна O(1).

между нами тремя

На самом деле эти три алгоритма — трудные братья, потому что временная сложность алгоритмов составляет O(n^2). В худшем случае они оба требуют масштабирования всего массива. Просто сортировка выбором менее стабильна.

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

Быстрая сортировка, как следует из названия, работает быстро, имеет низкую временную сложность и хорошую производительность. Это уменьшает временную сложность алгоритма сортировки до O (nlogn).

Идеи:

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

легенда:

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

Исходный адрес изображения

Код:

const arr = [30, 32, 6, 24, 37, 32, 45, 21, 38, 23, 47];

function quickSort(arr){
  if(arr.length <= 1){
    return arr;
  }
  let temp = arr[0];
  const left = [];
  const right = [];
  for(var i = 1; i < arr.length; i++){
    if(arr[i] > temp){
      right.push(arr[i]);
    }else{
      left.push(arr[i]);
    }
  }
  return quickSort(left).concat([temp], quickSort(right));
}

console.log(quickSort(arr));

кодовый адрес

представление:

• Временная сложность: средняя временная сложность O(nlogn), только в особых случаях будет O(n^2), но это очень редко
• Сложность пространства: вспомогательное пространство равно logn, поэтому сложность пространства равна O(logn)

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

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

Идеи:

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

легенда:

Код:

//迭代版本
const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48]

function mergeSort(arr){
  const len = arr.length;

  for(let seg = 1; seg < len; seg += seg){
    let arrB = [];
    for(let start = 0; start < len; start += 2*seg){
      let row = start, mid = Math.min(start+seg, len), heig = Math.min(start + 2*seg, len);
      let start1 = start, end1 = mid;
      let start2 = mid, end2 = heig;
      while(start1 < end1 && start2 < end2){
        arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);
      }
      while(start1 < end1){
        arrB.push(arr[start1++]);
      }
      while(start2 < end2){
        arrB.push(arr[start2++]);
      }
    }
    arr = arrB;
  }

  return arr;
}

console.log(mergeSort(arr));

кодовый адрес

//递归版
const arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];

function mergeSort(arr, seg = 1){
  const len = arr.length;
  if(seg > len){
    return arr;
  }
  const arrB = [];
  for(var start = 0; start < len; start += 2*seg){
    let low = start, mid = Math.min(start+seg, len), heig = Math.min(start+2*seg, len);
    let start1 = low, end1 = mid;
    let start2 = mid, end2 = heig;
    while(start1 < end1 && start2 < end2){
      arr[start1] < arr[start2] ? arrB.push(arr[start1++]) : arrB.push(arr[start2++]);
    }
    while(start1 < end1){
      arrB.push(arr[start1++]);
    }
    while(start2 < end2){
      arrB.push(arr[start2++]);
    }
  }
  return mergeSort(arrB, seg * 2);
}

console.log(mergeSort(arr));

кодовый адрес

представление:

• Временная сложность: средняя временная сложность O (nlogn)
• Сложность пространства: вспомогательное пространство равно n, а сложность пространства равна O (n).

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

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

Идеи:

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

легенда:

Код:

const arr = [3221, 1, 10, 9680, 577, 9420, 7, 5622, 4793, 2030, 3138, 82, 2599, 743, 4127, 10000];

function radixSort(arr){
  let maxNum = Math.max(...arr);
  let dis = 0;
  const len = arr.length;
  const count = new Array(10);
  const tmp = new Array(len);
  while(maxNum >=1){
    maxNum /= 10;
    dis++;
  }
  for(let i = 1, radix = 1; i <= dis; i++){
    for(let j = 0; j < 10; j++){
      count[j] = 0;
    }
    for(let j = 0; j < len; j++){
      let k = parseInt(arr[j] / radix) % 10;
      count[k]++;
    }
    for(let j = 1; j < 10; j++){
      count[j] += count[j - 1];
    }
    for(let j = len - 1; j >= 0 ; j--){
      let k = parseInt(arr[j] / radix) % 10;
      tmp[count[k] - 1] = arr[j];
      count[k]--;
    }
    for(let j = 0; j < len; j++){
      arr[j] = tmp[j]; 
    }
    radix *= 10;
  }
  return arr;
}

console.log(radixSort(arr));

кодовый адрес

представление:

• Временная сложность: средняя временная сложность составляет O (k * n), а в худшем случае — O (n ^ 2).

Суммировать

Всего мы реализовали алгоритмов сортировки 6. Для front-end разработки знакомство с первыми 4-мя обязательно. Особенно быстрый ряд, основные вопросы интервью. Краткое содержание этой статьи разделено на шесть частей:

• Пузырьковая сортировка
• сортировка выбором
• Сортировка вставками
• быстрая сортировка
• Сортировка слиянием
• сортировка по основанию

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

Если у вас есть какие-либо вопросы по поводу того, что я написал, вы можете прокомментировать.Если есть ошибка в том, что я написал, пожалуйста, поправьте меня. Если вам нравится мой блог, подписывайтесь на меня в Star~ Yo. Давайте добиваться прогресса вместе. Добро пожаловать, чтобы следовать за мнойблог на гитхабе