Article catalog
1, Array sorting algorithm
1. Binary search
- Overview of binary search
When finding the position of the specified element in the array, the previous method is to get each element one by one through traversal to see whether it is the element to be found. This method is when the number is When there are many group elements, the search efficiency is very low
Binary search is also called half search. Half of the search range can be removed each time, so as to improve the efficiency of search
- demand
Find the position of an element in the array {1,2,3,4,5,6,7,8,9,10}
- Implementation steps
- Define two variables that represent the range to find. Default min = 0, max = maximum index
- Loop search, but min < = max
- Calculate the value of mid
- Judge whether the element at the mid position is the element to be searched. If so, directly return the corresponding index
- If the value to be found is in the left half of mid, the min value remains unchanged, max = mid -1 Continue with the next cycle
- If the value to be found is in the right half of mid, the max value remains unchanged, min = mid + 1 Continue with the next cycle
- When min > max, it means that the element to be found does not exist in the array, and - 1 is returned
- code implementation
public class MyBinarySearchDemo {
public static void main(String[] args) {
int [] arr = {1,2,3,4,5,6,7,8,9,10};
int number = 11;
//1. What am I going to do now--- Binary search
//2. What do I need to do this--- Array element
//3. I'm finished. Do you want to return the result to the caller - return the index to the caller
int index = binarySearchForIndex(arr,number);
System.out.println(index);
}
private static int binarySearchForIndex(int[] arr, int number) {
//1. Define the search range
int min = 0;
int max = arr.length - 1;
//2. Circular search min < = max
while(min <= max){
//3. Calculate the mid position
int mid = (min + max) >> 1;
//Element to which mid points > num be
if(arr[mid] > number){
//Indicates that the element to be found is on the left
max = mid -1;
}else if(arr[mid] < number){
//Element pointed to by mid < num be
//Indicates that the element to be found is on the right
min = mid + 1;
}else{
//Element pointed to by mid = = num be
return mid;
}
}
//If min is greater than max, it indicates that the element does not exist and returns - 1
return -1;
}
}- matters needing attention
There is a precondition that the elements in the array must be arranged in size order. If there is no size order, the binary search method cannot be used
2. Bubble sorting
- Bubble sorting overview A sort method, which compares the adjacent data in the data to be sorted, puts the larger data behind, and operates all the data in turn until all the data are sorted as required If there are n data to sort, a total of n-1 comparisons are required After each comparison, one less data will be involved in the next comparison
- code implementation
public class MyBubbleSortDemo2 {
public static void main(String[] args) {
int[] arr = {3, 5, 2, 1, 4};
//1 2 3 4 5
bubbleSort(arr);
}
private static void bubbleSort(int[] arr) {
//The outer loop controls the number of times less than the length of the array
for (int i = 0; i < arr.length -1; i++) {
//Memory loops are compared with actual loops
//-1 is to keep the array from going out of bounds
//-i at the end of each round, we will have less than one number
for (int j = 0; j < arr.length - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
printArr(arr);
}
private static void printArr(int[] arr) {
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
}
}3. Quick sort
- Quick sort overview
In the bubble sorting algorithm, the end of a cycle is equivalent to determining the current maximum value and the position where the maximum value should be stored in the array
In the quick sort algorithm, each recursion takes the first number as the reference number to find all the numbers in the array that are smaller than the reference number Find all the larger than the benchmark Small Put all on the left and all the large ones on the right to determine the correct position of the reference number
- Core steps
- Start from the right and find the one smaller than the reference number
- Start from the left and find the one larger than the reference number
- Swap the position of two values
- Red continues to look left and blue continues to look right until the two arrows point to the same index
- Reference number homing
- code implementation
public class MyQuiteSortDemo2 {
public static void main(String[] args) {
// 1. Start from the right and find the one smaller than the benchmark number
// 2. Start from the left and find the one larger than the reference number
// 3. Exchange the position of two values
// 4. Red continues to look to the left and blue continues to look to the right until the two arrows point to the same index
// 5. Datum number homing
int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};
quiteSort(arr,0,arr.length-1);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i] + " ");
}
}
private static void quiteSort(int[] arr, int left, int right) {
// Conditions for the end of recursion
if(right < left){
return;
}
int left0 = left;
int right0 = right;
//Calculate the reference number
int baseNumber = arr[left0];
while(left != right){
// 1. Start from the right and find the one smaller than the benchmark number
while(arr[right] >= baseNumber && right > left){
right--;
}
// 2. Start from the left and find the one larger than the reference number
while(arr[left] <= baseNumber && right > left){
left++;
}
// 3. Exchange the position of two values
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
//Reference number homing
int temp = arr[left];
arr[left] = arr[left0];
arr[left0] = temp;
// Recursively call yourself to order the left half
quiteSort(arr,left0,left-1);
// Recursively call yourself and put the right half in order
quiteSort(arr,left +1,right0);
}
}4.Arrays
- Common methods of Arrays
- Sample code
public class MyArraysDemo {
public static void main(String[] args) {
// public static String toString(int[] a) returns the string representation of the contents of the specified array
// int [] arr = {3,2,4,6,7};
// System.out.println(Arrays.toString(arr));
// public static void sort(int[] a) sorts the specified array in numerical order
// int [] arr = {3,2,4,6,7};
// Arrays.sort(arr);
// System.out.println(Arrays.toString(arr));
// public static int binarySearch(int[] a, int key) uses binary search to return the index of the specified element
int [] arr = {1,2,3,4,5,6,7,8,9,10};
int index = Arrays.binarySearch(arr, 0);
System.out.println(index);
//1. The array must be ordered
//2. If the element to be searched exists, the actual index of the element is returned
//3. If the element to be searched does not exist, then (- insertion point - 1) is returned
//Insertion point: if this element is in the array, which index should it be in
}
}- Tool design idea
- The construction method is decorated with private
- Members are decorated with public static