插入排序有2种，分别是直接插入排序和希尔排序。
1.直接插入排序：从还没排序的数组里取出一个数，插入到已排序的数组里。
这里有一个未排序的数组:
image
那么具体的排序升序过程(从待排序数组里取出索引下标从1开始，因为初始时排好序的数组没有数字，那么下标是0的数字就直接放入排好序的数组里):
第1趟：从未排序的数组取出第一个的数字4，4比1大，直接插入排好序的数组里；
第2趟：再从未排序的数组取出第一个的数字3，在已排好序的数组里从后往前找，找到一个比3小的数(数字1)，并插入到数字1的后面；
...
如此重复插入的过程直到排好序。
image
具体实现代码如下：
image
时间复杂度：O(n^2)；
空间复杂度:只用到一个临时空间，所以空间复杂度O(1)；
2.希尔排序：希尔排序根据增量d(看情况设置)将待排序的数组分组，每组进行直接插入排序，每次分组排序后，d=d/2，重复分组排序数组，直到d=0结束排序。具体排序：
d=3
第1组数据：1 6 7 排序后：1 6 7
第2组数据：4 5 排序后：4 5
第3组数据：3 2 排序后：2 3
d=1
第1组数据：1 2 3 4 5 6 7 排序后：1 2 3 4 5 6 7
d=0,结束排序。
image
具体代码实现:
image
时间复杂度：不确定，取决于增量d的值；
空间复杂度:只用到一个临时空间，所以空间复杂度O(1)；
其实希尔排序是直接插入排序的升级版，所以整体来看，只要思路清晰，其实插入排序并不难。
网友评论