直接插入排序

原理

首先,我们将数组中的数据分为两个区间,已排序区间和未排序区间.初始已排序区间只有一个元素,就是数组的第一个元素.插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并 保证已排序区间数据一直有序.重复这个过程,直到未排序区间中元素为空,算法结束.

示例

6 3 2 5 4 1 [] 1 2 3 4 5 6 插入3 36 插入2 6>2 366 2>2 336 236 插入5 6>5 2366 3<5 2356 2356 插入4 6>4 23566 5>4 23556 3<4 23456 23456 插入1 6>1 234566 5>1 234556 4>1 234456 3>1 233456 2>1 223456 123456

代码

public static void main(String[] args){ int[] arr={6,3,2,5,4,1}; for (int i = 1; i < arr.length; i++) { int insert=arr[i]; System.out.println("要插入的数:"+insert); int j=i-1; for (; j >= 0; j--) { if(arr[j]>insert) { arr[j+1]= arr[j]; }else { break; } } arr[j+1]=insert; System.out.println(Arrays.toString(arr)); } }

插入排序是原地排序算法吗?

从实现过程可以很明显地看出,插入排序算法的运行并不需要额外的存储空间,所以空间复杂度是 O(1),也就是说,这是一个原地排序算法.

插入排序是稳定的排序算法吗?

在插入排序中,对于值相同的元素,我们可以选择将后面出现的元素,插入到前面出现元素的后面,这样就可以保持原有的前后顺序不变,所以插入排序是稳定的排序算法.

插入排序的时间复杂度是多少?

O(n²)