предисловие
Сортировка слиянием и быстрая сортировка — это два алгоритма сортировки, которые имеют практическое применение, имеют некоторые общие характеристики и схожи в общем мышлении. В этой статье мы начнем с некоторых более простых алгоритмов сортировки, перейдем к реализации сортировки слиянием и быстрой сортировки, а также рассмотрим их простое сравнительное мышление и краткое изложение. Перед этим кратко представим смысл алгоритма сортировки.
Алгоритмы сортировки представляют собой расположение строки данных в соответствии с определенным методом сортировки, и они имеют множество исследований и приложений в информатике.
Представьте себе следующий сценарий:
- Придя в кинотеатр, ищите место, указанное в билете в кино.
Если в приведенной выше ситуации «данные», такие как контакты, файлы и места в театре, не организованы в требуемом порядке, как найти нужные вам конкретные «данные»? Будет очень хлопотно! Следовательно, данные, которые нужно искать, обычно должны быть сначала отсортированы!
Разминка первая: сортировка выбором
Все примеры в этой статье - числовая сортировка.Для этой задачи самый простой и интуитивно понятный метод: сначала найти наименьшее, затем найти второе наименьшее, затем найти третье наименьшее... В этом заключается идея сортировки выбором .
function selectionSort(array) {
const len = array.length;
for (let i = 0; i < len - 1; i++) {
let min = i;
for (let j = i + 1; j < len; j++) {
if (array[min] > array[j]) {
min = j;
}
}
[ array[min], array[i] ] = [ array[i], array[min] ];
}
return array;
}
Реализовать разбор:
- перебирать массив
- Найдите наименьший элемент в текущем объеме с помощью индекса записи Minindex, первый раз, когда весь массив проходит диапазон
- Поменять местами значение элемента с нижним индексом minIndex с элементом с текущим минимальным нижним индексом Элемент с наименьшим нижним индексом в первом обходе — это [0]
- При втором обходе диапазон начинается с нижнего индекса второго элемента данных, поэтому текущий минимальный элемент нижнего индекса равен [1]
function createUnsortedArray(size) {
const array = [];
for (let i = size; i > 0; i--) {
const num = (i / 10 > 1) ? i : 10;
array.push( Math.round(Math.random(i) * num + Math.round(Math.random(i)) * Math.random(i) * num * 10) );
}
return array;
}
function show(fn, size = 11) {
console.log('------------------------------------------');
console.log(`Method: ${fn.name}`);
console.log('------------------------------------------');
const array = createUnsortedArray(size);
console.log('before:');
console.log(array.toString());
console.log('after:');
console.log(fn(array).toString());
}
show(selectionSort);
// ------------------------------------------
// Method: selectionSort
// ------------------------------------------
// before:
// 9,22,3,27,74,54,8,41,80,74,3
// after:
// 3,3,8,9,22,27,41,54,74,74,80
Разминка 2: сортировка пузырьком
И сортировка выбором Пузырьковая сортировка в чем-то похожа, за исключением того, что максимальная всплывающая пузырьковая сортировка — это первая до последней позиции. Еще в 1956 г. была исследована пузырьковая сортировка.
function bubbleSort(array) {
for (let first = 0, len = array.length; first < len; first++) {
let isSorted = true;
for (let second = 0; second < len - first - 1; second++) {
if (array[second] > array[second + 1]) {
let temp = array[second];
array[second] = array[second + 1]
array[second + 1] = temp;
isSorted = false;
}
}
if (isSorted) {
break;
}
}
return array;
}
show(bubbleSort);
// ------------------------------------------
// Method: bubbleSort
// ------------------------------------------
// before:
// 35,8,2,2,8,1,3,4,2,10,4
// after:
// 1,2,2,2,3,4,4,8,8,10,35
Реализовать разбор:
- перебирать массив
- Выполните обход второго уровня, сравните два соседних элемента спереди назад, и значение предыдущего элемента больше, чем значение следующего элемента, затем обменяйтесь (пузырь). Первое всплытие, самое большое значение элемента всплывает до конца
- Поскольку каждый проход в виде всплывающего окна определяет текущее максимальное значение и помещает его в конец текущего диапазона, каждый проход в виде всплывающего окна может проверять на одну позицию меньше.
- Переменная может использоваться для записи того, произвел ли текущий барботирование обмен элементами, если нет, это означает, что текущая сортировка завершена и цикл завершен.
Разминка 3. Сортировка вставками
Вставка своего рода мышление очень распространена в повседневной жизни, например, как Лунжи запланировал сидения? Комплексные показатели происхождения, способности, статус к ситуации и другим людям, он занял второе место в Ляншанпо, второй только к песне Jiang. Это то, что мышление вставлено. Небольшое количество данных или тому подобное «сидение на ряд к JUNYI» в этом случае данные отсортированы в увеличении вставки данных, отличные от сортировки, упомянутых здесь.
function insertionSort(array) {
for (let i = 0, len = array.length; i < len; i++) {
let j = i;
const temp = array[i]
while (j > 0 && array[j - 1] > temp) {
array[j] = array[j - 1];
j--;
}
array[j] = temp;
}
return array;
}
show(insertionSort);
// ------------------------------------------
// Method: insertionSort
// ------------------------------------------
// before:
// 3,8,68,30,28,56,35,30,2,4,13
// after:
// 2,3,4,8,13,28,30,30,35,56,68
Реализовать разбор:
- Начиная с первого элемента, элемент можно считать отсортированным
- Возьмите следующий элемент и просканируйте его от начала до конца в отсортированной последовательности элементов.
- Если элемент (отсортированный) больше нового элемента, переместите элемент в следующую позицию
- Повторяйте шаг 3, пока не найдете позицию, в которой отсортированный элемент меньше или равен новому элементу.
- После вставки нового элемента в эту позицию
- Повторите шаги 2–5.
Сортировка слиянием (рекурсивная реализация)
Временная сложность сортировки выбором и пузырьковой сортировки составляет O(n^2), что редко используется в практических проектах, временная сложность сортировки слиянием составляет O(nlog(n)), что является дополнительной сортировкой в практических проектах. .
function mergeSort(unsorted) {
function merge(leftArr, rightArr) {
const lenL = leftArr.length;
const lenR = rightArr.length;
let indexL = 0;
let indexR = 0;
const result = [];
while (indexL < lenL && indexR < lenR) {
if (leftArr[indexL] < rightArr[indexR]) {
result.push(leftArr[indexL++]);
} else {
result.push(rightArr[indexR++]);
}
}
while (indexL < lenL) {
result.push(leftArr[indexL++]);
}
while (indexR < lenR) {
result.push(rightArr[indexR++]);
}
return result;
}
function split(array) {
const len = array.length;
if (len <= 1) {
return array;
}
const mid = Math.floor(len / 2);
const leftArr = array.slice(0, mid);
const rightArr = array.slice(mid, len);
return merge( split(leftArr), split(rightArr) );
}
return split(unsorted);
}
show(mergeSort);
// ------------------------------------------
// Method: mergeSort
// ------------------------------------------
// before:
// 86,55,0,31,104,6,5,49,89,19,6
// after:
// 0,5,6,6,19,31,49,55,86,89,104
Анализ реализации:
- Средний вырезать из массива в две массивы
- После разделения до минимума запустите операцию слияния, то есть объединить две отсортированные массивы
function quickSort(unsorted) {
function partition(array, left, right) {
const pivot = array[ Math.floor((left + right) / 2) ];
while (left <= right) {
while (array[left] < pivot) {
left++;
}
while (array[right] > pivot) {
right--;
}
if (left <= right) {
[array[left], array[right]] = [array[right], array[left]];
left++;
right--;
}
}
return left;
}
function quick(array, left, right) {
if (array.length <= 1) {
return array;
}
const index = partition(array, left, right);
if (left < index - 1) {
quick(array, left, index - 1);
}
if (right > index) {
quick(array, index, right);
}
return array;
}
return quick(unsorted, 0, unsorted.length - 1);
}
show(quickSort);
// ------------------------------------------
// Method: quickSort
// ------------------------------------------
// before:
// 41,9,22,4,1,32,10,28,4,94,3
// after:
// 1,3,4,4,9,10,22,28,32,41,94
Анализ реализации:
- разделить текущий массив
- При разбиении сначала выберите опорное значение, а затем создайте два указателя, левый указывает на первый элемент массива, а правый — на последний элемент массива. Перемещайте левый указатель, пока он не найдет элемент, превышающий опорное значение, перемещайте правый указатель, пока не найдет элемент, меньший опорного значения, затем поменяйте их местами и повторяйте этот процесс, пока левый указатель не превысит правый указатель. Таким образом, при разделении и обмене все элементы, меньшие опорного значения, располагаются перед опорным значением, а элементы, превышающие опорное значение, располагаются после опорного значения.Это операция разделения.
- Повторяйте операции разделения и замены для двух областей после последнего раздела, пока раздел не станет наименьшим.
Сравните сортировку слиянием и быструю сортировку
- Используется идея «разделяй и властвуй». По сравнению с сортировкой выбором и пузырьковой сортировкой, сортировка слиянием и быстрая сортировка используют сегментацию вместо прямого обхода, что эффективно снижает количество обменов.
- Сортировка слиянием сначала разделяется, затем сортируется, процесс можно описать как: разделить, разделить, разделить...сортировать, сортировать, сортировать...
- Быстрая сортировка - раздел, сортирован чередуется, процесс можно описать как: раздел, сортировка, раздел, сортировка ...
- «Сортировка», упомянутая в двух предыдущих абзацах, не является одной и той же операцией сортировки слиянием и быстрой сортировки.Операция сортировки слиянием заключается в объединении двух массивов в один (операция слияния), а операция быстрой сортировки — обмен.