Java classical algorithm in detail – not to see a pity

Is learning Java you several Java programming in the classic algorithm do not miss, algorithm in Java development will play a very important role, understand these commonly used algorithms will let you in the work to achieve twice the result with half the effort!

Look today for you to sort out the classical algorithm in detail:

Insert sort

This is a good understanding of playing mahjong or poker. For example, if you have a set of cards 1, 2, 4, 7 and a 3 in your left hand, insert the card 2, 4 from right to left to verify that it is correct.

Operation process of an insert sort:

If the value of the current element is larger than the value of the element to be inserted, the element to be inserted will be moved to the position next to it; otherwise, the element to be inserted will be directly inserted to the position next to the current element, because it indicates that the final position of the insertion point has been found:

public class InsertSort { public static void sort(int[] arr) { if (arr.length >= 2) { for (int i = 1; i < arr.length; Int x = arr[I]; int x = arr[I]; int j = i - 1; While (j >= 0 &&arr [j] > x) {// When arr[j] is greater than x, move j back one bit, fill the pit arr[j + 1] = arr[j]; j--; } arr[j + 1] = x; }}}}Copy the code

Second,Selection sort

The basic idea of selective sorting is that in the process of traversing a number set, I represents the current sequence number to be sorted, and the minimum value should be found in the remaining [I… n-1], and then the minimum value found should be exchanged with the value pointed to by I. Because there is a subprocess of selecting the maximum value for each element determination, it is figuratively called selection sorting.

The following is an example:

Initial values are: [38, 17, 16, 16, 7, 31, 39, 32, 2, 11]

i = 0: [2 , 17, 16, 16, 7, 31, 39, 32, 38 , 11] (0th [38]<->8th [2])

i = 1: [2, 7 , 16, 16, 17 , 31, 39, 32, 38, 11] (1st [38]<->4th [17])

i = 2: [2, 7, 11 , 16, 17, 31, 39, 32, 38, 16 ] (2nd [11]<->9th [16])

I = 3: [2, 7, 11, 16, 17, 31, 39, 32, 38, 16]

i = 4: [2, 7, 11, 16, 16 , 31, 39, 32, 38, 17 ] (4th [17]<->9th [16])

i = 5: [2, 7, 11, 16, 16, 17 , 39, 32, 38, 31 ] (5th [31]<->9th [17])

i = 6: [2, 7, 11, 16, 16, 17, 31 , 32, 38, 39 ] (6th [39]<->9th [31])

I = 7: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39]

I = 8: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39]

I = 9: [2, 7, 11, 16, 16, 17, 31, 32, 38, 39]

By example, you can see that the selection as is gradually increasing (I), compare the number of times will be less and less, but whether or not the initial array orderly, selection sort from I to compare a choice at the end of an array, so the array of a given length, selection sort of number is fixed: 1 + 2 + 3 +… . + n = n * (n + 1) / 2, and the number of swaps depends on the order of the initial array. If the initial array order is random, the elements of the array will be swapped n times in the worst case, and 0 times in the best case (the array itself is ordered).

Code examples:

* * Selection Sorting */ SELECTION(new Sortable() { public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { int len = array.length; for (int i = 0; i < len; i++) { int selected = i; for (int j = i + 1; j < len; j++) { int compare = array[j].compareTo(array[selected]); if (compare ! = 0 && compare < 0 == ascend) { selected = j; } } exchange(array, i, selected); }}})Copy the code

Quicksort

In simple terms, set a standard value, put the value greater than this value on the right (regardless of sorting), and put the value less than this value on the left (regardless of sorting), so this is just the difference between the left and the right, no sorting, it doesn’t matter, the left and right sides repeat the process. Until it’s too late.

Code examples:

Public class QuickSort {public static void sort(int[] arr,int begin,int end) {public class QuickSort {public static void sort(int[] arr,int begin,int end) { int b = end; If (a >= b) {return; Int x = arr[a]; int x = arr[a]; // If the logic of a and B is correct --a<b, and the last value arr[b]>x, keep looking until the next value is greater than x while (a <b &&)  arr[b] >= x) { b--; } // select * from 'a' where 'b' >= 'b' where 'b' >= 'b'; Arr [a] arr[b] = arr[b]; arr[a] arr[b] = arr[b]; // sort by a++; Arr [b] while (a < b &&arr [a] <= x) {a++; } if (a < b) { arr[b] = arr[a]; // The end of the sort is moved up one bit by b--; If (a==b) arr[a] arr[a] = x; if (a= b) arr[a] = x; Sort (arr,begin,a-1); sort(arr,a+1,end); }}Copy the code

Four, bubble sort basic version

Each bubbling process starts with the first element of the sequence and then compares it to the rest in turn. Like a queue, the ratio of the sizes of two adjacent elements changes from left to right in the highest and lowest position. Finally, the highest (maximum) must come after

But that just puts the highest one behind, we have to find the second highest one, so we compare the first two, the taller one goes back, and then the second highest one falls behind

And then the third highest…

Code examples:

public class MaoPao { public static void sort(int[] arr){ for (int i = 1; i < arr.length; For (int j = 0; int j = 0; j < arr.length-1; If (arr[j] > arr[j]){int temp = arr[j]; if (arr[j] > arr[j]){int temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; } } } } }Copy the code

Five, bubble sort advanced version

Supplement and improvement, see the following test results found that ascension is not large, this is normal, because the improvement step is omitted after the success of judgment, if there is no improvement, even after the success of sorting and just array traversal, no data update, we know that reading array fast update slow, so it didn’t seem to be any better than the previous version of the improvement

In this version, two changes were made:

The first point is to add a Boolean value to determine whether the second layer of the loop has been switched. If the second layer of the loop has not been switched, it means that the rest of the loop is sorted, no longer need to recycle, directly out of the loop, the sorting is finished.

The second point is that the second loop no longer circulates to arr. Length-1, because the outer I loop is incremented once, which means that the array ends up with a big, sorted bubble. The second loop does not need to reach the last bit and can end the loop prematurely

Code examples:

@param arr */ public static void sortPlus(int[] arr){if(arr! = null && arr.length > 1){ for(int i = 0; i < arr.length - 1; I++){// initialize a Boolean flag = true; for(int j = 0; j < arr.length - i - 1 ; J ++){if(arr[j] > arr[j]){// swap int temp; temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = temp; // Change flag flag = false; } } if(flag){ break; }}}}Copy the code

Hill sort

Hill sort was born because insertion sort encountered the problem of moving too many elements when dealing with large arrays.

The idea of hill sort is to divide a large array into several smaller arrays, divided by gaps, such as the array [1,2,3,4,5,6,7,8]. If gap = 2, we can divide it into two arrays [1,3,5,7] and [2,4,6,8], and then insert and sort the arrays separately. After sorting each subarray, reduce the gap value and repeat the previous step until gap = 1, that is, insert sort for the entire array. At this point, the array is almost sorted, so the elements that need to be moved are very, very small, which solves the problem of inserting sorts that require more movement when dealing with large arrays.

For an example, see Insertion sort.

Hill sort is an improved version of insert sort, which can help improve efficiency in the case of large data volumes. When the amount of data is very small, it is recommended to use insert sort directly.

Code examples:

/** * Shell Sorting */ SHELL(new Sortable() { public <T extends Comparable<T>> void sort(T[] array, boolean ascend) { int length = array.length; int gap = 1; // use the most next to length / 3 as the first gap while (gap < length / 3) { gap = gap * 3 + 1; } while (gap >= 1) { for (int i = gap; i < length; i++) { T next = array[i]; int j = i; while (j >= gap) { int compare = array[j - gap].compareTo(next); // already find its position if (compare == 0 || compare < 0 == ascend) { break; } array[j] = array[j - gap]; j -= gap; } if (j ! = i) { array[j] = next; } } gap /= 3; }}})Copy the code

---

Incidentally in the list according to a few classic algorithm interview questions:

The first

Question: There is a pair of rabbits. From the third month after birth, they gave birth to a pair of rabbits a month. When the pups are three months old, they give birth to another pair of rabbits every month. If rabbits don’t die, what is the total number of rabbits per month?

Code demo:

Public class test01 {public static void main(String[] args) {int f1=1,f2=1,f; int M=30; System.out.println(f1); System.out.println(f2); for(int i=3; i<M; i++) { f=f2; f2=f1+f2; f1=f; System.out.println(f2); }}}Copy the code

The second

Question: Determine how many primes there are between 101 and 200, and print all primes.

Program analysis: judge the method of prime number: use a number to remove 2 respectively to SQRT (this number), if can be divisible, it shows that this number is not prime, and vice versa.

public class test02 { public static void main(String[] args) { int count=0; for(int i=101; i<200; i+=2) { boolean flag=true; for(int j=2; j<=Math.sqrt(i); j++) { if(i%j==0) { flag=false; break; } } if(flag==true) { count++; System.out.println(i); } } System.out.println(count); }}Copy the code

The third

Problem: Print out all the “daffodil numbers”, the so-called “daffodil number” is a three-digit number, the cube sum of the numbers is equal to the number itself. For example, 153 is a “daffodil number” because 153=1 ^ 3 +5 ^ 3 +3 ^ 3.

public class test03 {
    public static void main(String[] args) {
        int a,b,c;
        for(int i=101;i<1000;i++) {
            a=i%10;
            b=i/10%10;
            c=i/100;
            if(a*a*a+b*b*b+c*c*c==i)
                System.out.println(i);
            }
        }
} 
Copy the code

Fourth:

Problem: Decomposing positive integers into prime factors. For example, enter 90 and print 90=233*5.

Program analysis: To decompose the prime factors of N, first find a minimum prime number k, and then complete the following steps:

(1) If the prime number is exactly equal to N, the process of decomposing the prime factors is over and you can print it out.

(2) If n>k, but n is divisible by k, print out the value of k, quotient n by k as a new positive integer, and repeat the first step.

(3) If n cannot be divided by K, repeat the first step with K+1 as the value of K.

import java.util.Scanner; public class test04 { public static void main(String[] args) { Scanner input=new Scanner(System.in); int n=input.nextInt(); int k=2; while(n>=k) { if(n==k) { System.out.println(k); break; }else if (n%k==0) { System.out.println(k); n=n/k; }else { k++; }}}}Copy the code

Fifth:

Problem: Use conditional operators to nest this problem: students with academic scores >=90 are denoted as a, students with scores between 60 and 89 as B, and students below 60 as C.

import java.util.Scanner; public class test05 { public static void main(String[] args) { Scanner input=new Scanner(System.in); int score=input.nextInt(); char grade=score>=90? 'A':score>=60? 'B':'C'; System.out.println(grade); }}Copy the code

Sixth:

Problem: Enter a line of characters and count the number of letters, Spaces, digits, and other characters.

import java.util.Scanner; public class test07 { public static void main(String[] args) { int abccount=0; int spacecount=0; int numcount=0; int othercount=0; Scanner input=new Scanner(System.in); String toString=input.nextLine(); char [] ch=toString.toCharArray(); for(int i=0; i<ch.length; i++) { if(Character.isLetter(ch[i])) { abccount++; }else if(Character.isDigit(ch[i])) { numcount++; }else if(Character.isSpaceChar(ch[i])){ spacecount++; }else { othercount++; } } System.out.println(abccount); System.out.println(spacecount); System.out.println(numcount); System.out.println(othercount); }}Copy the code

Above all the content of this time, part of the article content excerpts with the network, data sharing era is learning for you, add a reminder

Recommended historical articles

10 Must-read Java books

Java- Programmer: The most commonly used development tool

Javase2021 has no one of the strongest learning routes

Snipe the interviewer -21 Linux — > Common commands