插入排序:
從頭到尾遍歷數組
將當前元素同當前元素之前的所有元素對比
如果，當前元素小於其之前元素，將當前元素向前移，直到使當前元素之前的所有元素按大小排好序
代碼如下：
[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<arrays.length;i++)
{
/**
* 當前元素同當前元素之前的所有元素對比
* 1,將當前元素向前移，直到使當前元素之前的所有元素按大小排好序
*/
currentIndex = i;
preIndex = i-1;
while(currentIndex!=0&&preIndex>=0){
if(arrays[currentIndex]<arrays[preIndex])
{
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<arrays.length;i++){
System.out.print(arrays[i]+" ");
}
}
}
在最好的情況下，即數組已經是有序的時候，插入排序的時間復雜度是O(n)
數組越有序，需要做的工作就越少
在最壞的情況下，該算法在最壞的情況下的時間復雜度為O(n^2)
