插入排序:

从头到尾遍历数组

将当前元素同当前元素之前的所有元素对比
如果，当前元素小于其之前元素，将当前元素向前移，直到使当前元素之前的所有元素按大小排好序

代码如下：

[html]
package com.robert.paixu;

/**
* 插入排序
* 从小到大排序
* @author Administrator
*/
public class InsertSortAlgorithm {

public static void main(String[] args){
int[] arrays = {4,6,9,2,0,1,-5,10,-20,100,20,15};
insertSort(arrays);
display(arrays);
}

/**
* 插入排序
*/
private static void insertSort(int[] arrays){
//循环遍历数组
int currentIndex = 0;
int preIndex = 0;
for(int i=0;i {
/**
* 当前元素同当前元素之前的所有元素对比
* 1,将当前元素向前移，直到使当前元素之前的所有元素按大小排好序
*/
currentIndex = i;
preIndex = i-1;
while(currentIndex!=0&&preIndex>=0){
if(arrays[currentIndex] {
swap(arrays,currentIndex,preIndex);
currentIndex--;
}
else
{
break;
}
preIndex--;
}
}
}

private static void swap(int[] arrays,int currentIndex,int preIndex){
int temp = arrays[currentIndex];
arrays[currentIndex] = arrays[preIndex];
arrays[preIndex] = temp;
}

/**
* 显示排序后的数组的值
* @param arrays
*/
private static void display(int[] arrays){

for(int i=0;i System.out.print(arrays[i]+" ");
}
}

}
在最好的情况下，即数组已经是有序的时候，插入排序的时间复杂度是O(n)

数组越有序，需要做的工作就越少

在最坏的情况下，该算法在最坏的情况下的时间复杂度为O(n^2)