Пузырьковая сортировка — один из самых простых алгоритмов сортировки в программировании. Он неоднократно проходит через последовательность, подлежащую сортировке, сравнивая два элемента за раз и меняя их местами, если они находятся в неправильном порядке. Повторяйте работу по посещению массива до тех пор, пока не останется элементов, требующих обмена, а это значит, что массив отсортирован.
Сортировка пузырьком похожа на пузырьки, выходящие из воды: при сортировке пузырьком наименьшее или наибольшее число, в зависимости от того, сортируем ли мы массив по возрастанию или убыванию, пузырьки всплывают ближе к началу или концу массива.
1) Сравните соседние элементы. Если первый больше второго, поменяйте их местами.
2) Сделайте то же самое для каждой пары соседних элементов, начиная с первой пары и заканчивая последней парой, после чего последний элемент должен иметь наибольшее число.
3) Повторите описанные выше действия для всех элементов, кроме последнего.
4) Продолжайте повторять описанные выше шаги для все меньшего и меньшего количества элементов, пока не останется пар чисел для сравнения.
Пузырьковая сортировка работает хуже по сравнению с другими алгоритмами сортировки, такими как быстрая сортировка, сортировка слиянием или сортировка оболочкой. Средняя сложность этих алгоритмов составляет O(nlogn), а средняя сложность пузырьковой сортировки — O(n^2).
В лучшем случае пузырьковая сортировка лучше, чем быстрая сортировка с производительностью O(n). Пузырьковая сортировка в три раза медленнее, чем быстрая сортировка или сортировка слиянием, даже при n=100, но ее легче реализовать и запомнить.
Сложность и производительность пузырьковой сортировки следующие:
1) Наихудшая производительность пузырьковой сортировки равна O(n^2).
2) Наилучшая производительность пузырьковой сортировки — O(n).
3) Средняя производительность пузырьковой сортировки равна O(n^2).
//Пузырьковая сортировка publicstaticvoidbubbleSort(int[]arr){//Внешний цикл используется для управления количеством оборотов цикла массива for(inti=0;i<arr.length-1;i++){//Внутренний цикл используется для завершения сравнения значений элементов и замены больших значений элементов назад for(intj=0;j<arr.length-1-i;j++){if(arr[j]>arr [j+1]){inttemp= arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}//Вывод результата for(intn:nums){System .out.println(n);} }Например:
publicclassMain{publicstaticvoidmain(String[]args){inta[]={6,1,15,32,9};for(inti=1;i<a.length;i++){for(intj=0;j<a .length-1;j++){if(a[j]>a[j+1]){inttemp=a[j];a[j]=a[j+1];a[j+1]=temp ;}}}System.out.println(Результат пузырьковой сортировки:);for(inttemp:a){System.out.print(temp+);}}}Результаты бега следующие:
Результат пузырьковой сортировки: 1691532.
Вы можете попробовать это сами!