插入排序属于内排,就是以插入的方式来达到排序的目的
将待排序的数组看成一个有序列表和一个无序列表。刚开始时有序列表只有一个元素 arr[0],无序列表有n-2 的数据 arr[1] ~ arr[n-1]。排序开始,每次从无序列表中取出第一个元素,找到相应的位置,并将其按照插入有序列表中。
算法名称 | 平均时间复杂度 | 最好情况 | 最坏情况 | 空间复杂度 | 稳定性 |
---|---|---|---|---|---|
插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
/**
* @author shengjk1
* @date 2020/4/9
*/
public class InsertSort {
public static void main(String[] args) {
int[] arr = new int[8];
for (int i = 0; i < 8; i++) {
arr[i] = (int) (Math.random() * 80000000);
}
for (int i = 1; i < arr.length; i++) {
int insertIndex = i;
int insertValue = arr[insertIndex];
//找到相应的位置
while (insertIndex - 1 >= 0 && arr[insertIndex - 1] > insertValue) {
arr[insertIndex] = arr[insertIndex - 1];
insertIndex--;
}
//并将其按照插入有序列表中
arr[insertIndex] = insertValue;
System.out.printf("第%d次遍历 insertIndex %d arr:%s", i, insertIndex, Arrays.toString(arr));
System.out.println();
}
}
}