插入排序法是一种简单直观的排序方法，原理比较容易理解，就跟我们平时打扑克一样，我们默认拿的第一张牌是有序的，然后后面依次将牌插入在该有序牌中适当的位置从而形成新的有序牌，以此达到排序效果。插入排序法的基本操作是构建有序序列，对于未排序数据，在已排序的序列中从后到前扫描，找到相应的位置便插入。
public void insertSort(int[] arr){ //从下标为1的元素开始选择合适位置插入，下标为0的只有一个元素，默认是有序的 for(int i=1;i<arr.length;i++){ //记录要插入的数据 int tmp = arr[i]; //记录要插入数据的索引 int index = i; //从已经排好序的右边序列中寻找，直到找到比要插入的数据还要小的数 for(int j=i-1;j>=0;j--){ /** * 如果找到比插入值tmp大的数，就将已经排好序的数组往后移动，并且记录下该索引j的值 * 直到找到比插入值tmp小的数，就退出循环，将数值插在这个比插入值tmp小的数的后面 * 也就是插入 */ if(tmp<arr[j]){ arr[j+1] = arr[j]; index = j; }else { break; } } //插入数据 if(index!=i){ arr[index] = tmp; } } } public void print(int[] a){ //遍历输出数组元素 for(int num:a){ System.out.print(num+" "); } } public static void main(String[] args) { int a[]={8,3,2,5,9,3,6}; new Sort().insertSort(a); new Sort().print(a); }
