排序算法-插入排序

属性

        当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排序码与array[i1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置上的元素顺序后移

        直接插入排序的特性总结： 1. 元素集合越接近有序，直接插入排序算法的时间效率越高 2. 时间复杂度：O(N^2) 3. 空间复杂度：O(1)，它是一种稳定的排序算法 4. 稳定性：稳定

代码及其注释

        

public class InsertSort {// 插入排序public static void insertSort(int[]arr){//首先比较第一个元素和第二个元素之间的大小关系，所以i从1开始for(int i=1;i<arr.length;i++){//将要进行比较的数放到一个临时变量中，此时就相当于i位置现在是空的int tmp=arr[i];//遍历i前面的数据，与temp中的数据进行比较int j=i-1;for(;j>=0;j--){//要是i前面的数据比i的数据大，就说明该数据应该在i数据之前，就将该数据向前移if(arr[j]>tmp){arr[j+1]=arr[j];}//i前面的数据比i的数据小了，找到了合适的位置，就退出循环并将i的数据放到当前遍历到的j数据之前else {break;}}//这里有特殊情况，当i前面的数据都比i大时，j的取值会一直取到-1，退出循环，此时就需要将i的值放到0的位置arr[j+1]=tmp;}}
}