This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

One, foreword

Insertion sort: is a simple and intuitive sorting algorithm

This algorithm divides the array into ordered and unordered regions. Each time, one element is removed from the unordered region and inserted into the correct position of the ordered region, so that the ordered region remains in order. Repeat this until the entire array is in order.

It’s like grabbing a card and inserting it into the right position every time you catch a row.

Ju Li, the GIF is as follows:





Two, knowledge points

Knowledge points, as follows:

  1. Time complexity
  2. The reverse of
  3. Implementation: Simple implementation

(1) Time complexity

  • Best case: Order, time complexity O(N)

  • Worst case: Reverse order, time complexity O(N ^ 2)

  • Stability: Stable.

    For example, the original array {4, 1, 4}

    Unstable: The second 4 is ranked before the first 4 in the sorting process.

General sorting diagram, as shown in figure:


(2)

If arr[I] > A [j] for subscript I < j, (I, j) is an inversion pair.

For example, sequence{34, 8, 64, 51, 32, 21}How many inversions are there?

Nine: (34, 8), (34, 32), (34, 21), (64, 51), (64, 32), (64, 21), (51, 32), (51, 21), (32, 21)Copy the code

Obtained theorem:

  • Theorem: ArbitraryNA sequence of different elements has an average ofN(N-1)/4A reverse order to
  • Theorem: The average time complexity of any algorithm that sorts only by swapping two adjacent elements isO(N^2)

So what’s the use of reverse pairs?

  1. It’s the number of swaps you have to make.

  2. It provides the basis for improving the efficiency of the algorithm

In order to improve the efficiency of the algorithm, it is necessary to:

  1. It cancels out more than one inversion pair at a time

  2. Swap two elements far apart at a time


(3) implementation

Pick up a card, place it at the end of the line, then compare the previous card until it is the same size (in reverse order), jump out of the loop, and then set the card you get.

The code is as follows:

public class InsertSort {

    // Time: O(n^2), Space: O(1)
    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) return;
        for (int i = 1; i < arr.length; ++i) {
            int cur = arr[i];
            int j = i - 1;
            while (j >= 0 && arr[j] > cur) {
                arr[j+1] = arr[j];
                --j;
            }
            arr[j+1] = cur; }}}Copy the code