Принцип: сравните два смежных элемента и обмена элементами с большими значениями с правой частью.
Идея: Сравните два смежных числа в последовательности, поместите десятичные тквималы спереди и большие числа сзади. То есть в первой поездке: сначала сравните первые и вторые цифры, поместите десятичное значение до и большие числа после. Затем сравните второе число и третье число, поместите десятичное значение до и после большого числа, продолжайте так, пока не будут сравниваться последние два числа, поместите десятичное значение до и после большого числа. Повторите первый шаг, пока вся сортировка не будет завершена.
Например: сортировать массив: int [] arr = {6,3,8,2,9,1};
Первый заказ:
Первый сортировка: 6 и 3 сравнения, 6 больше, чем 3, Положение свопа: 368291
Второй сортировка: 6 и 8 сравнить, 6 меньше 8, без обмена позиции: 368291
Третий заказ: 8 и 2 сравнения, 8 больше, чем 2, Положение свопа: 362891
Четвертый заказ: 8 и 9 сравнить, 8 меньше 9, без обмена позиции: 362891
Пятый заказ: 9 и 1 Сравнение: 9 больше 1, Положение свопа: 362819
Первая поездка сравнивалась в общей сложности 5 раз, сортируя результаты: 362819
---------------------------------------------------------------------
Второй заказ:
Первая сортировка: 3 и 6 сравнение, 3 - меньше 6, без обмена позиции: 362819
Вторая сортировка: 6 и 2 сравнения, 6 - больше 2, положения свопа: 326819
Третий заказ: 6 и 8 сравниваются, 6 больше 8, без обмена позиции: 326819
Четвертый заказ: 8 и 1 сравнение, 8 больше 1, Положение свопа: 326189
Вторая поездка сравнивалась в общей сложности, и результат сортировки был: 326189
---------------------------------------------------------------------
Третий заказ:
Первый сортировка: 3 и 2 сравнивать, 3 больше 2, положения свопа: 236189
Вторая сортировка: 3 и 6 сравнивать, 3 меньше 6, без обмена позиции: 236189
Третий заказ: 6 и 1 сравнение, 6 - больше 1, Положение свопа: 231689
Вторая поездка сравнивалась в общей сложности, и результат сортировки был: 231689
---------------------------------------------------------------------
Четвертый заказ:
Первая сортировка: 2 и 3 сравнения, 2 меньше 3, без обмена позиции: 231689
Вторая сортировка: 3 и 1 Сравнение, 3 больше 1, Положение свопа: 213689
Вторая поездка сравнивалась в общей сложности, и результат сортировки был: 213689
---------------------------------------------------------------------
Пятый заказ:
Первый сортировка: 2 и 1 сравнение, 2 больше, чем 1, Положение свопа: 123689
Вторая поездка сравнивалась в общей сложности, и результат сортировки был: 123689
---------------------------------------------------------------------
Окончательный результат: 123689
---------------------------------------------------------------------
Исходя из этого, мы видим, что n чисел необходимо отсортировать, и в общей сложности сортируется n-1. Количество времени сортировки для каждого I-Pass составляет (Ni), поэтому вы можете использовать оператор двойного цикла для управления, сколько раз наружный слой будет контролировать количество раз для каждой поездки, то есть, то есть
for (int i = 1; i <arr.length-1; i ++) {for (int j = 1; j <arr.length-1-i; j ++) {// Положение свопа}Преимущества сортировки пузырьков: каждый раз, когда вы сортируете, вы будете сравнивать меньше, потому что каждый раз, когда вы сортируете, вы найдете большее значение. Как упомянуто выше: после первого сравнения, последнее число должно быть самым большим числом. При сортировке во второй раз вам нужно только сравнить другие числа, кроме последнего числа, и вы также можете обнаружить, что наибольшее число ранжируется после того, как число участвует во втором сравнении. Сравнивая третий раз, вам нужно только сравнивать другие числа, кроме последних двух чисел, и т. Д., Другими словами, если вы не выполняете сравнение, каждый раз, когда вы сравниваете один раз, что в определенной степени уменьшает количество алгоритма.
С точки зрения сложности времени:
1. Если наши данные в порядке, нам нужно только отправиться в поездку, чтобы завершить сортировку. Требуемое количество сравнений и движений записей являются минимальным значением, то есть: cmin = n-1; mmin = 0; Следовательно, лучшая сложность времени для сортировки пузырьков - O (n).
2. Если, к сожалению, наши данные являются обратным порядком, требуется заказ N-1. Каждый заказ должен быть сравнивать (1≤i≤n-1), и каждое сравнение должно быть перемещено в запись три раза, чтобы достичь позиции записи обмена. В этом случае сравнение и время движения достигают максимума: худшая сложности пузырьков: O (N2).
Подводя итог: общая средняя сложности пузырьковой сортировки: O (N2).
Реализация кода:
/ * * Bubble Sort */public class bubblesort {public static void main (string [] args) {int [] arr = {6,3,8,2,9,1}; System.out.println («Массив перед сортировкой:»); for (int num: arr) {System.out.print (num+""); } for (int i = 1; i <arr.length; i ++) {// Внешний цикл контролирует количество времени сортировки для (int j = 1; j <arr.length-i; j ++) {// внутренний цикл контролирует, сколько раз каждый раз он сортируется, если (arr [j-j]> arr [j]) {int temp = arr [J]; arr [j] = arr [j-1]; arr [j-1] = temp; }}} System.out.println (); System.out.println («Сортированный массив:»); for (int num: arr) {System.out.print (num+""); }}}