Simple understanding of bubble sorting

High quality resource sharing

Learning route guidance （ Click unlock ）	Knowledge orientation	Crowd positioning
🧡 Python Actual wechat ordering applet 🧡	Progressive class	This course is python flask+ Perfect combination of wechat applet , From the deployment of Tencent to the launch of the project , Create a full stack ordering system .
Python Quantitative trading practice	beginner	Take you hand in hand to create an easy to expand 、 More secure 、 More efficient quantitative trading system

Detailed description

Bubble sort is a sort of exchange sort , The basic idea is to sort in a set of numbers , All numbers in the range that are not currently ordered , Compare and adjust the two adjacent numbers from top to bottom , Let the larger number sink , Smaller up .

That is, whenever two adjacent numbers are compared and their order is found to be opposite to the sorting requirements , Just swap them .

The detailed implementation steps of bubble sorting are as follows ：

1. Let's start with the first element , Compare adjacent elements , If the former is bigger than the latter , Just exchange the two of them ;
2. Before and after , Do the same for each pair of adjacent elements , From the beginning of the first couple to the end of the last couple , So the last element will be the largest number ;
3. Put the largest element found this time on the last element position , Then repeat the above for all elements except the largest element 1~2 step ;
4. Repeat the above steps , Until the last element and the second element are compared 、 In exchange for , Then the sorting is finished .

Algorithm diagram

Problem solving

Is bubble sorting an in place sort algorithm ？

Bubble sort is an in place sort algorithm , The process only involves the exchange of adjacent data , Only temporary space at the constant level is needed , Its spatial complexity is O(1).

Is bubble sort a stable sort algorithm ？

In order to ensure the stability of bubble sorting algorithm , When there are two adjacent elements of equal size, no exchange is required , Data of the same size will not change the order before and after sorting , So bubble sort is a stable sort algorithm .

What is the time complexity of bubble sorting ？

Using the optimal time complexity solution , The time complexity when the original sequence is ordered is O(n); The worst case time complexity is O(n2); The average time complexity is O(n2).

Code implementation

|  | package cn.fatedeity.sort; |
|  |  |
|  | public class BubbleSort { |
|  | private static void swap(int[] numbers, int src, int target) { |
|  | int temp = numbers[src]; |
|  |  numbers[src] = numbers[target]; |
|  |  numbers[target] = temp; |
|  |  } |
|  |  |
|  | public static int[] sort(int[] numbers) { |
|  | for (int i = 0; i < numbers.length - 1; i++) { |
|  | boolean doSwap = false; |
|  | for (int j = 0; j + 1 < numbers.length - i; j++) { |
|  | if (numbers[j] > numbers[j + 1]) { |
|  |  swap(numbers, j, j + 1); |
|  |  doSwap = true; |
|  |  } |
|  |  } |
|  | //  Steps to optimize basic bubble sorting  |
|  | if (!doSwap) { |
|  | //  If you traverse the entire sequence, you don't need to exchange , It means that the whole sequence has been completely ordered  |
|  | return numbers; |
|  |  } |
|  |  } |
|  | return numbers; |
|  |  } |
|  | } |