Bubble sort
Bubble Sort, when I saw this algorithm, I remembered the saying "The decimals float up, and the big numbers sink." Through layer by layer comparison, the decimals float to the surface, and the big numbers "sink the stones at the bottom of the water." This achieves the effect of sorting. Bubble sorting is a simple sorting algorithm. It repeatedly visits the sequence to be sorted, compares two elements at a time, and swaps them if they are incorrect. The work of visiting the sequence is repeated until no exchange is needed, that is, the sequence has been sorted. The origin of this algorithm is because the smaller the element will slowly "float" to the top of the sequence via exchange.
The operation of the bubble sorting algorithm is as follows:
1. Compare adjacent elements. If the first one is bigger than the second one, exchange them for the two.
2. Do the same work for each pair of adjacent elements, starting from the first pair to the last pair at the end. At this point, the last element should be the largest number.
3. Repeat the above steps for all elements except the last one.
4. Continue to repeat the above steps for fewer and fewer elements each time until there are no pairs of numbers that need to be compared.
Bubble sorting process diagram:
Example code
public class BubbleSort{ public static int[] bubbleSort(int[] array){ for(int i = 0;i < array.length;i++){ for(int j = 0; j < array.length-i-1;j++){ if(array[j] > array[j+1]){ int temp = array[j]; array[j] = array[j+1]; array[j+1] = temp; } } System.out.println("th"+(i+1)+"sorting"); for(int k = 0;k < array.length;k++){ System.out.print(array[k]+" "); } System.out.println(); } return array; } /** * @param args */ public static void main(String[] args){ int[] array = {7,3,9,5,6,8,1}; bubbleSort(array); }}Print result:
1st order 3 7 5 6 8 1 9Sorting 2nd order 3 5 6 7 1 8 9Sorting 3 5 6 1 7 8 9Sorting 4th order 3 5 1 6 7 8 9Sorting 5th order 3 1 5 6 7 8 9Sorting 6th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 6th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 3 5 6 7 8 9Sorting 5th order 5th order 5th order 5th order 5th order 5th order 5th order 5th
Binary search
After sorting the order, we also need to find the data we want. Dichotomous search is a commonly used, section-time, and basic algorithm. Binary search is to search and compare from the middle position of the sorted data, similar to the middle pair of the wooden stick, so it is also called folding and half-finding. It is a more efficient search method.
[Binary search requirements]: 1. The sequential storage structure must be adopted. 2. The key must be arranged in an orderly manner according to the size of the keyword.
[Pros and Disadvantages] The advantages of the half-finish search method are that it has fewer comparison times, fast search speed, and good average performance; its disadvantage is that the table to be looked up is an ordered table and it is difficult to insert and delete. Therefore, the half-finding method is suitable for orderly lists that are not frequently changed and are frequently found.
[Algorithm Thought] First, compare the keywords recorded in the middle position of the table with the search keywords. If the two are equal, the search will be successful; otherwise, the table will be divided into two sub-tables with the intermediate position record. If the keywords recorded in the middle position are greater than the search keyword, further search for the previous sub-table, otherwise further search for the next sub-table.
Repeat the above process until the record that meets the conditions is found so that the search is successful, or until the child table does not exist, the search is unsuccessful at this time.
[Algorithm Complexity] Assuming that the array length is n, its algorithm complexity is o（log（n））， the worst-case time complexity is O(n)。
Example code
package com.somnus.array;/** * Binary search method* @author Compaq * */public class BinarySearch{ public static int binarySearch(int[] array, int value){ int low = 0; int high = array.length-1; int middle = 0; while(low <= high){ middle = (low+high)/2;//0 6 4 6 6 6 for(int i = 0;i < array.length;i++){ System.out.print(array[i]+" "); if(i == middle)//3 5 6 Print the delimiter immediately following the middle point { System.out.print("## "); } } System.out.println(); if(array[middle] == value){ return middle; } if(value < array[middle]){ high = middle - 1; } if(value > array[middle]){ low = middle + 1; } } return -1; } /** * @param args */ public static void main(String[] args){ int[] array = {7,3,9,5,6,8,1}; int[] array1 = BubbleSort.bubbleSort(array); int index = binarySearch(array1,1); System.out.println("local:"+index); }}Print result:
1st order 3 7 5 6 8 1 9Sorting 2nd order 3 5 6 7 1 8 9Sorting 3 5 6 1 7 8 9Sorting 4th order 3 5 1 6 7 8 9Sorting 5th order 3 1 5 6 7 8 9Sorting 6th order 1 3 5 6 7 8 9Sorting 7th order 1 3 5 6 7 8 91 3 5 6 ## 7 8 91 3 ## 5 6 7 8 91 3 ## 5 6 7 8 9 Location:0
Analysis and summary
In search algorithms, dichotomy is the fastest, but must be an ordered sequence. These are the foundations of algorithms, and we still need to put a lot of effort into experimenting, summarizing, absorbing, and sticking to algorithm learning.