插入排序,也称为直接插入排序。插入排序是简单排序中效率最好的一种,它也是学习其他高级排序的基础,比如希尔排序/快速排序,所以非常重要,而它相对于选择排序的优点就在于比较次数几乎是少了一半。
每次将待排序的元素插入到已排序的序列中,直至全部插入完成。
核心代码
public class InsertionSort { // 插入排序 public static void sort(Comparable[] a){ for (int i = 1;i < a.length;i++){ for (int j = i;j > 0;j--){ //比较索引j处的值与索引j-1处的值,如果j-1索引处的值大,则交换数据,反之,则找到了合适的位置,退出循环 if (greater(a[j - 1],a[j])){ swap(a,j - 1,j); }else{ break; } } } } //比较 v 是否大于 w public static boolean greater(Comparable v,Comparable w){ return v.compareTo(w) > 0; } //数组元素交换位置 private static void swap(Comparable[] a,int i,int j){ Comparable temp; temp = a[i]; a[i] = a[j]; a[j] = temp; } }
方法调用
public class InsertionSortTest { public static void main(String[] args) { Integer[] arr = {3,44,38,5,47,15,36,26,27}; InsertionSort.sort(arr); System.out.println(Arrays.toString(arr)); } } //排序前:{3,44,38,5,47,15,36,26,27} //排序后:{3,5,15,26,27,36,38,44,47}
当待排序的 n 个元素是正序排列时,是排序的最佳情况,只需要比较(n-1)次,时间复杂度是O(n);最坏的情况是该序列是反序排列,此时就需要比较n(n-1)/2次,时间复杂度为 O(n²)。
插入排序的平均时间复杂度为 O(n²)
插入排序的空间复杂度为常数阶O(1)