----- Этим утром -----
Что такое пузырьковая сортировка?
пузырьковая сортировка на китайскомBubble Sort, является самым основнымобменная сортировка.
Все, должно быть, пили газированную воду, часто в газированной воде много маленьких пузырьков, которые всплывают наверх. Это связано с тем, что углекислый газ, из которого состоят крошечные пузырьки, легче воды, поэтому крошечные пузырьки могут постепенно всплывать вверх.
Причина, по которой наша пузырьковая сортировка называется пузырьковой, заключается именно в том, что каждый элемент этого алгоритма сортировки может постепенно перемещаться в одну сторону массива в соответствии со своим размером, как маленький пузырь.
Как это переместить? Посмотрим на каштан:
Есть 8 чисел, образующих неупорядоченную последовательность: 5, 8, 6, 3, 9, 2, 1, 7, я надеюсь отсортировать от меньшего к большему.
Согласно идее пузырьковой сортировки, нам нужноСоседние элементы сравниваются попарно, а позиции элементов меняются местами в соответствии с их размером., процесс выглядит следующим образом:
Сначала сравним 5 и 8 и обнаружим, что 5 меньше 8, поэтому положение элемента не меняется.
Затем сравним 8 и 6 и обнаружим, что 8 больше 6, поэтому 8 и 6 поменяются местами.
Продолжайте сравнивать 8 и 3 и найдите, что 8 больше 3, поэтому 8 и 3 меняются местами.
Продолжайте сравнивать 8 и 9 и найдите, что 8 меньше 9, поэтому положение элемента остается неизменным.
Затем сравним 9 и 2 и обнаружим, что 9 больше 2, поэтому 9 и 2 поменяются местами.
Затем сравним 9 и 1 и обнаружим, что 9 больше 1, поэтому 9 и 1 поменяются местами.
Наконец, сравним 9 и 7 и обнаружим, что 9 больше 7, поэтому 9 и 7 поменяются местами.
Таким образом, элемент 9, как самый большой элемент последовательности, плывет и плывет, как маленький пузырь в газировке, и плывет далеко вправо.
На этом первый раунд нашей пузырьковой сортировки закончен. Элемент 9 в крайней правой части последовательности можно рассматривать как упорядоченную область, а упорядоченная область в настоящее время имеет только один элемент.
Теперь давайте проведем второй раунд сортировки:
Сначала сравним 5 и 6 и обнаружим, что 5 меньше 6, поэтому положение элемента не меняется.
Затем сравним 6 и 3 и обнаружим, что 6 больше 3, поэтому 6 и 3 поменяются местами.
Продолжайте сравнивать 6 и 8 и найдите, что 6 меньше 8, так что положение элемента остается неизменным.
Затем сравним 8 и 2 и найдем, что 8 больше 2, поэтому 8 и 2 поменяются местами.
Затем сравним 8 и 1 и обнаружим, что 8 больше 1, поэтому 8 и 1 поменяются местами.
Продолжайте сравнивать 8 и 7 и найдите, что 8 больше 7, поэтому 8 и 7 меняются местами.
После второго раунда сортировки отсортированная область в правой части нашей последовательности состоит из двух элементов в следующем порядке:
Что касается деталей последующего обмена, то здесь мы их подробно описывать не будем, статус после третьего раунда таков:
Статус после четвертого тура выглядит следующим образом:
Статус после пятого раунда следующий:
Статус после шестого тура следующий:
После седьмого тура статус такой (он уже в порядке, поэтому не изменился):
После восьмого тура статус следующий (тоже без изменений):
Пока все элементы в порядке, что и является общей идеей пузырьковой сортировки.
Первоначальная пузырьковая сортировкастабильная сортировка. Поскольку каждый раунд алгоритма сортировки должен пройти через все элементы, количество раундов равно количеству элементов, поэтому временная сложность равнаО (Н ^ 2) .
Первая версия пузырьковой сортировки:
public class BubbleSort {
private static void sort(int array[]){
int tmp = 0;
for(int i = 0; i < array.length; i++){ for(int j = 0; j < array.length - i - 1; j++) { if(array[j] > array[j+1]) { tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; } } }}public static void main(String[] args){ int[] array = new int[]{5,8,6,3,9,2,1,7}; sort(array); System.out.println(Arrays.toString(array));}}
Код очень прост и использует двойной цикл для сортировки. Внешний цикл управляет всеми раундами, а внутренний цикл представляет собой всплывающий процесс каждого раунда, сначала выполняя сравнение элементов, а затем выполняя обмен элементами.
————————————
Каковы точки оптимизации исходной пузырьковой сортировки?
Давайте рассмотрим только что описанные детали сортировки, все еще взяв в качестве примера последовательность 5, 8, 6, 3, 9, 2, 1, 7, когда алгоритм сортировки выполняется до шестого, седьмого и восьмого раундов соответственно. , Статус последовательности следующий:
Очевидно, что начиная с шестого раунда сортировки вся последовательность уже в порядке. Однако наш алгоритм сортировки по-прежнему «добросовестно» продолжает выполнять седьмой и восьмой раунды.
В этом случае, если мы сможем определить, что последовательность уже в порядке, и пометить ее, остальные раунды сортировки можно будет выполнить без исполнения, и работа закончится раньше.
Пузырьковая сортировка, второе издание
public class BubbleSort {
private static void sort(int array[]){
int tmp = 0;
for(int i = 0; i < array.length; i++) { //有序标记，每一轮的初始是true boolean isSorted = true; for(int j = 0; j < array.length - i - 1; j++) { if(array[j] > array[j+1]) { tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; //有元素交换，所以不是有序，标记变为false isSorted = false; } } if(isSorted){ break; } }}public static void main(String[] args){ int[] array = new int[]{5,8,6,3,9,2,1,7}; sort(array); System.out.println(Arrays.toString(array));}}
В эту версию кода внесено небольшое изменение для использования логической переменной isSorted в качестве маркера. Если в этом раунде сортировки элементы меняются местами, значит, последовательность вышла из строя, если нет обмена элементами, значит, последовательность уже упорядочена и сразу выпрыгивает из большого цикла.
Чтобы проиллюстрировать проблему, давайте на этот раз найдем новую последовательность:
Характеристика этой последовательности состоит в том, что первая половина (3, 4, 2, 1) неупорядочена, вторая половина (5, 6, 7, 8) — в порядке возрастания, а элементы второй половины уже являются максимальными. значение последовательности.
Отсортируем по идее пузырьковой сортировки и посмотрим на конкретный эффект:
первый раунд
Элемент 3 и 4 сравниваются, и оказывается, что 3 меньше 4, поэтому позиция остается неизменной.
Элементы 4 и 2 сравниваются и выясняется, что 4 больше 2, поэтому 4 и 2 меняются местами.
Элемент 4 сравнивается с 1 и обнаруживается, что 4 больше 1, поэтому 4 и 1 меняются местами.
Сравнивая элементы 4 и 5, оказывается, что 4 меньше 5, поэтому положение остается неизменным.
Сравнивая элементы 5 и 6, оказывается, что 5 меньше 6, поэтому положение остается неизменным.
Сравнивая элементы 6 и 7, оказывается, что 6 меньше 7, поэтому положение остается неизменным.
Сравнивая элементы 7 и 8, оказывается, что 7 меньше 8, поэтому положение остается неизменным.
В конце первого раунда упорядоченная область последовательности содержит один элемент:
второй раунд
Элементы 3 и 2 сравниваются и выясняется, что 3 больше 2, поэтому 3 и 2 меняются местами.
Элемент 3 сравнивается с 1 и обнаруживается, что 3 больше 1, поэтому 3 и 1 меняются местами.
Элемент 3 и 4 сравниваются, и оказывается, что 3 меньше 4, поэтому позиция остается неизменной.
Сравнивая элементы 4 и 5, оказывается, что 4 меньше 5, поэтому положение остается неизменным.
Сравнивая элементы 5 и 6, оказывается, что 5 меньше 6, поэтому положение остается неизменным.
Сравнивая элементы 6 и 7, оказывается, что 6 меньше 7, поэтому положение остается неизменным.
Сравнивая элементы 7 и 8, оказывается, что 7 меньше 8, поэтому положение остается неизменным.
В конце второго раунда упорядоченная область последовательности содержит один элемент:
Где суть этого вопроса? Ключ заключается в определении упорядоченной области последовательности.
По существующей логике длина сортируемой области и количество раундов сортировки равны. Например, длина упорядоченной области после первого раунда сортировки равна 1, а длина упорядоченной области после второго раунда сортировки равна 2...
На самом деле реальная упорядоченная область последовательности может быть больше этой длины, например, в примере только второй тур, последние пять элементов фактически принадлежат упорядоченной области. Поэтому многие последующие поэлементные сравнения бессмысленны.
Как избежать этой ситуации? В конце каждого раунда сортировки мы можем записать позицию последнего обмена элементами, которая является границей неупорядоченной последовательности, а затем упорядоченной области.
Пузырьковая сортировка третье издание
public class BubbleSort {
private static void sort(int array[]){ int tmp = 0; //记录最后一次交换的位置 int lastExchangeIndex = 0; //无序数列的边界，每次比较只需要比到这里为止 int sortBorder = array.length - 1; for(int i = 0; i < array.length; i++) { //有序标记，每一轮的初始是true boolean isSorted = true; for(int j = 0; j < sortBorder; j++) { if(array[j] > array[j+1]) { tmp = array[j]; array[j] = array[j+1]; array[j+1] = tmp; //有元素交换，所以不是有序，标记变为false isSorted = false; //把无序数列的边界更新为最后一次交换元素的位置 lastExchangeIndex = j; } } sortBorder = lastExchangeIndex; if(isSorted){ break; } }}
public static void main(String[] args){ int[] array = new int[]{3,4,2,1,5,6,7,8}; sort(array); System.out.println(Arrays.toString(array));}}
В этой версии кода sortBorder является границей неупорядоченного массива. В каждом раунде сортировки элементы после sortBorder вообще не нужно сравнивать, и их нужно упорядочивать.
Несколько дополнений:
Этот комикс предназначен исключительно для развлечения, пожалуйста, цените свою текущую работу как можно больше и не подражайте поведению Сяохуэй.
Друзья, которым понравилась эта статья, нажмите и удерживайте изображение, чтобы следить за номером подписки.программист маленький серый, смотрите больше захватывающего контента