1.算法原理
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴，但它的原理应该是最容易理解的了，因为只要打过扑克牌的人都应该能够秒懂。插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
插入排序和冒泡排序一样，也有一种优化算法，叫做拆半插入。
2. 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
3.代码实现
/*** 插入排序，通过while循环优化了没必要的循环，速度较快* @param arrays* @return*/public static int[] insertSort(int[] arrays){//判断数组是否为空if (arrays == null || arrays.length <= 0){return null;}//设置一个临时数组存放排序元素,不改变参数内容int[] tempArrays = Arrays.copyOf(arrays,arrays.length);for (int i=1;i<tempArrays.length;i++){// 从已经排序的序列最右边的开始比较，找到比其小的数int j =i;// 记录要插入的数据int tmp = arrays[i];while (j>0 && tmp < tempArrays[j-1]){tempArrays[j] = tempArrays[j-1];j--;}if (i != j){tempArrays[j] = tmp;}}return tempArrays;}/*** 插入排序，通过二分插入法进行优化,比普通插入法速度反而慢，不太清楚为什么* @param arrays* @return*/public static int[] insertSortBinary(int[] arrays){if (arrays == null || arrays.length <= 0){return null;}//拷贝一个临时数组，不去改变参数里的数组int []tempArrays = Arrays.copyOf(arrays,arrays.length);for (int i=1;i<tempArrays.length;i++){//将要排序的元素进行存储int temp = tempArrays[i];int left = 0;int right = i-1;int mid;while (left <= right){mid = (left + right)/2;if (temp < tempArrays[mid]){//假如要插入的数值比中间的小，更新右索引right = mid - 1;}else {//假如要插入的数值比中间的小或者等于，更新左索引left = mid +1;}}for (int j = i-1;j>= left;j--){//将要插入位置后面的数组进行移动tempArrays[j+1] = tempArrays[j];}//进行数值的插入tempArrays[left] = temp;}return tempArrays;}