当前位置：网站首页>I was beaten by the interviewer because I didn't understand the sorting

I was beaten by the interviewer because I didn't understand the sorting

2022-07-05 00:51:00 【Java geek Technology】

Because the sorting is not clear , Beaten by the interviewer _ Sorting algorithm

Today, ah fan will talk about this Java Various sorting algorithms in , Because I met an interview senior developer before , The result turned out to be a Nine Nine Multiplication Table problem , A fan heard what the reader said at that time , Instantly understand what it means , This feeling is a little deceptive , But it's actually the interviewer who wants to examine your sorting algorithm , It may also be really boring .

Sorting algorithm

What is a sorting algorithm , In fact, there is not much to say about this , Just express your meaning clearly , So called sorting , Is to make a string of records , According to the size of one or some of the keywords , An operation arranged incrementally or decrementally .

The types of sorting algorithms can be said to be relatively diversified , Right time , Efficiency of space , Different sorting algorithms have different advantages and disadvantages , Some use time for space , Some exchange space for time , Today, ah fan will list them one by one .

Bubble sort

What is bubble sorting ？

Bubble sorting is to compare two adjacent numbers in turn , Put the decimals first , Big numbers in the back .

Like a bubble , Like a bubble , Float straight up .

Bubble sorting is to compare two adjacent numbers in turn , Put the decimals first , Big numbers in the back .

In fact, the process of comparison is like this ：

The first comparison ：

First of all, compare No 1 And the first 2 Number , Put decimals first , Big numbers in the back , Then compare the 2 Number and number 3 Number , Put decimals in front , Big numbers in the back , Then compare until the end , such , The largest number is put on the last side .

The second comparison ：

First of all, compare No 1 And the first 2 Number , Put decimals first , Big numbers in the back , Then compare to the penultimate number , Then the second comparison ends , In this way, the one in the last position is the largest , Then the penultimate position is the second largest number .

Then go on like this , The third time is to take the third number , So it goes through the cycle , It must be understandable to say so , Suppose the number of sequences to be sorted is n, You need to go through n-1 round , Finish sorting . In the first round , The number of comparisons is n-1 Time , After each round, reduce 1 Time .

Let's use code to realize ：

        public static void main(int[] a) {
        
        int temp;
        
        // Need to compare n-1 round 
        
        for (int i = 0; i 
        < 
        a.length-1; 
        i++) 
        {
        

        // according to a.length-i-1, The number of comparisons per round is reduced round by round 1 Time 
        

        for 
        (int 
        j = 
        0; 
        j 
        < a.length-i-1 ; j++) {
        
                // Compare adjacent numbers , Replace if qualified 
        
                if (a[j] > a[j+1]) {
        
                    temp = a[j];
        
                    a[j] = a[j+1];
        
                    a[j+1] = temp;
        
                }
        
            }
        
        }
        
    }
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.

Insertion sort

There are many kinds of insertion sorting

Direct insert sort
Bisection insertion sort
Shell Sort

These sorting methods all belong to insert sorting ,

Let's first look at direct insertion sorting ：

The comparison process is like this , The second data of the array starts to compare forward , At the beginning, compare the second number with the one in front of him , If If they meet the conditions, let them exchange positions .

Suppose we give an array , We should sort from small to large , The array is [3,1,4,6,5,17,12,11] Now , The first step is to hold 1 and 3 Compare , If 1 Less than 3 , This is the time , Just put 1 and 3 Change the position ,[1,3,4,6,5,17,12,11] .

Next, compare the third number with the second , If it matches, it will be exchanged , But here we have to move on , Just use 4 and 3 and 1 Compare them separately , Then keep repeating like this . Until all the data are arranged , We get the result we want , Let's write a code to see what it looks like .

        public static void basal(int[] array) {
        
 //  Start with the second 
        
    if (array == null || array.length 
        < 
        2) 
        {
        

        return;
        

        }
        

        for 
        (int 
        i = 
        1; 
        i 
        < array.length; i++) {
        
            int cur = array[i];
        
            // cur  Landing sign , Prevent the minimum number to be inserted 
        
            boolean flag = false;
        
            //  Reverse traversal , Constantly shifting 
        
            for (int j = i - 1; j > -1; j--) {
        
                if (cur 
        < 
        array[j]) 
        {
        

        array[j 
        + 
        1] = 
        array[j];
        

        }else 
        {
        

        array[j 
        + 
        1] = 
        cur;
        

        flag = 
        true;
        

        break;
        

        }
        

        }
        

        if 
        (!flag) 
        {
        

        array[0] = 
        cur;
        

        }
        

        }
        

        }
        

        }
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.

Since we have said before , There are many ways to insert sorting , Then we have to talk about other insertion sorting , Then I'm looking at the differences between them , I don't know if they're right ？

Since we have just said sorting, we need to talk about array backward every time , But our previous judgment conditions can be optimized , In this way, other different insertion sorts are derived from the optimization , Next, let's take a look at the binary search insertion sort .

Binary search insert sort

The core of optimizing direct insertion sorting is ： Quickly locate the position where the current number is to be inserted . Find a given value in an ordered array , The fastest way is undoubtedly binary search , At least in a fan's heart, if you want to optimize, you must choose whether you can use the binary search method at the first time ？

Let's take a look at the code implementation , Then look at his shortcomings , Why do many people choose not to use binary search insert sorting .

        //  Use the binary search method provided by the system , Locate the insertion position 
        
      //  Unstable sequencing 
        
     public static void optimized(int[] array) {
        
         if (array == null || array.length 
        < 
        2) 
        {
        

        return;
        

        }
        

        for 
        (int 
        i = 
        1; 
        i 
        < array.length; i++) { int cur = array[i];
        
            int[] sorted = Arrays.copyOf(array, i);
        
            int index = Arrays.binarySearch(sorted,cur);             if (index 
        < 
        0) 
        {
        

        index = 
        -(index 
        + 
        1);
        

        }
        

        for 
        (int 
        j = 
        i 
        - 
        1; 
        j 
        > index - 1; j--) {
        
                array[j + 1] = array[j];
        
            }
        
            array[index] = cur;
        
         }
        
    }
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

In the Middle East: , A fan uses the system's own Arrays, Then the binary search insertion sort , Why use it like this ？ stay JDK Provided in Arrays.binarySearch(), Method requires an ordered array to be passed in To implement , Why not use this method ？

Suppose before sorting , Two numbers are equal , But after sorting , Both of them may change the order, which means that the sorting algorithm is unstable . This is what we call stability .

Since there is such an unstable sort , Should there be a stable sort ？ Yes, it is , There is , So what is a stable sort ？ Yes , Everyone is right , Bubble sort is stable sort , Because bubble sorting only changes the positions of adjacent elements when their sizes do not meet the requirements , It does not change the relative order between the same elements , So it's a stable sort algorithm .

Since we just said that there is also Hill sort in this interpolation sort , Let's take a look at Hill sort .

Shell Sort

Tell the truth , When ah fan first knew this sort , Just want to say , Is it someone named Hill who improved , result , It's a discovery , Shell Sort , Also known as （（ Reduced delta sort ）, because D.L.Shell On 1959 It was named after it was put forward in 1949 , Actually, it should be called Shell's Sort.

Hill sort is to divide the whole sequence of records to be sorted into several subsequences for direct insertion sort , To be recorded throughout the sequence “ The basic order ” when , All records are then directly inserted in sequence .

In fact, it is equivalent to a simple grouping first , The array to be sorted in steps gap Grouping , Then the elements of each group are sorted by direct insertion ; Every time gap Reduce by half , Cycle the above operations ; When gap=1 when , Using direct insertion , To complete the order .

The code implementation is like this

        public static void sort(int[] a) {
        
    int length = a.length;
        
    int h = 1;
        
    while (h 
        < 
        length 
        / 
        3) 
        h = 
        3 
        * 
        h 
        + 
        1;
        

        for 
        (; 
        h 
        >= 1; h /= 3) {
        
        for (int i = 0; i 
        < 
        a.length 
        - 
        h; 
        i 
        += 
        h) 
        {
        

        for 
        (int 
        j = 
        i 
        + 
        h; 
        j 
        > 0; j -= h) {
        
                if (a[j] 
        < 
        a[j 
        - 
        h]) 
        {
        

        int 
        temp = 
        a[j];
        

        a[j] = 
        a[j 
        - 
        h];
        

        a[j 
        - 
        h] = 
        temp;
        

        }
        

        }
        

        }
        

        }
        

        }
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.

Selection sort

Selection sort （Selection sort） It is a simple and intuitive sorting algorithm .

This is a little bit easier , Why do you say that? , It is because it directly finds the smallest or largest element in the unordered sequence , To the beginning of the collating sequence , then , Continue to find the smallest from the remaining unsorted elements （ Big ） Elements , And then at the end of the sorted sequence . And so on , Until all the elements are sorted .

In fact, it is similar to bubble sorting in idea , But it's just different .

Let's look at the code implementation ：

        public static void sort(int[] a) {
        
    for (int i = 0; i 
        < 
        a.length; 
        i++) 
        {
        

        int 
        min = 
        i;
        

        // Select the position with the lowest value to be sorted 
        

        for 
        (int 
        j = 
        i 
        + 
        1; 
        j 
        < a.length; j++) {
        
            if (a[j] 
        < 
        a[min]) 
        {
        

        min = 
        j;
        

        }
        

        }
        

        // Exchange when the minimum value is not equal to the current value 
        

        if 
        (min 
        != 
        i) 
        {
        

        int 
        temp = 
        a[i];
        

        a[i] = 
        a[min];
        

        a[min] = 
        temp;
        

        }
        

        }
        

        }
       
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.

Since ah fan has listed these sorts for you , So we come back to another question , Sort so much , How to choose , Why choose , This involves time complexity and space complexity , Or use space for time , Or use time for space .

summary

Bubble sort

Average time complexity	The best situation	The worst	Spatial complexity
O(n²)	O(n)	O(n²)	O(1)

Direct insert sort

Average time complexity	The best situation	The worst	Spatial complexity
O(n²)	O(n²)	O(n²)	O(1)

Binary search sort

Average time complexity	The best situation	The worst	Spatial complexity
O(n²)	O(n²)	O(n²)	O(1)

Shell Sort

Average time complexity	The best situation	The worst	Spatial complexity
O(nlog2 n)	O(nlog2 n)	O(nlog2 n)	O(1)

Selection sort

Average time complexity	The best situation	The worst	Spatial complexity
O(n²)	O(n²)	O(n²)	O(1)

That's all for today's sorting , Have you learned ？

Out of order ！ Out of order ！

Java There are many excellent partners in Geek technology wechat group discussing Technology , Occasionally, there are irregular information sharing and red envelope distribution ！ If you want to improve yourself , And want to make progress with excellent people , Interested friends , You can reply in the background of the official account below ： Add group .

Because the sorting is not clear , Beaten by the interviewer _ Bubble sort _02

原网站

版权声明
本文为[Java geek Technology]所创，转载请带上原文链接，感谢
https://yzsam.com/2022/02/202202141105593919.html