Java sorting InsertionSort insertion sort example

Insertion sort の implementation

---

Insertion sort is like making a bet, such as double buckle. When drawing cards, take one card at a time and compare this card with the previous cards one by one. Choose where to insert this card, and play cards more smoothly after arranging the sequence. Otherwise, it would be troublesome to find them one by one. It is also not conducive to the overall situation of playing cards. Look at the picture below

Assuming that the 7 of clubs is drawn for the first time, there is no need to sort. Because there is only one

Then I drew 10 clubs . Because 10 is greater than 7, there is no need to sort.

# Then draw cards. I found that I drew 5 clubs . Don't hesitate at this time, 2 o'clock is really not a big deal. Discard decisively

# Then we compare 5 and 10. 5 is less than 10 so swap places.

Take 5 and compare with 7. 5 is smaller than 7. So swapping the positions of 5 and 7 gives us .

# At this time it is already sorted. This is the principle.

　Because it is relatively simple. Paste the code directly

// O(n^2) 最坏的情况
    // 最好的情况 O(n)
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            for (int j = i ; j > 0; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }
    
    public static void sort(Comparable[] a, int low, int hi) {
        for (int i = low; i <= hi ; i++) {
            for (int j = i ; j > low; j--) {
                if (less(a[j], a[j - 1])) 
                    exch(a, j, j - 1);
                else
                    break;
            }
        }
    }

InsertSort

##Performance Analysis

The worst case scenario is that every time The card drawn is the smallest. At this time, you need to traverse from the tail to the head every time. Time is proportional to N ^ 2

The best situation is that it has been sorted. Because it's already sorted. So the cards drawn each time do not need to be sorted. Time is proportional to N

The above is the detailed content of Java sorting InsertionSort insertion sort example. For more information, please follow other related articles on the PHP Chinese website!