Bubble sort is a classic interview question in which the largest number is placed last or the smallest number is placed first. Here is a question:
1, problem,
If you were to rank this set of data from smallest to largest, you’d say, I can see it straight away, I can sort it out in a minute.
[75,66,33,34,31,337,65,346]
That’s because there are only 8 numbers here. What if there are 800?
So we have to use computers, algorithms.
So just to make it easier, let’s think of these eight numbers as 800, and it’s the same idea, but let’s see how bubble sort works.
2. Bubbling sort idea
- Basic idea: bubbling sort, similar to bubbling in water, the larger number sinks and the smaller number rises slowly. Assume that from small to large, that is, the larger number slowly moves to the back row and the smaller number slowly moves forward.
- Visually, each time you walk, you move the largest number to the end of the sequence.
Conclusion: Each cycle is compared from the starting position n and n+1, and the cycle is switched when the conditions are met.
3. Fundamentals
Compare the values of adjacent elements in pairs from back to front (or from front to back) or, in reverse order, swap them until the sequence is compared. This process is called a bubble sort, and it only takes n-1 sort at most. Each sorting can move an element to the final position, and the elements that have been determined to the final position do not need to be compared in subsequent processing. If no “swap” occurs in a particular sort, the algorithm can end prematurely.
4. Sorting algorithm
Bubble sort flow chart:
4.1. Javascript implementation code
<script type="text/javascript">
function maopao(array){
var temp;
for(var i=0; i<array.length; i++){// Compare the number of trips, starting with the first one
for(var j=0; j<array.length-i-1; j++){// How many times to compare each trip
if(array[j]>arra[j+1]){
temp=array[j];
array[j]=array[j+1];
array[j+1]=temp; }}};return array;
}
var numbers=[65.4.43.37.31.17.6.46];
var s=maopao(numbers);
console.log(s);
</script>
Copy the code4.2 Java implementation code
Java bubble sort and javascript bubble sort is the same principle, the difference is different language, the following to achieve Java bubble sort.
public static void main(String[] args) {
int[] arr = {3.2.3.4.5};
for (int i = 0; i < arr.length-1; i++) {
for (int j = 0; j <arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
temp(arr, j, j+1); }}}}Copy the codeThere’s nothing wrong with writing this code in an interview, but the best option is to use recursion. You’ll impress your interviewer.
Optimize bubble sort and test its best time complexity
Bubble sort is done by comparing and swapping adjacent values in an array through a loop. So, for sorted and unsorted arrays of the same length, they take the same amount of time.
5. Use recursion to optimize bubble sort
Bubble sort (the default for the following methods is to use an ordered array from smallest to largest)
public static void bubbleSort(int[] arr) {
for (int i = 0; i < arr.length-1; i++) {
long start = System.currentTimeMillis();
/* Recursively determine if arr[n] > ARr [n+1] or ARr [n] > arr[n+1] 1. When the array is ordered, the fastest time complexity is N 2. When the array is completely unordered, the time complexity is higher than ordinary bubble sort */
boolean flag = recursion(arr,i);
long end = System.currentTimeMillis();
System.out.println("Recursion time:"+(end-start));
// If flag==true, the array is ordered, and the sorting method ends directly
if (flag) break;
for (int j = 0; j <arr.length-1-i; j++) {
if (arr[j] > arr[j+1]) {
temp(arr, j, j+1); }}}}/ / print
public static void print_b(int[] arr) {
System.out.print("[");
for (int i = 0; i < arr.length; i++) {
if( i == arr.length-1 ) System.out.print(arr[i]);
else System.out.print(arr[i] + ",");
}
System.out.println("]");
}
/ / exchange
public static void temp(int[] arr , int num1,int num2) {
int temp = arr[num1];
arr[num1] = arr[num2];
arr[num2] = temp;
}
Copy the codeRecursive method
- The call method passes the array arr and the current array subscript n
- We recursively compare values with subscripts n plus 1
- Returns true if n == arr. Length-1 that is, n has reached the index of the last value of the array
- Return false and terminate the method if arr[n] > arr[n+1] exists
/ / recursion
public static boolean recursion(int[] arr,int n ) {
if (n == arr.length-1) {
return true;
}else if (arr[n] > arr[n+1]) {return false;
}
return recursion(arr, n+1);
}
Copy the codesummary
1. The bubble sort, generally is processed by two layers of cycle, the first layer circulation mainly in order to let the bubble sort is successful, the array needs how many large cycle, here we identified in a greater than or equal to two digital array (because there is only a digital array do not need to sort), to identify a number of sort requires a large cycle, That is, n numbers have n-1 major cycles; The second loop mainly compares the first number of the array with the following number, and then determines the sort.
2. To sum up, when the second loop completes, the first big loop completes once, so the array has determined the sort of a number. After all the loops complete, the bubble sort (from small to large) is complete.
In this case, the largest is always put in the back, so we have the last row, we do the first n minus 1 again, so we have another maximum, again, and finally we have the end of the row.
4. Bubble sort, because it is relatively simple and easy to understand, often becomes the first thought of the sorting algorithm problem in the interview. If you are good at writing, you are not afraid of interviewing.