插入排序是和冒泡排序一样，是一个平均时间复杂度在O(n2)的简单排序算法，但是其在数据量小，且基本有序的情况下，具有优秀的性能，如果待排序数组满足基本有序的条件，那么插入排序的最优时间复杂度接近O(n2)。希尔排序是最早突破O(n2)时间界限的一种排序算法，希尔排序算法是在插入排序算法的基础上进行改进的排序算法，本文先描述插入排序的基本实现过程，后续有文章在此基础上介绍希尔排序的基本原理。
一丶插入排序
插入排序是和冒泡排序一样，是一个平均时间复杂度在O(n2)的简单排序算法，但是其在数据量小，且基本有序的情况下，具有优秀的性能，如果待排序数组满足基本有序的条假设待排序数组A,满足int [] A = new int[]{5,7,2,3,1,9},用插入排序算法对上述数组进行排序，可用图解的过程描述如下：
-
初始指针p指向待排序数组的第一个元素，默认p指针之前的p-1个元素都是有序。此时需要调整p指针所指向的元素位置，使得包括p指针所指向元素在内的前p个元素有序排列，此时p指针指向第一个元素，无须调整。
-
p++,p指针指向第二个元素，发现无须调整p指针所指向元素的位置即可保证前p个元素的有序性
image -
p++,p指针指向第三个元素2，此时需要调整p指针指向元素的位置，从p-1处开始比较，找到第一个小于元素2的元素，比较后发现前面没有比元素2小的元素，所以元素2应该排在第一个，调整结果如下所示
image -
p++，p指针指向第四个元素3，调整元素3的位置，从p-1的位置开始，向前搜索第一个小于3的元素，搜索后发现了元素2，所以元素3应排在元素2后面，调整结果如下所示：
image -
p指针不断后移，遍历所有元素，并且重复上述的调整过程后，排序工作就完成了，后续的调整过程如下图所示：
image
总结：
上述图例介绍了插入排序算法的基本实现过程，根据算法实现过程，可以对插入排序的时间复杂度做一个定性分析:
(1)插入排序的时间复杂度，第一体现在需要对被待排序数组中每个元素进行遍历，第二体现在对不满足顺序的元素需要进行调整的过程。
(2)数组长度为n，需要遍历n次。在每次遍历的过程中，假设元素A[n]均需要调整，
这个调整过程主要体现在从n-1的位置向前搜索第一个小于A[n]的元素。
(3)假如前n-1个元素是顺序的，那么搜索一次结束。那么一趟排序下来总共需要搜索n次，此时间复杂度是O(n),是插入排序的最优时间复杂度。
(4) 假如前n-1个元素是逆序，那么需要搜索n-1次结束。一趟排序下来需要搜索的总次数是：，时间复杂度是O(n2),属于最坏时间复杂度。
(5)平均时间复杂度不做证明，也是O(n2)。
二丶java代码实现
public classInsertSort {
publicstatic void main(String [] args){
int[] data = new int[]{3,5,4,7,8,9,1,2};
insertSort(data);
for(int i =0;i<data.length;i++){
System.out.println(data[i]+" ");
}
}
publicstatic void insertSort(int[]data){
for(int i =0;i<data.length;i++){
int temp =data[i];
int j =i-1;
for(;j>=0;j--){
if(data[j]>temp){
data[j+1] =data[j];
}else{
break;
}
}
data[j+1] = temp;
}
}
}
Reference:
[1] 数据结构与算法 java语言描述
[2] 原文博客链接
