Java数据结构与算法中的排序算法（三）插入排序法详解

 插入排序法属于内部排序法，是对欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

插入排序法的思想：

  把n各待排序的元素看成为一个有序表和一个无序表，开始时，有序表中只包含一个元素，无序表中包含n-1个元素，排序过程中每次从无需表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表的适当位置，使之成为新的有序表

排序代码如下：

   //插入排序    public static void insertsort(int[] arr) {        //定义待插入的数        int insertVal = 0;        int insertIndex = 0;          for (int i = 1; i < arr.length; i++) {            insertVal = arr[i];            insertIndex = i - 1;  //arr[1]前面哪个数的下标
            //给insertVal找到插入的位置            while (insertIndex >= 0 && insertVal < arr[insertIndex]) {  //insertIn >=0保证在给insertVal找插入位置时，不越界  如果insertVal < arr[insertIndex],说明还没有找到位置                arr[insertIndex + 1] = arr[insertIndex];                insertIndex--;
            }            //当退出while循环时，说明插入的位置找到，insertIndex+1            if (insertIndex + 1 != i) {                arr[insertIndex + 1] = insertVal;            }            //           System.out.println("第" + i + "轮插入");            //           System.out.println(Arrays.toString(arr));        }    }

举一个例子来验证：

  可以看到，假设数组中共有6个数，那么需要排序5轮，正确。

  同样，我们随即生成8000个数，存入数组，比较排序算法的运行时间：

  发现选择排序算法的时间还是比较快的。