Java 插入排序

插入排序是把数组分为左右两段，左侧是已经排序好的，右侧的元素都是还未进行排序的。

左侧从1个元素开始，从右侧拿出一个元素，在左侧区域中进行比较，放置到左侧都比此元素小，右侧都比此元素大的位置

依次从右侧遍历拿出所有元素放入左侧，最总右侧区域没有元素，即排序结束。

public class InsertSort {

	
	public void sort(int[] pArray) {
		if (pArray == null) {
			throw new NullPointerException();
		}
		
		int i, j;
		// 从左向右依次遍历数组，默认左侧第一个为已排序区域
		// 所以从第二个位置即 i = 1开始
		for (i = 1; i < pArray.length; i++) {
			// 数组是从左向右，从小到大排序。
			// 所以左侧大于右侧的需要移位处理。
			if (pArray[i - 1] > pArray[i]) {
				int temp = pArray[i];
				// 以排序区间从右向左
				for (j = i - 1; j >= 0 && pArray[j] > temp; j--) {
					// 所有大于temp的值都向右移动
					pArray[j + 1] = pArray[j];
				}
				// 所有左侧的都比temp小，所有右侧的都比temp大
				pArray[j + 1] = temp;
			}
		}
	}
	
}

虽然第一次循环是从i = 1开始，传入的数组也可能仅有一个元素，直接调用pArray[1] 会导致数组越界，但是for的第二个部分进行判断，所以无需针对数组长度等于1时进行特别处理。

注意：最终把值插入的地方容易写错，pArray[j + 1] = temp; 而不是pArray[j ] = temp;

测试main方法：

	public static void main(String[] args) {
		int[] arr = {3, 5, 1, 10, 0, 100, 3, 9};
		
		InsertSort insertSortSort = new InsertSort();
		insertSortSort.sort(arr);
		
		for (int i = 0; i < arr.length; i++) {
			System.out.println("value = "+ arr[i]);
		}
	}

时间复杂度：1+2+3+ ...... +（n-1) = n*(n-1)/2 = O(N平方)

最好情况：O（n）

最坏情况：O（n平方）

空间复杂度：O(1) 因为未使用辅助空间

稳定性：稳定