图解Java经典算法插入排序的原理与实现

插入排序的算法描述是一种简单直观的排序算法。其原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。本文将用Java语言实现插入排序算法并进行可视化，感兴趣的可以了解一下

一、算法介绍

插入排序，也称为直接插入排序。插入排序是简单排序中效率最好的一种，它也是学习其他高级排序的基础，比如希尔排序/快速排序，所以非常重要，而它相对于选择排序的优点就在于比较次数几乎是少了一半。

二、算法思想

每次将待排序的元素插入到已排序的序列中，直至全部插入完成。

三、算法原理

把所有元素分为两个序列，将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从未排序序列中的第一个元素开始，向已排序的序列中插入
倒序遍历已排序序列，依次和待插入的元素比较，找到一个小于或等于待插入的元素，插入到该元素后面，其余元素向后移动一位

四、动图演示

五、代码实现

核心代码

public class InsertionSort { //  插入排序 public static void sort(Comparable[] a){ for (int i = 1;i  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}