算法基础之插入排序

1、插入排序基本思想

插入排序的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。(类似与打牌时自己按顺序整理牌面时

2、代码实现

public class Test {public static void main(String[] args) {int [] arr = {3,5,2,9,8,7,4,1,6};System.out.println("插入排序后的数组："+Arrays.toString(insertNum(arr)));}public static int[] insertNum(int[] arr) {//判断数组是否合法if (arr == null || arr.length <= 0) {return null;}//默认数组的第一个元素已经是排序好的数组，所以i从数组的第二位开始取；for (int i = 1; i < arr.length; i++) {//取未排序数组的头元素int temp = arr[i];//j用于保存排序好的数组的尾元素int j;//从尾元素开始在排序好的数组中向前遍历for(j=i-1;j>=0;j--) {//从小到大排序的话，判断temp是否小于已排序好的元素的值，如果小于说明还要向前遍历；if(temp < arr[j]) {arr[j+1]=arr[j];}else {//发现temp大于已排序好的arr[j]的，说明要插在此元素的后一位，break跳出for循环；break;}}//将排序的元素插在arr[j]的后一位arr[j+1]arr[j+1]=temp;}return arr;}}

结果如图：