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

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

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

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

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

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

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

Мы переводим описанный выше процесс непосредственно в код:

let array = [5, 4, 3, 2, 1]
for (let i = 0; i < array.length - 1; i++) {
  if (array[i] > array[i+1]) {
    swap(array, i, i+1)
  }
}
console.log(array) // [4, 3, 2, 1, 5]

Функция swap инкапсулирует способ обмена двумя элементами:

function swap(array, i, j) {
  [array[i], array[j]] = [array[j], array[i]]
}

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

Остальное и так далее. На этом этапе мы также можем легко написать n обход:

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

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

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

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

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

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

Категории