1, Briefly list 14 common algorithms in Java
Serial number | abbreviation | english | brief introduction |
1 | Binary search method | Binary Search | Binary search requires that the linear table must adopt the sequential storage structure, and the elements in the table are arranged in order by keywords. |
2 | Bubble sort algorithm | Bubble Sort | It repeatedly visits the element column to be sorted and compares two adjacent elements in turn element , if the order (e.g. from big to small, from Z to A) is wrong, exchange them. The work of visiting elements is repeated until no adjacent elements need to be exchanged, that is, the element column has been sorted. |
3 | Insertion sorting algorithm | Insertion sort |
By constructing an ordered sequence, for unordered data, scan from back to front in the sorted sequence, find the corresponding position and insert it.
|
4 | Quick sorting algorithm | Quick sort | An improvement of bubbling algorithm. It refers to dividing the data to be sorted into two independent parts through one-time sorting. All the data in one part is smaller than all the data in the other part, and then quickly sort the two parts of data according to this method. The whole sorting process can be carried out recursively, so that the whole data becomes an ordered sequence. |
5 | Hill sorting algorithm | Shell's Sort | Hill sort is a kind of insertion sort, also known as "reduced incremental sort", which is a more efficient improved version of direct insertion sort algorithm. Hill sorting is an unstable sorting algorithm |
6 | Merge sort algorithm | Merge Sort | Merge sort is an effective and stable sort algorithm based on merge operation. This algorithm is a very typical application of divide and conquer method. Merge the ordered subsequences to obtain a completely ordered sequence; That is, each subsequence is ordered first, and then the subsequence segments are ordered. If two ordered tables are merged into one, it is called two-way merging. |
7 | Bucket sorting algorithm | Bucket sort | Bucket sorting is also called box sorting. The working principle is to divide the array into a limited number of buckets. Each bucket is sorted individually (it is possible to use another sorting algorithm or continue to use bucket sorting recursively). Bucket sorting is an inductive result of pigeon nest sorting. Bucket sorting uses linear time when the values in the array to be sorted are evenly distributed( Θ (n)). However, bucket sorting is not a comparative sorting. It is not affected by the lower limit of O(n log n). |
8 | Cardinality sorting algorithm | Radix Sort | Cardinal sort belongs to "distribution sort", also known as "bucket sort" or bin sort. As the name suggests, it allocates the elements to be sorted to some "buckets" through some information of key values, so as to achieve the function of sorting. Cardinal sort belongs to stable sort, and its time complexity is O (nlog(r)m), where r is the cardinality adopted and M is the number of heaps, In some cases, the efficiency of cardinal ranking method is higher than that of other stable ranking methods. |
9 | Pruning algorithm | pruning algorithms | In the optimization of search algorithm, pruning is to avoid some unnecessary traversal process through some judgment. In image, it is to cut some "branches" in the search tree, so it is called pruning. The core problem of application pruning optimization is to design pruning judgment method, that is, to determine which branches should be abandoned and which branches should be retained. |
10 | Backtracking algorithm | Backtracking | Backtracking algorithm is actually a search attempt process similar to enumeration. It is mainly to find the solution of the problem in the search attempt process. When it is found that the solution conditions are not met, it will "backtrack" back and try other paths. |
11 | Shortest path algorithm | The path from a vertex to another vertex along the edge of the graph is called the shortest path. There are the following algorithms to solve the shortest path problem: Dijkstra algorithm, Bellman Ford algorithm, Floyd algorithm and SPFA algorithm. | |
12 | Maximum subarray algorithm | ||
13 | Longest common suborder algorithm | ||
14 | Minimum spanning tree algorithm |
2, Specific introduction
1. Binary search method
(1) Algorithm principle:
/** * Binary search * @param srcArray Source array * @param des Target element * @return If it is found, the index position is returned, and if it is not found, - 1 is returned */ public static int binarySearch(int[] srcArray, int des) { //Define initial minimum and maximum indexes int start = 0; int end = srcArray.length - 1; //Make sure that there are no duplicate lookups and out of bounds while (start <= end) { //Calculate the intermediate index value > > > logical right shift, that is, int middle = (end + start)/2 int middle = (end + start)>>>1 ;//Prevent overflow if (des == srcArray[middle]) { return middle; //Lower limit of judgment } else if (des < srcArray[middle]) { end = middle - 1; //Upper limit of judgment } else { start = middle + 1; } } //If not, - 1 is returned return -1; }
2. Bubble sorting algorithm
(1) Algorithm principle:
Compare adjacent elements. If the first one is bigger than the second, exchange them.
Do the same for each pair of adjacent elements, from the first pair at the beginning to the last pair at the end. At this point, the last element should be the largest number.
Repeat the above steps for all elements except the last one.
Continue to repeat the above steps for fewer and fewer elements at a time until no pair of numbers need to be compared.
(2) Code example:
public static void bubbleSort(int arr[]) { 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; } } } }
public static void bubbleSort2(int[] a, int n) { int i, j; for (i = 0; i < n; i++) {//Indicates n sorting processes. for (j = 1; j < n - i; j++) { if (a[j - 1] > a[j]) {//If the preceding number is greater than the following number, it will be exchanged //Exchange a[j-1] and a[j] int temp; temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; } } } }
3. Insertion sorting algorithm
(1) Concept: by constructing an ordered sequence, for unordered data, scan from back to front in the sorted sequence, find the corresponding position and insert it.
(2) A popular metaphor:
Insertion sorting is similar to sorting out playing cards when fighting landlords. When touching a card for the first time, the left hand is empty. After that, every time you touch a card and insert it into the card on the left hand, you will compare this card with the cards in order in the left hand from right to left to confirm the position of this card.
public static void insertionSort(int arr[]) { for (int i = 1; i < arr.length; i++) { //Number of inserts int insertVal = arr[i]; //Position inserted (prepare to compare with the previous number) int index = i - 1; //If the number inserted is smaller than the number inserted while (index >= 0 && insertVal < arr[index]) { //Will move arr[index] backward arr[index + 1] = arr[index]; //Move the index forward index--; } //Put the inserted number in the right place arr[index + 1] = insertVal; } }
4. Quick sorting algorithm
(1) Concept: quick sort refers to dividing the data to be sorted into two independent parts through one-time sorting. All the data in one part is smaller than all the data in the other part, and then quickly sort the two parts of data according to this method. The whole sorting process can be carried out recursively, so that the whole data becomes an ordered sequence.
(2) Quick sort process diagram:
Select a key value as the reference value. Those smaller than the benchmark value are in the left sequence (generally disordered), and those larger than the benchmark value are in the right sequence (generally disordered).
——Pictures from the Internet
(3) Code example:
/** * Quick sort * * @param arr Array to be sorted * @param start Minimum index of array: 0 * @param end Maximum index of array: arr.length - 1 * @return Sorted array */ public static int[] quickSort(int arr[], int start, int end) { int pivot = arr[start]; int i = start; int j = end; while (i < j) { while ((i < j) && (arr[j] > pivot)) { j--; } while ((i < j) && (arr[i] < pivot)) { i++; } if ((arr[i] == arr[j]) && (i < j)) { i++; } else { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } } if (i - 1 > start) arr = quickSort(arr, start, i - 1); if (j + 1 < end) arr = quickSort(arr, j + 1, end); return (arr); }
/** * Quick sort (no return value) * @param a Array to be sorted * @param low Minimum index of array: 0 * @param high Maximum index of array: arr.length - 1 */ public static void quickSort2(int[] a, int low, int high) { int start = low; int end = high; int key = a[low]; while (end > start) { //Compare from back to front while (end > start && a[end] >= key) //If there is nothing smaller than the key value, compare the next one until there is an exchange position smaller than the key value, and then compare from front to back end--; if (a[end] <= key) { int temp = a[end]; a[end] = a[start]; a[start] = temp; } //Compare from front to back while (end > start && a[start] <= key) //If there is no one larger than the key value, compare the next one until there is an exchange position larger than the key value start++; if (a[start] >= key) { int temp = a[start]; a[start] = a[end]; a[end] = temp; } //At this time, the first cycle comparison is over, and the position of the key value has been determined. The values on the left are smaller than the key values, and the values on the right are larger than the key values, but the order of the two sides may be different. Make the following recursive call } //recursion if (start > low) quickSort2(a, low, start - 1);//Left sequence. First index position to key index - 1 if (end < high) quickSort2(a, end + 1, high);//Right sequence. From key index + 1 to last }
5. Hill sorting algorithm
(1) Basic idea: first divide the whole record sequence to be sorted into several subsequences for direct insertion sorting. When the records in the whole sequence are "basically orderly", then directly insert and sort all records in turn.
(2) Code example:
/** * Shell Sort * @param a */ private static void shellSort(int[] a) { int dk = a.length / 2; while (dk >= 1) { //It is similar to insert sort, except that the increment of insert sort is 1, where the increment is dk. Just replace 1 with dk for (int i = dk; i < a.length; i++) { if (a[i] < a[i - dk]) { int j; int x = a[i];//x is the element to be inserted a[i] = a[i - dk]; for (j = i - dk; j >= 0 && x < a[j]; j = j - dk) { //Through the cycle, move back one by one to find the position to be inserted. a[j + dk] = a[j]; } a[j + dk] = x;//insert } } dk = dk / 2; } }
6. Merge sort algorithm
(1) Basic idea: Merge sorting method is to combine two (or more) ordered tables into a new ordered table, that is, the sequence to be sorted is divided into several subsequences, and each subsequence is ordered. Then the ordered subsequences are combined into an overall ordered sequence.
(2) Merge sort: it is an effective and stable sort algorithm based on merge operation.
What is merge operation?
Merging operation, also known as merging algorithm, refers to the method of merging two sequential sequences into one sequential sequence. as With sequence{6,202,100,301,38,8,1} Initial state: 6,202,100,301,38,8,1 After the first merger:{6,202},{100,301},{8,38},{1},Comparison times: 3; After the second merger:{6,100,202,301},{1,8,38},Comparison times: 4; After the third merger:{1,6,8,38,100,202,301},Comparison times: 4; The total number of comparisons is: 3+4+4=11; The number in reverse order is 14;
(2) Code example:
/** * Merge sort * @param nums Array to be sorted * @param l Start index: 0 * @param h Maximum index: num length - 1 * @return Sorted array */ public static int[] mergeSort(int[] nums, int l, int h) { if (l == h) return new int[]{nums[l]}; int mid = l + (h - l) / 2; int[] leftArr = mergeSort(nums, l, mid); //Left ordered array int[] rightArr = mergeSort(nums, mid + 1, h); //Right ordered array int[] newNum = new int[leftArr.length + rightArr.length]; //New ordered array int m = 0, i = 0, j = 0; while (i < leftArr.length && j < rightArr.length) { newNum[m++] = leftArr[i] <= rightArr[j] ? leftArr[i++] : rightArr[j++]; } while (i < leftArr.length) newNum[m++] = leftArr[i++]; while (j < rightArr.length) newNum[m++] = rightArr[j++]; return newNum; }
7. Bucket sorting algorithm
(1) Basic idea: divide the array arr into n sub intervals (buckets) of the same size, sort each sub interval separately, and finally merge. Counting sorting is a special case of bucket sorting, which can be regarded as the case where there is only one element in each bucket.
(2) Sorting process:
- Find the maximum value max and minimum value min in the array to be sorted
- We use the dynamic array ArrayList as the bucket, and the elements in the bucket are also stored in ArrayList. The number of barrels is (maxmin)/arr.length+1
- Traverse the array arr and calculate the bucket of each element arr[i]
- Each bucket is sorted separately
(3) Code example:
/** * Bucket sorting * * @param data Array to be sorted */ public static void bucketSort(int data[]){ int n = data.length; int bask[][] = new int[10][n]; int index[] = new int[10]; int max = Integer.MIN_VALUE; for (int i = 0; i < n; i++) { max = max > (Integer.toString(data[i]).length()) ? max : (Integer.toString(data[i]).length()); } String str; for (int i = max - 1; i >= 0; i--) { for (int j = 0; j < n; j++) { str = ""; if (Integer.toString(data[j]).length() < max) { for (int k = 0; k < max - Integer.toString(data[j]).length(); k++) str += "0"; } str += Integer.toString(data[j]); bask[str.charAt(i) - '0'][index[str.charAt(i) - '0']++] = data[j]; } int pos = 0; for (int j = 0; j < 10; j++) { for (int k = 0; k < index[j]; k++) { data[pos++] = bask[j][k]; } } for (int x = 0; x < 10; x++) index[x] = 0; } }
8. Cardinality sorting algorithm
(1) Basic idea: cut the integer into different numbers according to the number of digits, and then compare them according to each number of digits.
(2) Sorting process: unify all values to be compared (positive integers) into the same digit length, and fill zero in front of the shorter digit. Then, start from the lowest order and sort once in turn. In this way, the sequence will become an ordered sequence from the lowest order to the highest order.
(3) Code example:
/** * Cardinality sort * @param number Array to be sorted * @param d Indicates the maximum number of digits */ public static void sort(int[] number, int d) { int k = 0; int n = 1; int m = 1; //Which bit is the sorting basis of control key values int[][] temp = new int[10][number.length]; //The first dimension of the array represents the possible remainder 0-9 int[] order = new int[10]; //The array order[i] is used to represent the number of I bits while (m <= d) { for (int i = 0; i < number.length; i++) { int lsd = ((number[i] / n) % 10); temp[lsd][order[lsd]] = number[i]; order[lsd]++; } for (int i = 0; i < 10; i++) { if (order[i] != 0) for (int j = 0; j < order[i]; j++) { number[k] = temp[i][j]; k++; } order[i] = 0; } n *= 10; k = 0; m++; } }