一.原理
类似于洗扑克牌
1.把所有的元素分为两组，已排序的和待排序的；
2.找到待排序的组中的第一个元素，向已经排序的组中进行插入；
3.倒序遍历已经排序的元素，依次和待插入的元素进行比较，直到找到一个元素小于等于待插入元素，那么就把待
插入元素放到这个位置，其他的元素向后移动一位；
- 总结
分为待排序和已排序
首位默认已排序
每轮一个待排序
已排序>待排序则交换
已排序<=待排序则break
（将待排序的第一个元素为a[i],依次和a[i]前面的已排序元素比较，找到已排序中一个待排序的元素便是正序，则跳出循环）
刚开始时，默认第一个数为已排序。
二.java代码实现
public class insertion {
public static void sort(int[] a){
for(int i=1;i<a.length;i++){ // i为待排序的第一个数的范围，第一个默认已排序
for(int j=i;j>0;j--){ //j是已排序范围,倒序比较！
if(a[j-1]>a[j]){ //已排序的大则交换
swap(a,j,j-1);
}else{
break;//已排序的小于等于则跳出
}
}
}
}
private static void swap(int[] a,int i,int j){
int k;
k=a[i];
a[i]=a[j];
a[j]=k;
}
public static void main(String[] args) {
int[]a={4,6,8,7,9,2,10,1};
insertion.sort(a) ;
System.out.println(Arrays.toString(a));
}
}
需要注意的地方:
- 外层可视为待排序数字的可选范围，其第一个数的索引i为1，最大可以取到最后一位，所以i<a.length。
- 倒序比较，比较的是a[j-1]和a[j]，所以j-1>=0即j>0。
- 若已排序的数a比待排序数b大，则待排序数a的索引变为j-1，b数的索引变为j，即达到插入效果。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/89395.html
