本文正在参加「Java主题月 – Java 刷题打卡」，详情查看 活动链接

1、算法思想

1. 从第一个元素开始，该元素可以认为已经被排序

2. 取出第一个未排序元素存放在临时变量temp中，在已经排序的元素序列中从后往前扫描，逐一比较

3. 如果temp小于已排序元素，将该元素移到下个位置

4. 重复步骤3，直到找到已排序的元素小于或者等于

2、实例分析

{13,15,37,89,60,39,12,109,56,72}

第一趟： 13 {15,37,89,60,39,12,109,56,72} temp = 15

temp>13

第二趟： 13 ,15 { 37,89,60,39,12,109,56,72} temp = 37

temp>15 temp>13

第三趟： 13，15 ，37 {89,60,39,12,109,56,72} temp = 89

temp>37 temp>15 temp>13

第三趟： 13，15 ，37 ，89 {60,39,12,109,56,72} temp =60

temp< 89：60<->89 13，15 ，37 ， 60，89 {39,12,109,56,72}

temp>37 temp>15 temp>13

第四趟： 13，15 ，37 ， 60，89 {39,12,109,56,72} temp = 39

temp<89： 39<->89 13，15 ，37 ， 60，39，89 {12,109,56,72}

temp<60 ： 39<->60 13，15 ，37 ， 39，60，89 {12,109,56,72}

temp>37 temp>15 temp >13

第五趟： 13，15 ，37 ， 39，60，89 {12,109,56,72} temp = 12

temp<89 ：12<->89 13，15 ，37 ，39，60， 12，89 {109,56,72}

temp<60：12<->60 13，15 ，37 ，39，12，60，89 {109,56,72}

temp<39 ：12<->39 13，15 ，37 ，12，39，60，89 {109,56,72}

temp<37 ：12<->37 13，15 ，12 ，37 ，39，60，89 {109,56,72}

temp<15： 12<->15 13，12，15 ，37 ，39，60，89 {109,56,72}

temp<13 ：12<->13 12，13，15 ，37 ，39，60，89 {109,56,72}

第六趟： 12，13，15 ，37 ，39，60，89 {109,56,72} temp = 109

……

3、算法代码

import java.util.Arrays;

/**
 * 插入排序
 * @author xcbeyond
 *
 */
public class InsertSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		a = insertSort(a);
		String s = Arrays.toString(a);
		System.out.println(s);
	}
	
	public static int[] insertSort(int[] ary){
		for(int i = 1;i < ary.length;i++){
			int temp = ary[i];
			int j;
			for(j = i-1;j>=0 && temp < ary[j];j--){
				ary[j+1] = ary[j];
			}
			ary[j+1] = temp;
		}
		
		return ary;
	}
}
复制代码

另一种（易于理解）：

import java.util.Arrays;

/**
 * 插入排序
 * @author xcbeyond
 *
 */
public class InsertSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] ={13,15,37,89,60,39,12,109,56,72} ;
		a = insertSort(a);
		String s = Arrays.toString(a);
		System.out.println(s);
	}
	
	public static int[] insertSort(int[] ary){
		for(int i = 1;i < ary.length;i++){
			int temp = ary[i];
			int j;
			for(j = i-1;j>=0;j--){
				if(temp < ary[j]){
					ary[j+1] = ary[j];
				}
				else
					break; //找到插入位置
			}
			ary[j+1] = temp;
		}
		
		return ary;
	}
}
复制代码