Алгоритм сортировки
Формула в статье может быть не разобрана, можете проверить на сайте моего технического блога
- Для связи или большего количества контента, пожалуйста, обратите внимание на мой общедоступный номер:nezha_blog
- Мой технический блог:nezha.github.io
Пузырьковая сортировка
принцип
Эти два метода сравнивают коды сортировки соседних записей, и если происходит обратный порядок, они меняются местами; есть два способа всплытия: один — сначала всплывать маленькие элементы на передний план, а другой — всплывать большие элементы наверх. спина .
представление
Временная сложность $O(N^2)$, пространственная сложность $O(1)$. сортировка
稳定да, сортироватьКоличество сравнений не зависит от исходной последовательности, но количество перестановок связано с исходной последовательностью.
оптимизация
Если исходная последовательность отсортирована, для пузырьковой сортировки по-прежнему выполняется $O(N^2)$ сравнений, но без свопов. По этому можно оптимизировать, а можно поставить флаг Когда в последовательности нет обмена, последовательность отсортирована, но временная сложность сортировки после оптимизации не изменилась на порядок.
###Код
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
boolean flag = true;
for (int j = arr.length - 1; j > i; j--) {
if (arr[j] < arr[j - 1]) {
int tmp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = tmp;
flag = false;
}
}
if (flag) return;
}
}
Сортировка вставками
принцип
Выберите данные для сортировки по очереди и вставьте их в ранее отсортированную последовательность.
представление
Временная сложность $O(N^2)$, пространственная сложность $O(1)$. Алгоритм стабилен, а количество сравнений и обменов связано с исходной последовательностью.
оптимизация
Прямая сортировка вставками ищет вперед по порядку каждый раз, когда вставляется вперед.Его можно оптимизировать здесь.При поиске подходящей позиции вставки вперед используется бинарный поиск, то есть половинная вставка.
По сравнению с прямой сортировкой вставками полусвернутая сортировка вставками: средняя производительность выше, временная сложность снижена до $O(NlogN)$, сортировка стабильна, но сортировкаКоличество сравнений не зависит от исходной последовательности, всегда требует сравнения сортировки $foo(log(i))+1$.
код
public static void insertSort(int[] arr) {
for (int i = 1; i < arr.length; i++){
out:
for (int j=i;j>0;j--){
if (arr[j] < arr[j-1]){
int tmp = arr[j];
arr[j] = arr[j-1];
arr[j-1] = tmp;
}else break out;
}
}
}
public static void insertBinarySort(int[] arr){
for (int i = 1; i < arr.length; i++){
if (arr[i] < arr[i-1]){
int temp = arr[i];
int low = 0, high = i - 1, mid;
while (low <= high){
mid = (low + high) / 2;
if (temp < arr[mid]){
high = mid - 1;
}else {
low = mid + 1;
}
}
for (int j = i; j >low; j--){
arr[j] = arr[j - 1];
}
arr[low] = temp;
}
}
}
Сортировка холмов
принцип
Улучшенная версия сортировки вставками — это усовершенствованный метод, основанный на следующих двух свойствах сортировки вставками:
- Сортировка вставками очень эффективна при работе с почти отсортированными данными и может достигать эффективности линейной сортировки.
- Однако сортировка вставками может перемещать данные только на один бит каждый раз, когда они вставляются вперед, что относительно неэффективно.
Итак, идея сортировки Хилла такова:
- Сначала возьмите подходящую
gap<nВ качестве интервала разделите все элементы на подпоследовательности пробелов, поместите все элементы с расстоянием пробела в одну и ту же подпоследовательность, а затем выполните прямую сортировку вставкой для каждой подпоследовательности; - Уменьшите разрыв интервала, например,
gap=ceil(gap/2), повторите вышеуказанное деление подпоследовательности и сортировку - До последнего промежутка = 1 все элементы размещаются в одной и той же последовательности для сортировки вставками.
###представление
В начале значение зазора велико, количество элементов в подпоследовательности мало, а скорость сортировки высокая, что преодолевает недостатки сортировки прямым вставками; во-вторых, после значения зазора постепенно уменьшается, хотя количество элементов в последующем постепенно увеличивается, большинство элементов в основном упорядочены, поэтому он наследует преимущества прямой сортировки вставками и может сортировать с почти линейной скоростью.
###Код
public static void shellSort(int[] arr) {
int gap = Math.round(arr.length / 2);
while (gap > 0) {
for (int i = 0;i<gap;i++){
for (int j = i + gap;j<arr.length;j+=gap){
if (arr[j] > arr[j-gap]){
int temp = arr[j];
int k = j - gap;
while (k >= 0 && arr[k] > temp)
{
arr[k + gap] = arr[k];
k -= gap;
}
arr[k + gap] = temp;
}
}
}
}
}
public static void shellSort2(int[] arr){
for (int gap = arr.length / 2; gap > 0; gap /= 2){
for (int i = 0; i < arr.length; i = i + gap){
int temp = arr[i];
int j;
for (j = i; j >= gap && temp < arr[j-gap]; j -= gap){
arr[j] = arr[j - gap];
}
arr[j] = temp;
}
}
}
сортировка выбором
принцип
Каждый раз, когда минимальное значение находится в несортированной последовательности, оно записывается и, наконец, помещается в конец отсортированной последовательности.
представление
Временная сложность $O(N^2)$, пространственная сложность $O(1)$, сортировка不稳定(вызванный заменой минимального значения на отсортированный конец), конечная позиция элемента определяется каждый раз, независимо от исходной последовательности для количества сравнений.
код
public static void selectSort(int[] arr){
int len = arr.length;
//每次从后边选择一个最小值
for (int i = 0; i < len-1; i++){ //只需选择n-1次
int min = i;
for (int j = i+1; j < len; j++){
if (arr[min]>arr[j]){
min = j;
}
}
if (min != i){
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
быстрая сортировка
принцип
Идея разделяй и властвуй:
- Разделить: найти опорный элемент, разделить массив A[p..r] на A[p..pivotpos-1] и A[pivotpos+1...q], элементы слева меньше опорного , а элементы справа больше эталона;
- Conquer: рекурсивно сортировать два разделенных массива;
- Объединить: благодаря функции эталона два подмассива упорядочиваются на месте без необходимости операции слияния.
представление
Средняя временная сложность быстрой сортировки составляет $O(NlogN)$, а пространственная сложность — $O(logN)$, но в худшем случае временная сложность составляет $O(N^2)$$, пространственная сложность — $ O(N)$, и сортировка нестабильна, но конечное положение элемента в последовательности может быть определено каждый раз, а сложность связана с исходной последовательностью.
код
public static void swap(int i, int j, int[] arr) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void sortQuick(int[] quickArray) {
int[] arr = quickArray;
quickSort(0, arr.length - 1, arr);
}
public static void quickSort(int start, int end, int[] arr) {
if (start < end) {
int pivot = arr[start];
int left = start;
int right = end;
while (left != right) {
while (arr[right] >= pivot && left < right) right--;
while (arr[left] <= pivot && left < right) left++;
swap(left, right, arr);
}
arr[start] = arr[left];
arr[left] = pivot;
quickSort(start, left - 1, arr);
quickSort(left + 1, end, arr);
}
}
Сортировка слиянием
принцип
Сначала рассмотрите слияние двух упорядоченных массивов.Основная идея состоит в том, чтобы сравнить первое число двух массивов, в зависимости от того, что меньше, берется первым, а затем соответствующий указатель перемещается на один бит назад. Затем сравните, пока один массив не станет пустым, и, наконец, скопируйте остальную часть другого массива.
Затем рассмотрим рекурсивную декомпозицию. Основная идея состоит в том, чтобы разложить массив на левый и правый. Если внутренние данные этих двух массивов упорядочены, то описанный выше метод объединения массивов можно использовать для объединения и сортировки этих двух массивов. Как я могу сделать эти два массива внутренне упорядоченными? Ее можно разделить еще на две, пока разложенная группа не будет содержать только один элемент, в это время группа считается упорядоченной. Затем объедините и отсортируйте соседние две группы.
представление
Временная сложность всегда $O(NlogN)$, а пространственная сложность всегда 4O(N)$, алгоритм не имеет ничего общего с исходной последовательностью, сортировка стабильна.
###Код
public static void mergeSort(int[] arr){
mergeSortDiv(arr,0,arr.length-1);
}
public static int[] mergeSortDiv(int[] arr,int low,int high){
int mid = (low + high) / 2;
if (low < high) {
// 左边
mergeSortDiv(arr, low, mid);
// 右边
mergeSortDiv(arr, mid + 1, high);
// 左右归并
merge(arr, low, mid, high);
}
return arr;
}
public static void merge(int[] nums, int low, int mid, int high){
int[] temp = new int[high - low + 1];
int i = low;// 左指针
int j = mid + 1;// 右指针
int k = 0;
// 把较小的数先移到新数组中
while (i <= mid && j <= high) {
if (nums[i] < nums[j]) {
temp[k++] = nums[i++];
} else {
temp[k++] = nums[j++];
}
}
// 把左边剩余的数移入数组
while (i <= mid) {
temp[k++] = nums[i++];
}
// 把右边边剩余的数移入数组
while (j <= high) {
temp[k++] = nums[j++];
}
// 把新数组中的数覆盖nums数组
for (int k2 = 0; k2 < temp.length; k2++) {
nums[k2 + low] = temp[k2];
}
}
сортировка кучей
принцип
Сортировка кучей часто используется в задачах на топ-K. Сортировка кучей реализована с использованием двоичной структуры данных кучи, хотя по сути это одномерный массив. Двоичная куча — это приблизительно полное бинарное дерево.
Двоичная куча обладает следующими свойствами:
- Значение ключа родительского узла всегда больше или равно (меньше или равно) значению ключа любого дочернего узла.
- Левое и правое поддеревья каждого узла представляют собой двоичную кучу (как максимальную, так и минимальную).
шаг:
-
Построить максимальную кучу (Build_Max_Heap): если диапазон нижнего индекса массива равен 0~n, учитывая, что один элемент является большой корневой кучей, все элементы, начинающиеся с нижнего индекса n/2, являются большими корневыми кучами. Таким образом, пока вы начинаете с n/2-1 и по очереди строите большую корневую кучу, можно гарантировать, что при построении узла его левое и правое поддеревья уже являются большими корневыми кучами.
-
Сортировка кучи (HeapSort): поскольку куча моделируется с помощью массива. После получения большой корневой кучи массив не упорядочен внутри. Следовательно, массив с кучей необходимо отсортировать. Идея состоит в том, чтобы удалить корневой узел и выполнить рекурсивную операцию настройки максимальной кучи. Поменяйте местами кучу[0] с кучей[n-1] в первый раз, а затем выполните максимальную настройку кучи для кучи[0...n-2]. Поменяйте местами кучу[0] с кучей[n-2] во второй раз и выполните настройку максимальной кучи для кучи[0...n-3]. Эта операция повторяется до тех пор, пока куча [0] и куча [1] не будут заменены местами. Поскольку наибольшее число каждый раз объединяется со следующим упорядоченным интервалом, весь массив упорядочивается после операции.
-
Регулировка максимальной кучи (Max_Heapify): этот метод предоставляется для двух вышеуказанных вызовов процедур. Цель состоит в том, чтобы настроить конечный дочерний узел кучи так, чтобы дочерний узел всегда был меньше родительского узла.
представление
Временная сложность равна $O(NlogN)$, а пространственная сложность — $O(1)$, поскольку используемое пространство сортировки по-прежнему является исходной последовательностью, и новое пространство не открывается.Алгоритм нестабилен, не зависит от исходной последовательности.
сцены, которые будут использоваться
Если вы хотите узнать максимальное или минимальное значение, например, приоритетные очереди, планирование заданий и другие сценарии.
код
Сортировка слиянием (JAVA) алгоритма сортировки — форма массива
сортировка по подсчету
принцип
Сначала подсчитайте количество вхождений каждого элемента, затем подсчитайте абсолютную позицию (конечную позицию) элемента в конечной отсортированной последовательности, а затем последовательно переместите элементы в исходной последовательности в отсортированный массив в соответствии с конечной абсолютной позицией элемента. элемент средний.
представление
Временная сложность O(N+K), пространственная сложность O(N+K).Алгоритм устойчив, не зависит от исходной последовательности и может быть отсортирован без сравнения.
сортировка ведром
принцип
- В соответствии с диапазоном размеров элементов, подлежащих сортировке, разделите M ведер равномерно и независимо.
- Распределите N входных элементов по корзинам
- Затем отсортируйте элементы в каждом сегменте
- В это время элементы в каждом сегменте перечислены по порядку, то есть они отсортированы.
представление
Временная сложность $O(N+C)$, $O(C)=O(M(N/M)log(N/M))=O(NlogN-NlogM)$, а пространственная сложность $O ( N+M)$ алгоритм устойчив и не зависит от исходной последовательности.
сцены, которые будут использоваться
Идея алгоритма аналогична методу открытого хеширования в хешировании, при конфликте помещается в тот же бакет, может использоваться при относительно равномерном распределении объема данных или при большем количестве интервалов. сфокусированный.
сортировка по основанию
принцип
Когда есть d ключевых слов, они могут быть отсортированы по ключевым словам соответственно. Есть два способа:
- MSD: сначала сортируйте по старшему порядку, по каждому ключевому слову можно использовать сортировку по количеству
- LSD: сначала сортируйте по младшему порядку, по каждому ключевому слову можно использовать сортировку ведра.
представление
Временная сложность — O(d*(N+K)) и пространственная сложность — O(N+K).
Суммировать
использованная литература
[1]Резюме и реализация классических алгоритмов сортировки-Обзор алгоритмов сортировки на основе Python, очень хорошо написанный