<>java: A detailed summary of some algorithms used in array

<> One , concept

An array is a container , That can store elements of the same type “ container ”;

be careful :

The subscript is used for each element of the array , To represent an element ,

​ Subscript by 0 start , instead of 1,

therefore :

The last element subscript is one numerical unit smaller than the actual length ;

<> Two , definition

data type [] Array name ;

<> Three , Initialization of array
dynamic initialization : When defining an array , Specifies the array length , The system automatically assigns initial values to array elements by default ​ format : data type [] Array name =new data type [ Array length ];
initiate static : Specify the contents of array elements directly , The system specifies the array length ; ​ format : data type [] Array name =new data type []{x1,x2,x3........}; ​
Abbreviation : data type [] Array name ={x1,x2,x3......}; Wrong way of writing : ​ data type [] Array name = new data type [ Array length ]{x1,x2,x3.
..}; be careful : Bracket [] , It can be written before and after the array name , No grammatical errors will occur , According to personal habits ;
Sample code :
public static void main(String[] args) { // dynamic initialization : The array length is defined as 6 Integer array of arr; int [] arr
=new int[6]; // initiate static : The array length is defined as 3 Integer array of arr2; int [] arr2=new int[] {1,2,3};
// Short for static initialization : Direct write elements are defined 1,2,3 Integer array of arr3; int [] arr3= {1,2,3}; }
<> Four , Application of classical algorithm of array

1, Array traversal

thinking : application for Loop through the array elements in turn , And output ;
public static void main(String[] args) { // Statically initialized A length of 6 The integer array of arr; int [] arr= {
1,2,3,4,5,6}; //for Loop through array And display // The output code here is written for beautiful output , Unnecessary ; System.out.print(" Array content :[");
for(int x=0;x<arr.length;x++) { if(arr.length-1==x) { System.out.print(arr[x]+
"]"); }else { System.out.print(arr[x]+","); } } }
Operation results :
Array content :[1,2,3,4,5,6]
2, Find the maximum number in the array

thinking :

1, Hypothesis comparison , Suppose a maximum number ;

2, application for The loop compares each array element backward in turn ;

3, Greater than the assumed number becomes the maximum , And output ;
public static void main(String[] args) { // Statically initialized A length of 6 The integer array of arr, Find its maximum number ; int [
] arr= {20,60,52,70,90,4}; // Suppose a maximum max; int max=0; //for The loop compares the outputs in turn for(int x=0;x<
arr.length;x++) { // Elements greater than maximum , Become the maximum , Compare with the next element if(arr[x]>max) { max=arr[x]; } }
System.out.println(" The maximum number is :"+max); }
Operation results :
The maximum number of arrays is :90
3, Array elements in reverse order

thinking : Reverse sort array

1, It can be concluded that the intermediate interval must not exist or move in any case ;

2, So use it for loop , Divide the array into two pairs of symmetric elements before and after comparison

Exchange positions in pairs , End of cycle , Get the result and output it ;
public static void main(String[] args) { // Statically initialized A length of 6 The integer array of arr, Output it in reverse ; int
[] arr= {1,2,3,4,5,6}; System.out.println(" Array before reverse sort :"); getShow(arr); //for loop
//length/2 Split the array into two for(int x=0;x<arr.length/2;x++) { // Intermediate variable of element exchange int temp=0; temp
=arr[x]; arr[x]=arr[arr.length-1-x]; arr[arr.length-1-x]=temp; } // Output method System.
out.println(" Array sorted in reverse order :"); getShow(arr); } // Traversal output method public static void getShow(
int [] arr) { System.out.print("["); for(int x=0;x<arr.length;x++) { if(arr.
length-1==x) { System.out.println(arr[x]+"]"); }else { System.out.print(arr[x]+
","); } } }
Operation results :
Array before reverse sort : [1,2,3,4,5,6] Array sorted in reverse order : [6,5,4,3,2,1]
Four , Array simple query

thinking :

1,for Loop through array , Contrast in turn ,if== Determine whether the query element exists in the array ;

2, There are return subscripts , There is no return -1;
public static void main(String[] args) { // Statically initialized A length of 6 The integer array of arr, Output it in reverse ; int
[] arr= {1,2,3,4,5,6}; // Find numbers 5 stay array arr Location in ; findArr(arr, 5); } // Element search method The parameter is arr
Array to query ,key Number of queries // Return element subscript found // No return found -1 public static int findArr(int [] arr,
int key) { int index=-1; for(int x=0;x<arr.length;x++) { if(arr[x]==key) {
System.out.println(" The number queried is indexed as :"+x); break; } } return -1; }
Operation results :
The number queried is indexed as :4
Five , Binary array search method

Dichotomy premise : Array ordering

thinking :1, Set a Array subscript intermediate value variable mid, The initial value is : ( upper bound - Lower bound )/2 Array subscript of ;

​ 2, Set a Array subscript upper bound variable top The initial value is : Index of the last element of the array ;

​ 3, Set a Array subscript lower bound variable bottom The initial value is : First element subscript of array ;

​ 4,for loop , Match the found element with the mid Subscript array variable Cyclic comparison ;

​ 5, If the search element is greater than mid, be mid variable +1, Become bottom, meanwhile mid Recalculate ;

​ 6, If the search element is less than mid, be mid variable -1, Become top, meanwhile mid Recalculate ;

​ 7, Output the query results ; The query cannot output the result in advance after output ;
public static void main(String[] args) { // Statically initialized A length of 6 The integer array of arr, Output it in reverse ; int
[] arr= {1,2,3,4,5,6}; // Find numbers 5 stay array arr Location in ; findArr(arr, 5); } // Binary element search method
// Return subscript found , Judge the situation surrounding the array in advance ; public static void findArr(int [] arr,int key) {
// Define initial defining variables int top=arr.length-1; int bottom=0; // Judge whether the query data is in the array in advance if(key>arr[top]
||key<arr[bottom]) { System.out.println(" The query value is not in the array "); } //for Circular judgment search for(int x
=0;x<arr.length;x++) { // take mid Defined in for Inside the loop In order to dynamically change the intermediate value ; int mid=(top+bottom)/2;
// If parameter key= Intermediate variable mid, The query result is returned if(key==arr[mid]) { System.out.println(" Array element queried "+key+
" The array index of is :"+mid); break; } // If the search element is greater than mid, be mid variable +1, Become bottom, meanwhile mid Recalculate ; if(key>arr
[mid]) { bottom=mid+1; } // If the search element is less than mid, be mid variable -1, Become top, meanwhile mid Recalculate ; if(key<arr[mid
]){ top=mid-1; } } }
Operation results :
Array element queried 5 The array index of is :4
Six , Bubble sort

thinking :

1, Compare two adjacent elements , The left element is larger than the right element , Then left and right swap ;

2, Each pair of adjacent elements is compared in this way backward , Until the maximum element is placed in the last bit of the array ;

3, Traversal array , Repeat the above steps , Remove the last round and the largest elements that have been selected ( As more and more maximum values are selected , The number of pairwise comparisons will be reduced accordingly );
public class Test { public static void main(String[] args){ // Define an array arr int []
arr= {3,5,4,1,2}; // Array before sort System.out.println(" Array before sort :"); printShow(arr);
// Outer control repeat step again for(int i=0;i<arr.length-1;i++){ // Inner layer for Cycle control Control the number of pairwise comparison of array elements for(int j
=0;j<arr.length-1-i;j++) { if(arr[j]>arr[j+1]) { //temp As an intermediate value // If the former is greater than the latter Then switch positions
int temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } // Output sorted array System.out.
println(" Sorted array :"); printShow(arr); } // Traverse the array and display the method public static void printShow(
int [] arr) { System.out.println(" The array is as follows :"); 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(""); } }
Operation results :
Array before sort : The array is as follows : [3,5,4,1,2] Sorted array : The array is as follows : [1,2,3,4,5]
epilogue : Arrays are widely used , The above summary introduces some common algorithms of array , And the definition of the array ; skill comes from practice , You can copy the above example of code more practice ;

no , no ,! No one really likes it !..!!

Technology
©2020 ioDraw All rights reserved
148 Billion ! All shares of Evergrande clearing group Front end code specification you don't know Kaldi The father of Daniel Povey doctor : release k2 Core code Java Programmers haven't mastered it yet SpringBoot? This is a document , You should study hard Qualcomm licensed chip , Still hard to prevent Huawei from being replaced by millet 5G Base station power consumption , How terrible is it ?python Express your love Python Romantic confession source code ( With detailed tutorial )JAVA How to output log gracefully in the background vue Mobile end head assembly