上手难度:★☆
算法复杂度:O(n^2),但在数组近乎有序的情况下,插入排序的性能相对比较高,甚至比O(nlogn)还要高

排序思想:
两层循环
第一层循环从1到arr.length,前闭后开
最开始记录arr[i]的值为temp,也就是红色标记块
然后再以i为最大值进行倒序遍历
将temp与arr[j-1]进行比较不断往前挪动,挪动条件是小于前面的值,直到挪到挪不动的位置,就将temp放到这个位置
代码实现:
public class InsertSort {
public static void insertSort(int[] arr) {
for(int i = 1; i < arr.length; i++){
int temp = arr[i];//使用temp记录i对应位置的值
int j;
for(j = i; j > 0 && temp < arr[j - 1]; j--){
//每次与j前面的数进行比较,如果小于前面的值,就让arr[j]等于前一位的值,
//由于temp记录了arr[i],最开始的j等于i,因此起初的值不会丢失
arr[j] = arr[j - 1];//接收前一个元素的值
}//从逻辑上来说,这里是将temp的值在小于arr[j-1]时,往前挪动
arr[j] = temp;//到这一步,j自减到了temp>arr[j-1]的位置,
//由于j的值在循环过程中已经被j+1接收了,因此让arr[j] = temp就完成了交换
}
}
public static void main(String[] args) {
int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};
insertSort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}
运行结果

优点:
第二层循环由于是从i开始进行倒序循环,循环不用每次都完整循环,提高了效率,在面对一个近乎有序数组时,内层循环甚至只需要循环一次就能完成,例如 1 2 3 4这种,内层循环只需要循环一次即可,算法复杂度最高效的时候接近O(n)。
网友评论