插入排序算法
有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,
插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
插入算法把要排序的数组分成两部分：
第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），
而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
直接插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的纪录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的纪录插入完为止，得到一个新的有序序列.
例如,已知待排序的一组纪录是： 60,71,49,11,24,3,66
假设在排序过程中，前3个纪录已按关键码值递增的次序重新排列，构成一个有序序列： 49,60,71,11,24,3,66
之后为： 11,49,60,72,24,3,66
依次向前插入…
算法复杂度：O（n2）
算法思想：
- 当前值自当前位置向前进行比较，
- 如果比指针位置小则将指针位置元素覆盖到当前指针的下一个位置，并继续向前比较
- 直到指针位置不小于当前值，则跳出循环，将指针的下一个位置设置为当前值
/**
* 直接插入排序
* @author Naah
*
* @param > 泛型类必须继承比较接口
*/
public class InsertSort> {
/**
* 插入排序法
* @param array 数组
* @return 排序后的数组
*/
public T[] insertSort(T[] array){
//循环数组
for (int i = 0; i < array.length; i++) {
//取出当前元素做临时变量
T temp=array[i];
//创建变量
int j ;
//从该元素下标向前循环
for (j= i-1; j >= 0; j--) {
//比较两元素
//如果前面的元素大于临时变量
if (array[j].compareTo(temp)==1) {
//将前面的元素向后串一个位置
array[j+1]=array[j];
}
//如果不大于，则跳出循环
else {
break;
}
}
//将临时变量赋给最后空余的位置
array[j+1]=temp;
}
return array;
}
public static void main(String[] args) {
// TODO Auto-generated method stub
InsertSort sort=new InsertSort();
Integer[] array={4,6,2,7,8,10,24,76,132,-12,65,-6,324,-7};
array=sort.insertSort(array);
for (Integer integer : array) {
System.out.println(integer);
}
}
}
