今天记录下关于：直接插入排序一些理解和心得。
主要分为以下几个方面分享
- 直接插入排序的思想
- 实现方式
- 时间复杂度
直接插入排序的思想
当前位置:
1:当前位置是从下标为“1”处开始的。之所以不从0开始是因为，0前边至0位置的数只有array[0]，就它自己肯定是已经排好序的。所以只需要从1处开始。
2:每次循环递增“+1”。
排序思想：
定义:将一个记录插入到已经排序好的有序表中，从而得到一个新的、记录数量增1的有序表。
理解:
1:给定一个具有n位数据的数组，从 当前位置开始 至 1位置，依次与 前一位 进行 两两比较，如果当前值小(大)则交换2者的值。
2:重复n-1次上述操作，直至该序列中所有数据满足降(升)序为止。
实现方式
public static void main(String[] args){
Integer[] array = Util.createRandomArray(100, 10);
Integer[] array2 = Arrays.copyOf(array, array.length);
Integer[] array3 = Arrays.copyOf(array, array.length);
System.out.println("Arrays:" + Arrays.toString(array) + "------------------------------------");
insertSort2(array2);
Util.print(array2, "InsertSort2");
System.out.println("------------------------------------");
Util.test(array3);
Util.print(array3, "对数器");
}
private static void insertSort2(Integer[] source){
Util.checkSrc(source);
for(int i = 1; i < source.length; i++){ //n-1次循环
for(int j = i; j >= 1; j--){ //swap循环。记录当前位置
if(source[j] < source[j -1]){ //如果当前位置比前一位要小,则执行swap操作。
int temp = source[j - 1];
source[j - 1] = source[j];
source[j] = temp;
}
}
}
}
log:
Arrays:[45, 99, 39, 93, 71, 92, 68, 34, 91, 59]-----------------
InsertSort2:34---39---45---59---68---71---91---92---93---99
----------------------------------------------------------------
对数器:34---39---45---59---68---71---91---92---93---99
时间复杂度
时间复杂度:
结论:O(n^2)
分析:假如有n=5个数要排序，总共需要执行n-1=4次循环操作
第1次：需要比较 1次
第2次：需要比较 2次
第3次：需要比较 3次
第4次：需要比较 4次
总共执行的次数为：1 + 2 + ... + n-2 + n-1===>n^2/2，所以该排序的时间复杂度为:O(n^2)
空间复杂度:
1:O(1)
2:不需要额外申请内存
