排序算法（二） 插入排序
插入排序:
从头到尾遍历数组
将当前元素同当前元素之前的所有元素对比
如果，当前元素小于其之前元素，将当前元素向前移，直到使当前元素之前的所有元素按大小排好序
代码如下：
[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)
补充：软件开发 , C语言 ,
