The content of this paper comes from the arrangement of network resources , If there is a mistake , Please correct me .

java Common sorting methods in

java Several sorting methods in common use in : Select sort , Insert sort , Quick sort , Bubble sort , Merge sort ,shell sort .
java The search methods in are : Sequential search method , Binary search method

Select sort

thinking : In an out of order array , Assume that the first digit is the smallest , Compare the following numbers in turn , If you encounter a number smaller than it, swap positions , The first number in a row is the smallest number in the sequence , Then repeat from the second number .
public static void selectSort(int[] array) { int position = 0; for (int i = 0;
i <array.length; i++) { int j = i + 1; position = i; int temp = array[i]; for
(; j <array.length; j++) { if (array[j] < temp) { temp = array[j]; position =
j; } }array[position] = array[i]; array[i] = temp; }
System.out.println(Arrays.toString(array) + " selectSort"); }
Insert sort

thinking : It's like playing cards , Each time you touch a card, compare it with the card in your hand , Always put a card in front of a bigger card , Behind the smaller card . In this way, when the cards are all touched on the hand , It's an ordered sequence .
public static void insertSort(int[] array) { for (int i = 1; i < array.length;
i++) {int temp = array[i]; int j = i - 1; for (; j >= 0 && array[j] > temp;
j--) {// Will be greater than temp The value of is moved back one unit as a whole array[j + 1] = array[j]; } array[j + 1] = temp; }
System.out.println(Arrays.toString(array) + " insertSort"); }
shell sort

Shell Sort , Also known as decreasing incremental sort algorithm , Is a more efficient version of insert sort . Hill sort is an unstable sort algorithm .
Hill sort is based on the following two properties of insertion sort :
Insert sort is used to operate on almost ordered data , efficient , That is, the efficiency of linear sorting can be achieved ;
But insertion sort is generally inefficient , Because insert sort can only move data one bit at a time .
Take a positive integer first d1 < n, Keep everything apart d1 A set of records , Direct insertion sort within each group ; then d2 < d1, Repeat the above grouping and sorting operations ; until di =
1, That is, all records are put into a group for sorting .

public static void shellSort(int[] array) { int i; int j; int temp; int gap = 1
;int len = array.length; while (gap < len / 3) { gap = gap * 3 + 1; } for (;
gap >0; gap /= 3) { for (i = gap; i < len; i++) { temp = array[i]; for (j = i -
gap; j >=0 && array[j] > temp; j -= gap) { array[j + gap] = array[j]; } array[j
+ gap] = temp; } } System.out.println(Arrays.toString(array) + " shellSort"); }
Bubble sort

thinking : In the set of numbers to sort , For all the numbers in the range that are not ordered at present , The two adjacent numbers are compared and adjusted from top to bottom , Let the larger number sink , The smaller ones go up . Namely : Whenever two adjacent numbers are compared and found to be in reverse order , Just swap them .
code :
public static void bubbleSort(int[] array) { int temp = 0; for (int i = 0; i <
array.length - 1; i++) { for (int j = 0; j < array.length - 1 - i; j++) { if (
array[j] > array[j + 1]) { temp = array[j]; array[j] = array[j + 1]; array[j + 1
] = temp; } } } System.out.println(Arrays.toString(array) + " bubbleSort"); }
Quick sort

Quicksort is one of the fastest sorting methods , It is an improvement of bubble sort , It belongs to unstable ordering .

public static void quickSort(int[] array) { _quickSort(array, 0, array.length -
1); System.out.println(Arrays.toString(array) + " quickSort"); } private static
int getMiddle(int[] list, int low, int high) { int tmp = list[low]; // The first of the array is used as the center axis
while (low < high) { while (low < high && list[high] >= tmp) { high--; } list
[low] =list[high]; // Records smaller than the center axis move to the low end while (low < high && list[low] <= tmp) {
low++; }list[high] = list[low]; // Records larger than the center axis move to the high end } list[low] = tmp; // Center axle to tail
return low; // Return to the position of the center axis } private static void _quickSort(int[] list, int low, int
high) {if (low < high) { int middle = getMiddle(list, low, high);
// take list The array is divided into two parts _quickSort(list, low, middle - 1); // Recursively sort low word list _quickSort(list
, middle +1, high); // Recursively sort high word list } }
Merge sort

thinking : Merger (Merge) The sorting method is to combine two ( Or more than two ) Ordered tables are merged into a new ordered table , That is, the sequence to be sorted is divided into several subsequences , Each subsequence is ordered . Then, the ordered subsequences are merged into a whole ordered sequence .

code :
public static void mergingSort(int[] array) { sort(array, 0, array.length - 1
); System.out.println(Arrays.toString(array) + " mergingSort"); } private static
void sort(int[] data, int left, int right) { if (left < right) { // Find the middle index int
center = (left + right) /2; // Recursion on the left array sort(data, left, center); // Recursion on the right array
sort(data, center +1, right); // merge merge(data, left, center, right); } }
private static void merge(int[] data, int left, int center, int right) { int[]
tmpArr =new int[data.length]; int mid = center + 1; //third Record the index of the intermediate array int third
= left;int tmp = left; while (left <= center && mid <= right) {
// Take the smallest of the two arrays and put it into the middle array if (data[left] <= data[mid]) { tmpArr[third++] =
data[left++]; }else { tmpArr[third++] = data[mid++]; } } // The rest is placed in the middle array in turn while
(mid <= right) { tmpArr[third++] = data[mid++]; }while (left <= center) {
tmpArr[third++] = data[left++]; }// Copy the contents of the intermediate array back to the original array while (tmp <= right) {
data[tmp] = tmpArr[tmp++]; } }
shell sort

Shell Sort , Also known as decreasing incremental sort algorithm , Is a more efficient version of insert sort . Hill sort is an unstable sort algorithm .
Hill sort is based on the following two properties of insertion sort :
Insert sort is used to operate on almost ordered data , efficient , That is, the efficiency of linear sorting can be achieved ;
But insertion sort is generally inefficient , Because insert sort can only move data one bit at a time .
Take a positive integer first d1 < n, Keep everything apart d1 Put a group of records , Direct insertion sort within each group ; then d2 < d1, Repeat the above grouping and sorting operations ; until di =
1, That is, all records are put into a group for sorting .

code :
public static void shellSort(int[] array) { int i; int j; int temp; int gap = 1
;int len = array.length; while (gap < len / 3) { gap = gap * 3 + 1; } for (;
gap >0; gap /= 3) { for (i = gap; i < len; i++) { temp = array[i]; for (j = i -
gap; j >=0 && array[j] > temp; j -= gap) { array[j + gap] = array[j]; } array[j
+ gap] = temp; } } System.out.println(Arrays.toString(array) + " shellSort"); }
Search algorithm

java The commonly used search algorithms are sequential search and binary search . Sequential search may be inefficient , Binary search efficiency is high , But if the sequence is in order . The sequential search is not repeated here .

Binary search

prerequisite : Find in sorted array

The basic idea of binary search is : Firstly, the middle point of the search interval is determined : int mid = (low+upper) /
2; Then compare the value to be found with the value at the middle point : If equal , The search is successful and returns to this location . If the middle point position value is greater than the value to be checked , Then the new search interval is the left area of the middle point . If the middle point position value is less than the value to be checked , Then the new search interval is the right area of the middle point . The next search is for the new search interval .

Illustration :

raw data : int[] a={5,3,6,1,9,8,2,4,7}; Look for numbers 8;

The first step , Sort the array in ascending order using the sort method you learned earlier :int[] a={1,2,3,4,5,6,7,8,9};

Step two , Take the middle number :5 Follow 8 compare ,8 greater than 5 , Compare the array to the right of the median , Namely {6,7,8,9}

Step three : Repeat the first and second steps , Until you find the data or compare all the data .

code :
import java.util.Scanner; /* * Binary search */ public class BinarySearch { public
static void main(String[] args) { int[] arr={5,3,6,1,9,8,2,4,7}; // Print out the original array data first
System.out.println(" The original array data is as follows :"); for (int n : arr) { System.out.print(n+" "); }
System.out.println(); // First, sort the array , Bubble sort here 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]){ int temp=arr[j];
arr[j]=arr[j+1]; arr[j+1]=temp; } } } // Traverse output sorted array System.out.println(
" Bubble sorted array :"); for(int n:arr){ System.out.print(n+" "); } System.out.println();
// Line break Scanner input=new Scanner(System.in); System.out.println(" Please enter the number you want to find :"); int
num=input.nextInt();int result=binarySearch(arr, num); if(result==-1){ System.
out.println(" The number you are looking for does not exist ……"); } else{ System.out.println(" The number you are looking for exists , The position in the array is :"
+result); } }// Binary search algorithm public static int binarySearch(int[] arr,int num){ int
low=0; int upper=arr.length-1; while(low<=upper){ int mid=(upper+low)/2; if
(arr[mid]<num){ low=mid+1; } else if(arr[mid]>num){ upper=mid-1; } else return
mid; }return -1; } }

Technology
©2019-2020 Toolsou All rights reserved,
( Super detail )Eclipse Using tutorials —— use Eclipse Create first HelloWorld! Database operation 5 code implementation mysql Addition, deletion, modification and query of database What can MCU do , Do you have any interesting works made by MCU or open source hardware Go to the interview after reading this , Steady over ~~ Single linked list of primary data structure (C Language implementation )SQL Comprehensive questions Employee unit comprehensive questions Python Implementation of Hanoi Tower code VHDL——JK trigger It's over , Starting salary 30k