基本思想
每一趟将一个待排序的记录，按其关键字的大小插入到已经排好序的一组记录的适当位置上，直到所有待排序记录全部插入为止。
排序过程
1.初始化无序区、有序区，待排序数组的第一个元素为有序区，剩余元素为无序区；
2.遍历无序区，将无序区每一个元素插入到有序区的正确位置上；
Java算法实现
/**
* 排序接口类
* Created by zhouyh on 2018/5/25.
*/
public abstract class ISort {
public abstract int[] sort(int[] array);
}
/**
* 直接插入排序
* Created by zhouyh on 2018/5/25.
*/ public class DirectInsertSort extends ISort {
@Override
public int[] sort(int[] array) {
int tmp;
for (int i=1; i<array.length; i++){
tmp = array[i]; //array[i]的拷贝
//如果右侧无序区第一个元素
array[i] < array[i-1]
小于左侧有序区最后一个元素
//需要将左侧有序区比array[i]大的元素后移
if (array[i] < array[i-1]){
int j = i-1;
while (j>=0 && tmp<array[j]){
array[j+1] = array[j];
j--;
}
array[j+1] = tmp;
}
} return array;
}
}
性能分析
时间复杂度，在比较的数组有序的情况下，为O(n)，即此刻比较次数n-1次，移动次数0；在最坏的情况下，即数组逆序的情况下，为O(n^2)，平均时间复杂度为O(n^2)
空间复杂度，直接排序的过程中，仅用到了一个临时变量，空间复杂端为O(1)
稳定性，直接插入排序为稳定排序，即排序前后的元素位置还是保持和排序前的前后顺序一致，例{2①,45,12,2④,3}，排序后{2①,2④,3,12,45}，其中两个2的前后顺序保持一致。
使用场景
在数组包含的元素数量较小情况下，可以选择插入排序，元素数量较大的情况下，不适用，因此时移动元素的次数较多；
在数组基本有序的情况下，适合使用插入排序，此时时间复杂度基本上为O(n)
原创文章，作者：ItWorker，如若转载，请注明出处：https://blog.ytso.com/7489.html