Direct insertion sort - [common sort method (1/8)]

Catalog

1、 Ideas

2、 demonstration

3、 attribute

4、 Original code

---

1、 Ideas

1、 We regard the first number as an order , Then there is the unordered region

2、 from 1 The subscripts are compared with the previous ordered parts in turn , Stop until it is less than the element or the comparison has been completed

3、 Insert the element to the stop position

2、 demonstration

3、 attribute

1、 Time complexity

It is best to O（n） The sequence of numbers to be arranged has been orderly .

The worst is O（n^2） Sequence to be arranged in reverse order

2、 Spatial complexity

The space complexity is O（1）, No new series created

3、 stability

Stable

4、 Original code

public class TestDemo1 {
    public static void insertSort(int[] nums){
        for (int i = 1; i < nums.length; i++) {
            int tmp=nums[i];
            int j = i - 1;
            for (; j >= 0 ; j--) {
                if(nums[j]>tmp){// If you add the equal sign, it becomes unstable 
                    nums[j+1]=nums[j];
                }else{
                    break;
                }
            }
            nums[j+1]=tmp;
        }
    }

    public static void main(String[] args) {
        int[] nums={23,6,5,34,38,3,32,48};
        insertSort(nums);
        System.out.println(Arrays.toString(nums));
    }
}