插入排序
基本思想:
1.把n个待排序的元素看成为一个有序表和一个无序表,开始时有序表只包含一个元素,无序表中包含n-1个元素,
2.排序过程中每次从无序表中取出第一个元素,她的排序码依次与有序表的排序码进行比较
3.将它插入到有序表中的适当位置,使之成为新的有序表。
首先写一个插入排序方法
public static void insertSort(int [] arr){
for (int i = 1; i <arr.length ; i++) {
//定义待插入的数
int insertVal=arr[i];
int insertIndex=i-1;//即arr[i]前面这个数的下标
/*
* 1.insertIndex>=0 保证在给insertVal找到插入位置,不越界
* 2.insertVal<arr[insertIndex]待插入的数,还没有找到插入的位置
* 3.就需要将arr[insertIndex]后移*/
while (insertIndex>=0&&insertVal<arr[insertIndex]){
arr[insertIndex+1]=arr[insertIndex];//将arr[insertIndex]向后移一位
insertIndex--;
}
/*退出while循环说明找到了插入的位置,insertIndex+1*/
arr[insertIndex+1]=insertVal;
count++;
System.out.printf("第%d轮"+Arrays.toString(arr)+"\n",count);
}
}
然后测试
public static void main(String[] args) {
int [] arr={4,2,5,6,1};
System.out.println("排序前"+Arrays.toString(arr));
insertSort(arr);
}
最后是结果图