插入排序

插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。

算法步骤
1,将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

2,从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）


java代码实现：

package com.paixu;

public class insertionSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// 定义一个数组
		int[] insertion = { 1, 4, 5, 7, 81, 23, 4, 46, 67, 98, 64, 33, 37, 99,
				111, 23, 3, 298 };
		System.out.println("未排序的数组：\n");
		for (int m = 0; m < insertion.length; m++) {
			System.out.print(insertion[m] + "  ");
		}
		System.out.println(" ");
		int preIndex, current;
		for (int i = 1; i < insertion.length; i++) {
			preIndex = i - 1;
			current = insertion[i];
			while (preIndex >= 0 && insertion[preIndex] > current) {
				insertion[preIndex + 1] = insertion[preIndex];
				preIndex--;
			}
			insertion[preIndex + 1] = current;

			
		}
		System.out.println("排序结果：");
		for (int j = 0; j < insertion.length; j++) {
			System.out.print(insertion[j] + "  ");

		}

	}

}

未排序的数组：

1  4  5  7  81  23  4  46  67  98  64  33  37  99  111  23  3  298   
排序结果：
1  3  4  4  5  7  23  23  33  37  46  64  67  81  98  99  111  298