Personal blog portal

Algorithm diagram

Insert the ith (range 0 to length) number to the appropriate position in the ordered queue

Assume that the array length n, I (representing the length of an ordered array) = 0

1. I take the I +1 number,insertTo the appropriate position in an ordered array of length I
2. i+1
3. Repeat 1~2 until I = n

implementation

        int n = array.length;

        for (int i = 0; i < n - 1; i++) {
            int waitToInsert = array[i + 1];
            int pos = i + 1;
            while (pos > 0 && waitToInsert < array[pos - 1]) {
                // swap
                array[pos] = array[pos - 1];
                pos--;
            }
            array[pos] = waitToInsert;
        }
Copy the code

Time complexity

O(n) ~ O(n^2)

Best: The array is ordered and only needs to be traversed once

f(n) = n = O(n)

Worst: Arrays are messy

f(n) = n (n-1) / 2 = O(n^2)

Spatial complexity

O(1) doesn’t use any extra space