讲完了冒泡排序，选择排序，以及他们的升级版之后，现在我们要来讲跟他们同为三大排序的插入排序了。
插入排序：
插入排序是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到插入排序了。
基本思想：
插入排序首先将要排序的数组分成两部分。
第一部分：这个数组除待插入的元素以外的所有元素。
第二部分：待插入的所有元素。
然后在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
分类：
插入排序细分下来大致为以下几类：
1.直接插入排序：
每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。
代码如下：
public static void main(String[] args) { //定义一个长度为10的数组 int[] a = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; int i,j; long startTime = System.nanoTime(); // 获取排序开始时间 for( i=1;i<a.length;i++) { int temp=a[i]; for( j = i-1;j>=0&&temp<a[j];j--) { a[j+1]=a[j]; } a[j+1]=temp; } long endTime = System.nanoTime(); // 获取排序结束时间 System.out.println("排序結果:" + Arrays.toString(a)); System.out.println("程序运行时间： " + (endTime - startTime) + "ns"); }
打印结果：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：1800ns
2.二分插入排序（又称折半插入排序）：
直接插入需要将有序数据一个个进行查找，效率较慢，二分插入的中心思想就是使用二分查找法在有序区间进行查找，减少查找量。
代码如下：
public static void main(String[] args) { //定义一个长度为10的数组 int[] arr = { 1, 3, 4, 2, 6, 7, 8, 0, 5 }; long startTime = System.nanoTime(); // 获取排序开始时间 for(int i=1;i<=arr.length-1;i++) { if(arr[i]<arr[i-1]) { int temp=arr[i]; int low=0; int hight=i-1; while(low<=hight) { int mid=(low+hight)/2; if(temp<arr[mid]) { hight=mid-1; }else { low=mid+1; } } for(int j=i-1;j>=low;j--) { arr[j+1]=arr[j]; } arr[low]=temp; } } long endTime = System.nanoTime(); // 获取排序结束时间 System.out.println("排序結果:" + Arrays.toString(arr)); System.out.println("程序运行时间： " + (endTime - startTime) + "ns"); }
打印结果：
排序結果:[0, 1, 2, 3, 4, 5, 6, 7, 8] 程序运行时间：3300ns
在这里要说一下，很多人不知道二分排序是如何定义划分的中间点的，也就是把第几个索引定义为中间点，这里我讲一讲：
假设有n个元素，那么索引就是从0到n-1，我们用二分法找中间值的时候计算中间项的公式为：
（第一个索引+最后一个索引）/2 = 中间项的索引值
也就是：
（0+n-1）/2 取整数部分。
好了，关于简单的插入排序就先聊到这，下一篇文章我们会介绍一个稍微复杂一些的插入排序，希尔排序。有兴趣的可以持续关注。
