直接插入排序（Straight Insertion Sort）是一种最简单的排序方法，其基本操作是将一条记录插入到已排好的有序表中，从而得到一个新的、记录数量增1的有序表。
package paixu;
import java.util.Arrays;
public class InsertSort {
public static int[] insertSort(int[] array){
for(int i=1;i=0 && temp
接插入排序（straight insertion sort），有时也简称为插入排序（insertion sort），是减治法的一种典型应用。其基本思想如下：
- 对于一个数组A[0,n]的排序问题，假设认为数组在A[0,n-1]排序的问题已经解决了。
- 考虑A[n]的值，从右向左扫描有序数组A[0,n-1]，直到第一个小于等于A[n]的元素，将A[n]插在这个元素的后面。
直接插入排序的优化
主要是简化找到A[n]在A[0,n-1]何处插入的过程
- 设置哨兵位
- 将上次插入的位置设置成哨兵位，新插入的数据先与哨兵位比较，如果新数据需要放到哨兵前面，那么哨兵以及后面的全部都要后移，反之则从后向前一一寻找应该插入的位置。
- 二分查找法
- 新插入的数据直接用二分法查找要插入的位置，在大数据量下更加快捷，但是会破坏稳定性。
