【Java SE】如何用Java实现插入排序

摘要：前面三期分别写了三篇简单排序的算法，今天来讲一点稍微难一点的排序算法-----插入排序。

1. 基本思想：

   1. 设n个数据已经按照顺序排列好(假定从小排到大)。
   2. 输入一个数据x，将其放在恰当的位置，使其顺序依旧从小到大。
   3. 输出已经排序完的数据。

2. 适宜人群:

   1. 有一定Java SE基础，明白Java的数据类型，数组的定义、初始化以及常用数组的方法，还有Java的循环操作。

3. 前期准备：

   1. 最好有一个开发工具比如说：eclipse或者myeclipse都可以，当然你使用DOS系统进行编译运行都可以，只不过改bug会麻烦一点。

4. 插入排序的应用范围:

   1. 适合已经排序好的数据中插入一个或多个数据。

5. 算法的优缺点：

   1. 优点：稳定，快；
   2. 缺点：比较次数不一定，比较次数越少，插入点后的数据移动越多，特别是当数据总量庞大的时候，但用链表可以解决 这个问题。

6. 算法实现：

   package liuenci.cn.package_3;
   
   public class HomeWork {
   
       public static void main(String[] args) {
   
           int a[] = { 38,65,97,76,13,27,49 };
   
           insertSort(a);
   
           for(int i:a){
   
               System.out.print(i +" ");
   
           }
   
       }
   
       public static void insertSort(int[] a) {
   
           int i, j, insertNote;
   
           for (i = 1; i < a.length; i++) {
   
               insertNote = a[i];
   
               j = i - 1;
   
               while (j >= 0 && insertNote < a[j]) {
   
                   a[j + 1] = a[j];
   
                   j--;
   
               }
   
               a[j + 1] = insertNote;
   
           }
   
       }
   
   }