“This is the 12th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”

preface

Chapter we explained the heap sort, heap sort of way of thinking is very simple, but for junior programmers to implement or a bit abstract, still need a lot of practice to master, heap speed quickly and recommend junior programmer in-depth understanding, this chapter for everyone to do a side dish, which is one of the three basic sort: bubble sort.

Bubble sort analysis

Bubble sort complexity analysis: Average time complexity O(n^2) The worst time complexity O(n^2) the best time complexity O(n) Space complexity O(1) Stability: Stable

Analysis: from the above parameters we can see that the time speed of bubble sort is relatively slow, the speed is far less than the heap and hill sort mentioned in front, but he and the selection sort has an advantage is easy to master, the code implementation is particularly simple, his space complexity is normal occupation, do not use excess space.

Bubble sort idea

Bubble just as its name implies a bubble, you think bubble is growing bigger and bigger fish directly to the surface, we have this implementation also is same, is a number makes it compared with other values in the array, big run back, and so on, until the entire array is orderly.

The disadvantage of bubbling is that if the array is too disorderly, the number of swaps and the number of loops will be very large, making the sorting process very slow, so sorting is, again, the most appropriate sort for your needs is the best sort.

// private static int[] arr = {6, 5, 3, 2, 4};Let's use the above as an example6 5 3 2 4   // The initial array
5 3 2 4 6   // Compare 6 with each other in the array and find that it is the largest so put it at the end of the array
3 2 4 5 6   // compare 5 with all of array 6, then swap
2 3 4 5 6   // 3 is compared with an array, and then reversed
2 3 4 5 6   // the array is sorted
Copy the code

Bubble sort code implementation

After the above thought we can find that the number of bubble sort swap is a lot of. He is bubbling through constant exchange.

Code implementation:

@test public void bubbleSort() {for (int I = 0; i < arr.length; I++) {for (int j = 0; j < arr.length; If (arr[I] < arr[j]) {int temp = arr[I]; arr[i] = arr[j]; arr[j] = temp; } } } System.out.println(getArr(arr)); }Copy the code