插入排序就是把当前待排序的元素插入到一个已经排好序的列表里面。 一个非常形象的例子就是右手抓取一张扑克牌，并把它插入左手拿着的排好序的扑克里面。

为潮州等地区用户提供了全套网页设计制作服务，及潮州网站建设行业解决方案。主营业务为成都网站设计、网站建设、潮州网站设计，以传统方式定制建设网站，并提供域名空间备案等一条龙服务，秉承以专业、用心的态度为用户提供真诚的服务。我们深信只要达到每一位用户的要求，就会得到认可，从而选择与我们长期合作。这样，我们也可以走得更远！

         插入排序的最坏运行时间是O(n2)， 所以并不是最优的排序算法。

         如果输入数组已经是排好序的话，插入排序出现最佳情况，其运行时间是输入规模的一个线性函数。

         如果输入数组是逆序排列的，将出现最坏情况。平均情况与最坏情况一样，其时间代价是Θ(n2)。

简单例子：

public class Demo6 { 
   
  public static void main(String[] args) {  
    //定义一个整型数组  
    int[] nums = new int[]{4,3,-1,9,2,1,8,0,6};  
    //打印没有进行排序的数组  
    System.out.println("没有排序之前的结果:" + Arrays.toString(nums));  
    for(int index=0; index0 && nums[position-1] > key) {  
      nums[position] = nums[position-1];  
      position--;  
     }  
     nums[position] = key;  
    }  
    //打印排序后的结果  
    System.out.println("排序后的结果:" + Arrays.toString(nums));  
   }  
}

当前标题：java数据结构之插入排序-创新互联
转载注明：http://myzitong.com/article/copcge.html