Сортировка пузырьком java объяснение

Java Blog

Сортировка «пузырьком» (Bubble sort) — это самый простой алгоритм сортировки, он сравнивает первые два элемента, если первый больше второго, меняет их местами, продолжает выполнять (сравнивает и меняет местами) следующую пару смежных элементов. Затем он начинается снова с первых двух элементов, сравнивает, переставляет, пока не потребуется перестановка.

Вот пример реализации сортировки «пузырьком» на Java.

public static int[] sort(int[] data) < int dataLength = data.length; int swap; boolean sorted; for (int i = 0; i < dataLength; i++) < sorted = true; for (int a = 1; a < (dataLength - i); a++) < if (data[a - 1] >data[a]) < swap = data[a - 1]; data[a - 1] = data[a]; data[a] = swap; sorted = false; >> // если отсортировано - выходим, пропуская ненужный цикл. if (sorted) break; > return data; >

Опробуем его с тестовыми данными.

package Bubble; public class Main < public static void main (String[] args) < int[] data = ; String sorted = ""; for (int el : sort(data)) < sorted += String.valueOf(el)+" "; >System.out.println(sorted); > public static int[] sort(int[] data) < int dataLength = data.length; int swap; boolean sorted; for (int i = 0; i < dataLength; i++) < sorted = true; for (int a = 1; a < (dataLength - i); a++) < if (data[a - 1] >data[a]) < swap = data[a - 1]; data[a - 1] = data[a]; data[a] = swap; sorted = false; >> // если отсортировано, выходим, пропуская ненужный цикл. if (sorted) break; > return data; > >

• Получить ссылку
• Facebook
• Twitter
• Pinterest
• Электронная почта
• Другие приложения

Комментарии

Отправить комментарий

Популярные сообщения из этого блога

Методы класса Object в Java

Класс Object является корнем иерархии классов. У каждого класса есть Object как суперкласс. Все объекты, включая массивы, реализуют методы этого класса. Методы класса Object Метод getClass() public final Class getClass() Возвращает класс времени исполнения (runtime class) этого Object. Возвращенный объект Class — это объект, который заблокирован статическими синхронизированными методами представленного класса. Фактический тип результата — Class где |X| заменяется статическим типом выражения, для которого вызывается getClass. Например, в этом фрагменте кода не требуется приведение: Number n = 0; Class c = n.getClass(); Метод getClass() возвращает: Объект Class, представляющий класс времени исполнения (runtime class) этого объекта. Метод hashCode public int hashCode() Возвращает значение хэш-кода для объекта. Этот метод поддерживается для использования хэш-таблиц, таких как те, что предоставляются HashMap. Основной контракт метода hashCo

Как получить текущий timestamp в Java

Чтобы получить текущий timestamp в Java : package main; import java.sql.Timestamp; public class Main < public static void main(String[] args)< Timestamp timestamp = new Timestamp(System.currentTimeMillis()); System.out.println(timestamp); >> Вывод: 2019-10-03 10:09:21.61 Вот еще два более подробных примера как получить текущий timestamp в Java: 1. java.sql.Timestamp Есть два метода получить текущий java.sql.Timestamp package main; import java.sql.Timestamp; import java.text.SimpleDateFormat; import java.util.Date; public class Main < private static final SimpleDateFormat dateFormat = new SimpleDateFormat("yyyy.MM.dd.HH.mm.ss"); public static void main(String[] args) < // Метод 1 Timestamp timestamp = new Timestamp(System.currentTimeMillis()); System.out.println(timestamp); // Метод 2 - через Date Date date = new Date(); System.out.println(new Timestamp(date.getTime()

Spring Boot стартеры

Стартеры — это набор удобных дескрипторов зависимостей, которые вы можете включить в свое приложение. Вы получаете универсальный набор для всех необходимых вам Spring и связанных с ними технологий без необходимости искать примеры кода и копировать и вставлять множество дескрипторов зависимостей. Например, если вы хотите начать использовать Spring и JPA для доступа к базе данных, включите в ваш проект зависимость spring-boot-starter-data-jpa. Стартеры содержат множество зависимостей, которые необходимы вам для быстрого запуска и запуска проекта с согласованным, поддерживаемым набором управляемых переходных зависимостей. Что указывается в имени стартера Все официальные стартеры следуют аналогичной схеме именования; spring-boot-starter-*, где * это конкретный тип приложения. Эта структура наименования предназначена, чтобы помочь, когда вам нужно найти стартер. Интеграция Maven во многие IDE позволяет вам искать зависимости по имени. Например, если установлен соответствующий плагин Ecl

Источник

Алгоритмы сортировки на Java с примерами

В одной из предыдущих статей мы разобрались, где применяются алгоритмы сортировки, а теперь поговорим об их реализации на Java. Помните, что разные алгоритмы оптимальны для разных наборов и типов данных. В нашей статье мы рассмотрим наиболее «ходовые».

Алгоритм сортировки пузырьком на Java

Сортировка пузырьком (Bubble Sort) — это один из наиболее известных алгоритмов, суть которого состоит в последовательном сравнении двух соседних элементов. В том случае, если предыдущий элемент больше последующего, они меняются местами.

Так выглядит сортировка пузырьком на Java:

public static void bubbleSort(int[] sortArr) < for (int i = 0; i < sortArr.length - 1; i++) < for(int j = 0; j < sortArr.length - i - 1; j++) < if(sortArr[j + 1] < sortArr[j]) < int swap = sortArr[j]; sortArr[j] = sortArr[j + 1]; sortArr[j + 1] = swap; >> > > public static void main(String args[]) < int[] sortArr = ; bubbleSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Объяснение

Как видим из кода, метод bubbleSort() принимает массив в качестве входных данных для сортировки — sortArr . Далее мы создаём внешний цикл for , который перебирает каждый элемент массива, тогда как внутренний цикл for начинается с первого элемента массива до предпоследнего индекса: sortArr.length — i — 1 . С помощью условия if мы проверяем, больше ли элемент слева элемента справа или нет. Если элемент слева действительно больше, он меняется местами с правым элементом.

Примечание Внешний цикл for будет перебирать все элементы массива, даже если массив уже полностью отсортирован.

Массив, который принимает метод bubbleSort() , может быть любым. В нашем примере мы передаём значения 12, 6, 4, 1, 15, 10 .

Сложность алгоритма: О(n2)

А ниже представлен алгоритм сортировки двумерного массива Java пузырьком:

public static int[][] matrixBubbleSort(int[][] sortMatrix) < int swap; for (int i = 0; i < sortMatrix.length; i++) < for (int j = 0; j < sortMatrix[i].length; j++) < for (int k = 0; k < sortMatrix.length; k++) < for (int l = 0; l < sortMatrix[k].length; l++) < if (sortMatrix[i][j] > > > > return sortMatrix; > public static void main(String args[]) < int[][] sortMatrix = new int[][]< , , >; matrixBubbleSort(sortMatrix); //Вывод отсортированного двумерного массива: for (int i = 0; i < sortMatrix.length; i++) < for (int j = 0; j < sortMatrix[i].length; j++) < System.out.print(sortMatrix[i][j] + " "); >System.out.println(); > >

Алгоритм быстрой сортировки на Java

Быстрая сортировка, также известная как Quick Sort или сортировка Хоара, является одним их самых эффективных алгоритмов. Она включает в себя три этапа:

1. Из массива выбирается опорный элемент, чаще всего посередине массива.
2. Другие элементы массива распределяются таким образом, чтобы меньшие размещались до него, а большие — после.
3. Далее первые шаги рекурсивно применяются к подмассивам, которые разделились опорным элементом на две части — слева и справа от него.

Пример быстрой сортировки на языке Java:

public static void quickSort(int[] sortArr, int low, int high) < //завершить,если массив пуст или уже нечего делить if (sortArr.length == 0 || low >= high) return; //выбираем опорный элемент int middle = low + (high - low) / 2; int border = sortArr[middle]; //разделияем на подмассивы и меняем местами int i = low, j = high; while (i border) j--; if (i > //рекурсия для сортировки левой и правой части if (low < j) quickSort(sortArr, low, j); if (high >i) quickSort(sortArr, i, high); > public static void main(String args[]) < int[] sortArr = ; quickSort(sortArr, 0, sortArr.length - 1); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: O(n log n)

Алгоритм сортировки слиянием на Java

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

Примечание По возможности используйте готовые алгоритмы для коллекций и методы из java.util.Arrays .

Реализовать алгоритм сортировки слиянием на Java можно так:

import java.util.Arrays; public class Main < public static int[] mergeSort(int[] sortArr) < int[] buffer1 = Arrays.copyOf(sortArr, sortArr.length); int[] buffer2 = new int[sortArr.length]; int[] result = mergeSortInner(buffer1, buffer2, 0, sortArr.length); return result; >public static int[] mergeSortInner(int[] buffer1, int[] buffer2, int startIndex, int endIndex) < if (startIndex >= endIndex - 1) < return buffer1; >//уже отсортирован int middle = startIndex + (endIndex - startIndex) / 2; int[] sorted1 = mergeSortInner(buffer1, buffer2, startIndex, middle); int[] sorted2 = mergeSortInner(buffer1, buffer2, middle, endIndex); //слияние int index1 = startIndex; int index2 = middle; int destIndex = startIndex; int[] result = sorted1 == buffer1 ? buffer2 : buffer1; while (index1 < middle && index2 < endIndex) < result[destIndex++] = sorted1[index1] < sorted2[index2] ? sorted1[index1++] : sorted2[index2++]; >while (index1 < middle) < result[destIndex++] = sorted1[index1++]; >while (index2 < endIndex) < result[destIndex++] = sorted2[index2++]; >return result; > public static void main(String args[]) < int[] sortArr = ; int[] result = mergeSort(sortArr); System.out.println(Arrays.toString(result)); > >

Объяснение

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

Сложность алгоритма: O(n log n)

Алгоритм сортировки вставками на Java

Это простая сортировка, при которой массив постепенно перебирается слева направо. При этом элемент сравнивается со всеми предыдущими элементами и размещается так, чтобы оказаться в подходящем месте среди ранее упорядоченных элементов. Так происходит до тех пор, пока набор входных данных не будет исчерпан.

Так выглядит сортировка вставками на Java:

public static void insertionSort(int[] sortArr) < int j; //сортировку начинаем со второго элемента, т.к. считается, что первый элемент уже отсортирован for (int i = 1; i < sortArr.length; i++) < //сохраняем ссылку на индекс предыдущего элемента int swap = sortArr[i]; for (j = i; j >0 && swap < sortArr[j - 1]; j--) < //элементы отсортированного сегмента перемещаем вперёд, если они больше элемента для вставки sortArr[j] = sortArr[j - 1]; >sortArr[j] = swap; > > public static void main(String args[]) < int[] sortArr = ; insertionSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Объяснение

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

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

Сложность алгоритма: О(n2) для сравнений и перестановок.

Алгоритм сортировки выбором на Java

1. Разбиваем массив на отсортированную и неотсортированную части.
2. Находим в неотсортированной части минимальный элемент.
3. Меняем его местами с тем элементом, который находится на нулевой позиции —
   в конец отсортированного массива.
4. Далее находим следующий по величине элемент и меняем его с элементом на первой позиции, etc., пока не закончатся неотсортированные значения.

Реализация сортировки выбором на языке программирования Java:

public static void selectionSort(int[] sortArr) < for (int i = 0; i < sortArr.length; i++) < int pos = i; int min = sortArr[i]; //цикл выбора наименьшего элемента for (int j = i + 1; j < sortArr.length; j++) < if (sortArr[j] < min) < //pos - индекс наименьшего элемента pos = j; min = sortArr[j]; >> sortArr[pos] = sortArr[i]; //меняем местами наименьший с sortArr[i] sortArr[i] = min; > > public static void main(String args[]) < int[] sortArr = ; selectionSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: О(n2)

Алгоритм пирамидальной сортировки на Java

Чтобы реализовать алгоритм пирамидальной сортировки (Heapsort) на Java, нужно сперва понять принцип. Алгоритм сегментирует массив на отсортированный и неотсортированный. Неотсортированный сегмент преобразовывается в кучу (heap), что позволяет эффективно эффективно определить самый большой элемент.

Пирамидальная сортировка на Java с использованием класса java.util.Arrays :

//вернуть левого потомка `A[i]` private static int LEFT(int i) < return (2 * i + 1); >//вернуть правого потомка `A[i]` private static int RIGHT(int i) < return (2 * i + 2); >//вспомогательная функция для замены двух индексов в массиве private static void swap(int[] sortArr, int i, int j) < int swap = sortArr[i]; sortArr[i] = sortArr[j]; sortArr[j] = swap; >//рекурсивный алгоритм heapify-down. Узел с индексом `i` и 2 его прямых потомка нарушают свойство кучи private static void heapify(int[] sortArr, int i, int size) < // получить левый и правый потомки узла с индексом `i` int left = LEFT(i); int right = RIGHT(i); int largest = i; //сравниваем `A[i]` с его левым и правым дочерними элементами и находим наибольшее значение if (left < size && sortArr[left] >sortArr[i]) largest = left; if (right < size && sortArr[right] >sortArr[largest]) largest = right; //поменяться местами с потомком, имеющим большее значение и вызовите heapify-down для дочернего элемента if (largest != i) < swap(sortArr, i, largest); heapify(sortArr, largest, size); >> //функция для удаления элемента с наивысшим приоритетом (присутствует в корне) public static int pop(int[] sortArr, int size) < //если в куче нет элементов if (size int top = sortArr[0]; //заменяем корень кучи последним элементом массива sortArr[0] = sortArr[size-1]; //вызовите heapify-down на корневом узле heapify(sortArr, 0, size - 1); return top; > //функция для выполнения пирамидальной сортировки массива `A` размера `n` public static void heapSort(int[] sortArr) < //строим приоритетную очередь и инициализируем ее заданным массивом int n = sortArr.length; //build-heap: вызывать heapify, начиная с последнего внутреннего //узел до корневого узла int i = (n - 2) / 2; while (i >= 0) < heapify(sortArr, i--, n); >//несколько раз извлекаем из кучи, пока она не станет пустой while (n > 0) < sortArr[n - 1] = pop(sortArr, n); n--; >> public static void main(String args[]) < int[] sortArr = ; heapSort(sortArr); for(int i = 0; i < sortArr.length; i++)< System.out.print(sortArr[i] + "\n"); >>

Сложность алгоритма: O(n log n)

Источник

Алгоритм сортировки пузырьком

Рассмотрим любимую всеми учебную сортировку пузырьком. Пузырьковая сортировка — это учебная сортировка, у которой существует множество модификаций.

Идея пузырьковой сортировки: шаг сортировки состоит в проходе снизу вверх по массиву. По пути просматриваются пары соседних элементов. Если элементы некоторой пары находятся в неправильном порядке, то меняем их местами.

Расположим массив сверху вниз, от нулевого элемента — к последнему.

В результате нулевого прохода минимальный элемент «всплывает» вверх — отсюда и название алгоритма — сортировка пузырьком. Повторяем алгоритм для всех элементов, кроме нулевого — он уже находится на своем месте. И находим второй по величине элемент. Повторяем алгоритм, пока элементы не будут отсортированы.

Рассмотрим программу сортировки пузырьком на Java.

Внешний цикл for отвечает за номер прохода, а внутренний — за перебор элементов в одном проходе. Обмен значений производится с помощью временной переменной tmp . Во внутреннем цикле перебираем значения начиная с последнего (array.length — 1) и в каждом следующем проходе уменьшаем количество просмотренных элементов (j > i) .

public class BubbleSorter < public static void sort(int[] array) < // i - номер прохода for (int i = 0; i < array.length - 1; i++) < // внутренний цикл прохода for (int j = array.length - 1; j >i; j--) < if (array[j - 1] >array[j]) < int tmp = array[j - 1]; array[j - 1] = array[j]; array[j] = tmp; >> > > > 

Будем вызывать метод BubbleSorter.sort() из класса BubbleSorterTest , приведенного ниже. Отсортируем каждую строку многомерного массива data :

import java.util.Arrays; public class BubbleSorterTest < public static void main(String[] args) < int[][] data = < <>, , , , , >; for (int[] arr : data) < System.out.print(Arrays.toString(arr) + " =>"); BubbleSorter.sort(arr); System.out.println(Arrays.toString(arr)); > > > 

Источник