Элегантный алгоритм сортировки JavaScript (ES6)

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

Интервьюер: Вы понимаете алгоритм сортировки мальчика?

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

по-своему.

предисловие

Часто используется в этой статьеswapФункции, перечисленные здесь заранее, ниже опущены.

function swap(arr, indexA, indexB) {
  [arr[indexA], arr[indexB]] = [arr[indexB], arr[indexA]];
}

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

краткое объяснение

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

1 такой цикл может получить максимальное значение,n - 1Этот цикл может быть отсортирован.

Атрибуты

  • стабильность
  • временная сложностьO(n²)
  • обменO(n²)
  • Сортировка массива, который должен быть отсортированO(n)(Но в этом случае это не так хорошо, как вставка блока сортировки, пожалуйста, продолжайте читать ниже)

основная концепция

  • использоватьпоменять местами, выделить наибольшее число до конца
  • использоватьтайникpostionоптимизировать
  • использоватьДвусторонний обходоптимизировать

Первое издание: базовая реализация

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

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(bubbleSort(arr));

Версия 2: Кэширование поз.

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

function bubbleSort2(arr) {
  let i = arr.length - 1;

  while (i > 0) {
    let pos = 0;

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

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(bubbleSort2(arr));

Третье издание: двусторонний обход

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

function bubbleSort3(arr) {
  let start = 0;
  let end = arr.length - 1;

  while (start < end) {
    for (let i = start; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        swap(arr, i, i + 1);
      }
    }
    end -= 1;
    for (let i = end; i > start; i--) {
      if (arr[i - 1] > arr[i]) {
        swap(arr, i - 1, i);
      }
    }
    start += 1;
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(bubbleSort3(arr));

Четвертое издание: объединение 2 и 3

Первые два метода оптимизации (cachepos, двунаправленный обход) комбинация:

function bubbleSort4(arr) {
  let start = 0;
  let end = arr.length - 1;

  while (start < end) {
    let endPos = 0;
    let startPos = 0;

    for (let i = start; i < end; i++) {
      if (arr[i] > arr[i + 1]) {
        endPos = i;
        swap(arr, i, i + 1);
      }
    }
    end = endPos;
    for (let i = end; i > start; i--) {
      if (arr[i - 1] > arr[i]) {
        startPos = i;
        swap(arr, i - 1, i);
      }
    }
    start = startPos;
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(bubbleSort4(arr));

Муравей Финансовое Интервью

Вопрос интервью от Ant Financial:

Для пузырьковой сортировки можете ли вы передать второй параметр (параметр является функцией), чтобы управлять порядком возрастания и убывания? (подумай об этомarray.sort())

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

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(bubbleSort(arr, (a, b) => a - b));
console.log(bubbleSort(arr, (a, b) => b - a));

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

краткое объяснение

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

повторить этот циклn - 1результаты получены.

Атрибуты

  • нестабильный
  • Θ(n²)Независимо от ввода, этоΘ(n²)
  • Θ(n) 交换: Обратите внимание, что здесь толькоnраз обмен, единственное преимущество сортировки выбором*

Относительно Θ(n) свопов:

Selection sort has the property of minimizing the number of swaps. In applications where the cost of swapping items is high, selection sort very well may be the algorithm of choice.

видимыйДаже самая медленная сортировка выбора, как нам кажется, имеет свое место..

основная концепция

  • «Предсказуемая» временная сложность, все приходитO(n²), но не стабильно,Единственным преимуществом является то, что он уменьшаетswapчастота.

Первое издание: базовая реализация

function selectionSort(arr) {
  for (let i = 0, len = arr.length; i < len - 1; i++) {
    let minIndex = i;

    for (let j = i + 1; j < len; j++) {
      if (arr[j] < arr[minIndex]) {
        minIndex = j;
      }
    }
    if (i !== minIndex) {
      swap(arr, i, minIndex);
    }
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(selectionSort(arr));

Второе издание: Найдите максимум

Если вы хотите каждый раз внутри циклаНайдите максимальное значение и поменяйте местами его в конец массива(В сравненииminIndexнемного громоздко), вот код, который это реализует:

function selectionSort2(arr) {
  for (let i = arr.length - 1; i > 0; i--) {
    let maxIndex = i;

    for (let j = i - 1; j >= 0; j--) {
      if (arr[j] > arr[maxIndex]) {
        maxIndex = j;
      }
    }
    if (i !== maxIndex) {
      swap(arr, i, maxIndex);
    }
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(selectionSort2(arr));

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

краткое объяснение

дефолтa[0]для элементов в отсортированном массиве,отarr[1]Начните постепенно вставлять элементы в отсортированный массив,Сравните один за другим сзади наперед, если вставляемый элемент меньше отсортированного элемента, отсортированный элемент перемещается на одну позицию назад, пока вставляемый элемент не найдет подходящую позицию и не вставит ее в отсортированный массив.

проходить черезn - 1Сортировка завершается после вставки такого цикла.

Атрибуты

  • стабильность
  • Подходящая сцена:Временная сложность массива, который должен быть отсортирован, равнаO(n)
  • очень низкие накладные расходы
  • временная сложностьO(n²)

Благодаря своим преимуществам (адаптивность, низкие накладные расходы, стабильность, почтиO（n）время), сортировка вставками часто используется в качестве рекурсивного базового случая (когда размер задачи невелик) для более дорогих алгоритмов сортировки по принципу «разделяй и властвуй», таких какСортировка холмовилибыстрая сортировка.

основная концепция

  • Высокая производительность (особенно массивы, близкие к сортировке), низкие накладные расходы и стабильность
  • использоватьбинарный поископтимизировать

Первое издание: базовая реализация

function insertionSort(arr) {
  for (let i = 1, len = arr.length; i < len; i++) {
    const temp = arr[i];
    let preIndex = i - 1;

    while (arr[preIndex] > temp) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex -= 1;
    }
    arr[preIndex + 1] = temp;
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(insertionSort(arr));

алгоритм бинарного поиска

Поскольку метод оптимизации для сортировки вставками — это оптимизация бинарного поиска, вот реализация алгоритма бинарного поиска.

Основные концепции:сложить пополам.

function binarySearch(arr, value) {
  let min = 0;
  let max = arr.length - 1;
  
  while (min <= max) {
    const mid = Math.floor((min + max) / 2);

    if (arr[mid] === value) {
      return mid;
    } else if (arr[mid] > value) {
      max = mid - 1;
    } else {
      min = mid + 1;
    }
  }

  return 'Not Found';
}

// test
const arr = [1, 2, 3];
console.log(binarySearch(arr, 2));  // 1
console.log(binarySearch(arr, 4));  // Not Found

Второе издание: использование бинарного поиска

Сначала сделайте небольшую модификацию алгоритма бинарного поиска, чтобы он соответствовал нашей сортировке вставками:

function binarySearch(arr, maxIndex, value) {
  let min = 0;
  let max = maxIndex;
  
  while (min <= max) {
    const mid = Math.floor((min + max) / 2);

    if (arr[mid] <= value) {
      min = mid + 1;
    } else {
      max = mid - 1;
    }
  }

  return min;
}

затем при поиске позиции кареткиИспользовать бинарный поискспособ оптимизации производительности:

function insertionSort2(arr) {
  for (let i = 1, len = arr.length; i < len; i++) {
    const temp = arr[i];
    const insertIndex = binarySearch(arr, i - 1, arr[i]);

    for (let preIndex = i - 1; preIndex >= insertIndex; preIndex--) {
      arr[preIndex + 1] = arr[preIndex];
    }
    arr[insertIndex] = temp;
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(insertionSort2(arr));

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

краткое объяснение

Сортировка по холмуУлучшенная версия сортировки вставками,ЭтоУстранен дефект, заключающийся в том, что сортировка вставками может перемещать только одну соседнюю позицию.(сортировку по холмам можно перемещать одновременноgapрасстояние),Воспользуйтесь преимуществами очень высокой скорости сортировки вставками при сортировке почти уже отсортированных массивов..

Использовать динамически определяемыеgapпостепенно сортировать,Сначала отсортируйте элементы, которые находятся дальше, а затем постепенно прогрессируйте.,иНа самом деле вероятность того, что конечная позиция элемента в сортировке далека от начальной позиции, очень велика., поэтому сортировка по Хиллу значительно повышает производительность (Особенно когда задний ход очень быстрый, представьте скорость пузырьковой сортировки и сортировки вставками в это время).

И сортировка Хилла не только более эффективна (выше, чем всплытие и вставка), ее код относительно короткий, с низкими накладными расходами (Преимущества наследуемой сортировки вставками),Сортировка по холму хороша при выполнении этих характеристик (хорошие требования к эффективности, короткий код, низкие накладные расходы и небольшой объем данных).O(n·log(n))Альтернативы алгоритмам.

Подводя итог: оптимизация производительности сортировки Хилла исходит изИнкрементальный ввод очередииgapнастройки.

Атрибуты

  • нестабильный
  • Массив, который должен быть отсортирован, имеетO(n·log(n))временная сложность (и это очень быстро для обращения массивов)
  • O(n^3/2)время, как показано (подробнее см.wikipedia Shellsort)

Насчет нестабильности:

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

Есть небольшая сложность с худшим временем:

Временная сложность сортировки оболочки в худшем случае зависит от последовательности приращений.Для приращений 1 4 13 40 121…, которые используются здесь, временная сложность равна O(n3/2).Для других приращений временная сложность равна как известно, O(n4/3) и даже O(n·log2(n)).

основная концепция

Сортировка по холмуСортировка вставкамиУсовершенствованный метод предлагается для следующих двух свойств:

  1. Сортировка вставками эффективна при работе с почти отсортированными данными, т.O(n)эффективность;
  2. Но сортировка вставками, как правило, неэффективна, потому что сортировка вставками может перемещать данные только по одному биту за раз.;

вgapВыбор (постепенный) является важной частью сортировки Хилла.. пока наконецgapза 1 любойgapПоследовательности все работают. Алгоритм начинается с определенногоgapСортировать. затем продолжитgapСортировать,до того какgap = 1, алгоритм меняется на сортировку вставками.

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

Первое издание: базовая реализация

Оригинальное предложение Дональда Шелла (gap = n / 2) код версии (легко понять):

function shellSort(arr) {
  const len = arr.length;
  let gap = Math.floor(len / 2);

  while (gap > 0) {
    // 注意下面这段 for 循环和插入排序极为相似
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let preIndex = i - gap;

      while (arr[preIndex] > temp) {
        arr[preIndex + gap] = arr[preIndex];
        preIndex -= gap;
      }
      arr[preIndex + gap] = temp;
    }
    gap = Math.floor(gap / 2);
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(shellSort(arr));

Второе издание: последовательность приращений Кнута

Общий, простой в создании, оптимизированныйgapМетод последовательности для (из алгоритмов (4-е издание), некоторые более быстрые методы, но последовательности генерировать нелегко из-за более эзотерической математики):

function shellSort(arr) {
  const len = arr.length;
  let gap = 1;

  while (gap < len / 3) {
    gap = gap * 3 + 1;
  }
  while (gap > 0) {
    for (let i = gap; i < len; i++) {
      const temp = arr[i];
      let preIndex = i - gap;

      while (arr[preIndex] > temp) {
        arr[preIndex + gap] = arr[preIndex];
        preIndex -= gap;
      }
      arr[preIndex + gap] = temp;
    }
    gap = Math.floor(gap / 2);
  }

  return arr;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(shellSort(arr));

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

краткое объяснение

Сортировка слиянием с использованиемразделяй и властвуймысль, ссложить пополампуть крекурсия/итерацияСортируйте элементы, используйте пространство для обмена временем и достигайте временной сложностиO(n·log(n))при сохранении стабильности.

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

Атрибуты

  • стабильность (существуетO(n·log(n))Среди алгоритмов сортировки с временной сложностью сортировка слиянием является единственным стабильным.)
  • временная сложностьO(n·log(n))
  • Θ(n) дополнительное пространство для массивовУведомление:Сортировка слиянием требует дополнительного места, что является ее недостатком.
  • O (log (n)) дополнительное пространство для связанных списков,такСортировка слиянием отлично подходит для сортировки списков
  • Does not require random access to dataБлагодаря этой функции сортировка слиянием очень удобна для сортировки списков.

основная концепция

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

Первое издание: базовая реализация

Делайте это итеративно (но следите за тем, чтобы вызов функции не был слишком глубоким и не переполнял стек JavaScript):

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

  if (len < 2) { return arr; }

  const mid = Math.floor(len / 2);
  const left = arr.slice(0, mid);
  const right = arr.slice(mid);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];

  while (left.length > 0 && right.length > 0) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }

  return result.concat(left, right);
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(mergeSort(arr));

Второе издание: оптимизация пространства

использоватьarray.spliceзаменятьarray.slice, уменьшая занимаемую площадь вдвое.

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

  if (len < 2) { return arr; }

  const mid = Math.floor(len / 2);
  const left = arr.splice(0, mid);
  const right = arr;

  return merge(mergeSort(left), mergeSort(right));
}

function merge(left, right) {
  const result = [];

  while (left.length > 0 && right.length > 0) {
    result.push(left[0] <= right[0] ? left.shift() : right.shift());
  }

  return result.concat(left, right);
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(mergeSort2(arr));

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

краткое объяснение

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

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

  1. сначала собрать все данные
  2. затем переместитеarr[0]до конца массива (отсортированная область)
  3. пересыпать, И так далее, и так далее.

Воспользовавшись хорошей структурой данных кучи, онхорошая предсказуемостьодновременно (независимо от вводаO(n·log(n))временная сложность),Но и у него есть свои недостатки: то есть неустойчивый,иO(n·log(n))Средняя эффективность определяет, что она не так эффективна, как быстрая сортировка. Хорошо подходит для сортировки в движке базы данных (требуется такая предсказуемая производительность).

Атрибуты

  • нестабильный
  • O(n·log(n)) time

основная концепция

  • Используйте хорошую структуру данных — кучу, чтобы сортировать
  • Дихотомическое мышление
  • Улучшенная версия сортировки выбором, которая наследует «предсказуемость» (любой ввод данныхO(n·log(n)время)

Первое издание: базовая реализация

function heapSort(arr) {
  let size = arr.length;

  // 初始化堆，i 从最后一个父节点开始调整，直到节点均调整完毕 
  for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
    heapify(arr, i, size);
  }
  // 堆排序：先将第一个元素和已拍好元素前一位作交换，再重新调整，直到排序完毕
  for (let i = size - 1; i > 0; i--) {
    swap(arr, 0, i);
    size -= 1;
    heapify(arr, 0, size);
  }

  return arr;
}

function heapify(arr, index, size) {
  let largest = index;
  let left = 2 * index + 1;
  let right = 2 * index + 2;

  if (left < size && arr[left] > arr[largest]) {
    largest = left;
  }
  if (right < size && arr[right] > arr[largest]) {
    largest = right;
  }
  if (largest !== index) {
    swap(arr, index, largest);
    heapify(arr, largest, size);
  }
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(heapSort(arr));

Другой метод, указанный в вики

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

function heapSort(arr) {
  const size = arr.length;

  // 初始化 heap，i 从最后一个父节点开始调整，直到节点均调整完毕 
  for (let i = Math.floor(size / 2) - 1; i >= 0; i--) {
    heapify(i, size);
  }
  // 堆排序：先将第一个元素和已拍好元素前一位作交换，再重新调整，直到排序完毕
  for (let i = size - 1; i > 0; i--) {
    swap(arr, 0, i);
    heapify(0, i);
  }

  return arr;
}

function heapify(start, end) {
  // 建立父节点下标和子节点下标
  const dad = start;
  let son = dad * 2 + 1;

  if (son >= end) { return 0; }

  if (son + 1 < end && arr[son] < arr[son + 1]){
    son += 1;
  }
  if (arr[dad] <= arr[son]) {
    swap(arr, dad, son);
    heapify(son, end);
  }

  return 0;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(heapSort(arr));

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

краткое объяснение

  1. Выберите элемент из последовательности, называемый «стержнем»,
  2. переупорядочить массив,Все элементы, меньшие эталонного значения, помещаются перед эталонным значением, а все элементы, превышающие эталонное значение, размещаются за эталонным значением.(Одно и то же число может идти в обе стороны). После того, как этот раздел заканчивается, эталон находится в середине последовательности. это называетсяРаздел операции.
  3. Рекурсивно отсортируйте подмассивы элементов меньше эталонного значения и подмассивы элементов больше эталонного значения.

Атрибуты

  • нестабильный
  • O(n²) времени, но обычно O(n log(n)) времени (или быстрее)
  • O(log(n)) extra space

When implemented well, it can be about two or three times faster than its main competitors, merge sort and heap sort

основная концепция

  • использовалразделяй и властвуйподумал о

Первое издание: базовая реализация

function quickSort(arr) {
  const pivot = arr[0];
  const left = [];
  const right = [];
  
  if (arr.length < 2) { return arr; }

  for (let i = 1, len = arr.length; i < len; i++) {
    arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
  }

  return quickSort(left).concat([pivot], quickSort(right));
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(quickSort(arr));

Второе издание: функциональное программирование

Функциональное программирование: четко структурировано и не требует пояснений.

function quickSort2(arr) {
  const pivot = arr.shift();
  const left = [];
  const right = [];

  if (arr.length < 2) { return arr; }

  arr.forEach((element) => {
    element < pivot ? left.push(element) : right.push(element);
  });

  return quickSort2(left).concat([pivot], quickSort2(right));
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(quickSort2(arr));

Третье издание: на месте

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

Следовательно, версия на месте:

function quickSort3(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    const pivot = partition(arr, left, right);

    quickSort3(arr, left, pivot - 1);
    quickSort3(arr, pivot + 1, right);
  }
  return arr;
}

function partition (arr, left ,right) {
  let pivot = left; // 以第一个元素为 pivot

  for (let i = left + 1; i <= right; i++) {
    if (arr[i] < arr[left]) { 
      swap(arr, i, pivot);
      pivot += 1;
    }
  }
  swap(arr, left, pivot); //将 pivot 值移至中间
  
  return pivot;
}

// test
const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(quickSort3(arr));

Четвертое издание: о выборе опоры

Изюминкой этой версии является выбор точки поворота, которая больше не является простым выбором.arr[0], вместо:

const pivot = left + Math.ceil((right - left) * 0.5)

Большое спасибо за объяснение великого бога @Chris_dong в области комментариев:

const pivot = left + Math.ceil((right - left) * 0.5)=> (удалить MAth.ceil не так просто понять)left + (right - left) * 0.5 => (right + left) * 0.5.

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

Отсюда следующие версии:

function quickSort4(arr, left = 0, right = arr.length - 1) {
  if (left < right) {
    // const pivot = left + Math.ceil((right - left) * 0.5);
    const pivot = Math.floor((right + left) / 2);
    const newPivot = partition(arr, pivot, left, right);

    quickSort4(arr, left, newPivot - 1);
    quickSort4(arr, newPivot + 1, right);
  }

  return arr;
}

function partition(arr, pivot, left, right) {
  const pivotValue = arr[pivot];
  let newPivot = left;

  swap(arr, pivot, right);
  for (let i = left; i < right; i++) {
    if (arr[i] < pivotValue) {
      swap(arr, i, newPivot);
      newPivot += 1;
    }
  }
  swap(arr, right, newPivot);

  return newPivot;
}

const arr = [91, 60, 96, 7, 35, 65, 10, 65, 9, 30, 20, 31, 77, 81, 24];
console.log(quickSort4(arr));

Резюме и вопросы и ответы

Задайте несколько вопросов, которые можно использовать в качестве самопроверки:

  • Когда данные почти готовы к быстрой сортировке?

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

  • Когда объем данных небольшой, требования к эффективности невысокие, а код простой?

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

  • Объем данных большой и требует стабильной эффективности (не такой быстрой, как быстрая сортировка)O(n²)случай) (как в базе данных)?

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

  • Большой объем данных требует высокой эффективности и стабильности?

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

  • Большой объем данных и требуется лучшая средняя эффективность?

Размер производительности: Быстрая сортировка > Сортировка кучей > Сортировка слиянием

Потому что, хотя сортировка кучей делаетO(n·log(n), в то время как худший случай быстрой сортировкиO(n²), но в большинстве случаев быстрая сортировка более эффективна, чемO(n·log(n)Еще быстрее, поэтому быстрая сортировка действительно оправдывает свое название. (очень быстро)

  • Сортировка выбором абсолютно бесполезна?

Требуется только сортировка выборомO(n)Swap, после чего завершается пузырьковая сортировка.

Вопросы и ответы:

  • Блогер, откуда ты скопировал свой код?

Все блоггеры постарались, проверили информацию и со слезами на глазах тщательно закодировали ее построчно. Все адреса источников перечислены в разделе «Ссылки и благодарность» :)

  • Почему бы не написать это на ES5?

На самом деле эта статья наследуется отЭлегантный алгоритм сортировки JavaScript. Эта версия является общей родственной версией (упрощенное объяснение с использованием ES6, чтобы сделать код более кратким), если вы хотите обратиться к английской цитате, коду ES5 и подробному объяснению процесса, вы можете обратиться кпервое издание.

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

Приложение: стиль кода

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

Еще раз выскажу свое мнение:

  • Разработка программного обеспечения — это не догма
  • Нет высокого или низкого вкуса кода

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

Я приложил эти усилия для этой цели:

  • обращать вниманиеЧеловекочитаемое имя переменной*: например.preIndex, temp, size;
  • Краткая структура функций:
    function () {
      const/let ...;

      function body

      return...;
    };
  • в вычисленияхlen / 2время округлениядля удобочитаемостивыбранныйMath.floor(len / 2),нет выбораlen >> 1иparseInt(len / 2, 10);
  • Уведомлениевыделитьforиwhileсценарии использования, вы можете увидеть ответ на этот вопрос для деталей:
    stackoverflow.com/questions/3…
  • Для простоты и интуитивности, не используетсяArray.isArray(),Object.prototype.toString.call(),typeOf, instanceOfПроверятьarrЯвляется ли это типом массива, по умолчаниюarrявляется типом массива;
  • Используйте тернарный оператор( ? : )уменьшитьifвложенность для улучшения читаемости кода;
  • автоматическое приращение (++) и декрементации (--) оператор с использованием+=и-=заменять (forкроме последнего условия в);
  • использоватьES6Режим параметра по умолчанию в (в быстрой сортировке) упрощает код и выделяет ключевую логику;
  • Eslint+ Стиль глобального кода управления Airbnb;
  • Добавьте свои собственные предпочтения в дополнение к стилю, например, используяfunctionОбъявите функцию по конкретным причинам, см.:Код вкуса от перемешивания.

Это мой вкус, а ваш :)

Цитата и спасибо

  • Википедия об алгоритмах сортировки (на английском и китайском языках), относящаяся к объяснению концепции и реализации кода (измененная):
    En. Wikipedia.org/wiki/сортировать в…
  • Визуализация алгоритмов сортировки (английский),настоятельно рекомендую посмотреть,Очень полезно понимать процесс работы алгоритма сортировки:
    woohoo.topthem.com/developers/…
  • StackOverFlow Алгоритмы сортировки Обратитесь к ответам, связанным с алгоритмом сортировки, чтобы помочь понять:
    woohoo.Quora.com/why-do-major-you…
    Woohoo. Quora.com/why-is-setup…
    Woohoo Quora.com/why-is-heap…
    Есть еще несколько, чтобы перечислить...
  • демонстрация damonare (китайский), см. пузырьковую сортировку 1,2,3;Обратитесь к анимации, чтобы помочь понять; сортировка выбором; реализация сортировки слиянием; и изменение:
    GitHub.com/Damon are/so…
  • обратитесь к
    quick sort in-place edition gist.GitHub.com/Пол Льюис/1…
  • gitbook hustcc (китайский), относящийся к реализации быстрой сортировки и сортировки по холмам, и ее модификации
    sort.Hushitai.Cao Cao/6.быстрая сортировка…
Категории