直接插入排序——【常见排序法(1/8)】

目录

1、思路

2、演示

3、 属性

4、原码

---

1、思路

1、我们把第一个数当成有序，后面的就是无序区域

2、从1下标开始依次与前面有序部分相比较，直到小于该元素或是已经比较完停止

3、插入该元素到停止时的位置

2、演示

3、 属性

1、时间复杂度

最好是O（n）待排数列已经有序。

最差是O（n^2）待排数列逆序

2、空间复杂度

空间复杂度是O（1），没有创建新的数列

3、稳定性

稳定

4、原码

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){//如果加入等号之后就不稳定
                    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));
    }
}