по материалам https://proglib.io
Краткий гайд пригодится новичкам, расскажет о видах и способах сортировки. Для лучшего усвоения и наглядности процесса каждый вид сопровождается gif-анимацией.
Bubble sort (Сортировка пузырьком)
Сортировка пузырьком или сортировка простыми обменами – один из простейших алгоритмов сортировки. Он применяется для упорядочивания массивов небольших размеров.
Суть алгоритма в том, что совершается несколько проходов по массиву. При каждом проходе попарно сравниваются два соседних элемента. Если они находятся в верном порядке, то ничего не происходит, в противном случае они меняются местами. В результате первого прохода максимальный элемент окажется в конце, то есть всплывет словно пузырек. Затем все повторяется до того момента пока весь массив не будет отсортирован.
Quick sort (Быстрая сортировка)
Быстрая сортировка — в целом это один из самых быстрых алгоритмов сортировки массивов, однако на практике он чаще всего применяется с разного рода модификациями. Является примером принципа «разделяй и властвуй».
Идея алгоритма заключается в том, что выбирается опорный элемент, относительно которого будет происходит сортировка. Равные и бОльшие элементы помещаются справа, меньшие – слева. Затем к полученным подмассивам рекурсивно применяются два первых пункта.
Random quick sort (Рандомная быстрая сортировка)
Рандомная быстрая сортировка – то же самое, что и быстрая сортировка, лишь с тем отличием, что опорный элемент выбирается случайно.
Merge sort (Сортировка слиянием)
Сортировка слиянием – алгоритм, который сортирует такие структуры данных, где доступ к элементам осуществляется последовательно. Эта сортировка происходит следующим образом:
массив разбивается на две примерно равные части, затем каждая из них сортируется. После этого два отсортированных подмассива сливаются в один. Для этого сравниваются два первых элемента в каждом из них и в зависимости от порядка сортировки ставятся в нужной последовательности. Если же один подмассив закончился, то оставшиеся элементы второго записываются после последнего элемента первого.
Selection sort(Сортировка выбором)
Сортировка выбором — здесь, чтобы отсортировать массив, находим элемент с минимальным значением, затем сравниваем его со значением первой неотсортированной позиции. Если этот элемент меньше, то он становится новым минимумом и их позиции меняются.
Insertion sort (Сортировка вставками)
Сортировка вставками- сортировка, в которой элементы просматриваются по одному и ставятся на место в соответствии с уже упорядоченным массивом.
Counting sort (Сортировка подсчетом)
Сортировка подсчетом – один из базовых алгоритмов, служит основой для многих сортировок, но сам используется только для ознакомления с темой. Его суть в том, чтобы подсчитать сколько раз число встречается в массиве, а затем заполнить массив этими числами в соответствии с количеством.
Radix sort (Поразрядная сортировка)
Поразрядная сортировка — сортировка по разрядам. Существует две разновидности: LSD (least significant digit) и MSD (least significant digit). В первом случае происходит сортировка элементов по младшим разрядам (все оканчивающиеся на 0, затем на 1 и так до 9). После этого они группируются по следующему с конца разряду, пока они не закончатся. В MSD сортировка происходит по старшему разряду.