插入排序

1、插入排序

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

2、时间复杂度

最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)

3、动态演示

Image text

4、算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
package sort;

public class InsertionSort {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int [] a= {99,45,67,12,84,59,32};
		insertionSort(a);
		printArr(a);
	}
	
	public static void insertionSort(int [] a) {
		int cur;//记录即将插入的当前值
		for(int i=0;i<a.length-1;i++) {//比较a.length-1趟
			int index=i;//记录有序数组的最后一位坐标
			cur=a[i+1];
			
			while(index>=0 && cur<a[index]) {//当前值小于有序数组中的值时
				a[index+1]=a[index];//记录后移
				index--;
			}
			
			//当前值不小于前一个值时，把当前值赋给index+1
			a[index+1]=cur;
		}
	}
	
	public static void printArr(int [] a) {
		for(int i=0;i<a.length;i++) {
			System.out.print(a[i]+" ");
		}
	}
}