Hello，小伙伴们，大家好，我是才辰。
今天和大家一起学习的是排序算法中的插入排序和希尔排序。为什么把这两个排序放在一起呢？这是因为这两种排序有一定的关联，希尔排序实际上是对插入排序的一种变形。
还是老样子，我先总体上介绍一下算法的过程，接着以一个例子分步讲解，最后给出了详细的代码以及相关分析。
插入排序
插入排序，就和我们平时玩牌是一样的
因为你想，我们在打牌的时候，是不是先把手里的牌由小到大排好，然后每摸到一张牌，就依照大小把它放在排在正确的位置。同样，插入排序也是如此。
步骤：
- 首先选取数组第二个元素,若小于数组第一个元素，则插入到第一个位置，否则保持不动；
- 接着选取第3个元素，把它和左边第一个元素比较，如果其小于左边第一个元素，则继续与左边第二个元素比较，知道遇到不比它大的元素，然后插入到这个元素右边。
- 然后依次选取第4、5、6…n个元素，重复第二个步骤，选择适当的位置插入。
下面以数组arr=[4,3,9,8,1]说明一下
举例说明：
假设arr数组为[4,3,9,8,1].
第一步：选择数组第二个元素3，3<4，将3插入到数组第一个位置；
第二步：9>4，保持不动
第三步：8<9,8>4,将8插入到元素4的后面
第四步：1<9,1<8,1<4,1<3，将1插入到数组第一个位置，至此排序完成
代码（有详细注解）：
public class InsertSort{
public static int []InsertSort(int[] arr) {
if(arr.length<=1)
return arr;
int len=arr.length;
for(int i=1;i<len;i++) {
int t=arr[i];
//找到插入位置
int k=i-1;
while(k>=0&&arr[k]>arr[i])
k--;
//arr[k]之后的元素右移一位
for(int j=i;j>k+1;j--)
{
arr[j]=arr[j-1]
}
//插入位置是k+1
arr[k+1]=t;
}
return arr;
}
}性质：
- 时间复杂度：O（n*n）
- 空间复杂度：O(1)
- 是否是稳定排序：是
- 是否是原地排序：是
希尔排序
对于希尔排序，其实是插入排序的一种变形。
在插入排序中，如果元素的有序程度不高或者数据规模比较大，则需要交换很多次才能到达正确位置。希尔排序通过分组的方式，先使数组局部有序，从而可以减少最后元素交换次数，降低时间复杂度。
希尔排序是采用插入排序的思想，先让数组中任意间隔h的元素有序，接着让数组中任意间隔为h/2的元素有序，接着h/4,h/8…，就这样一直缩小，当h=1时，数组中任意间隔为1的数组都是有序的，即完成了数组的排序。
举例说明：
假设arr=[6,9,4,3,2,7,1,5,0,8]
第一步: 取h=n/2=5,将任意间隔为5的元素分为1组，即以下相同颜色的元素为一组
对每一组元素进行插入排序，得到结果如下：
第二步：取h=n/4=2,即将任意间隔为2的元素归为1组，可分为2组，如下
对每一组元素进行插入排序，得到
由此可以看出，数组已基本有序。
第三步：h=n/8=1,即将数组所有元素进行插入排序，得到最后结果
虽然希尔排序需要进行多趟排序，但在数组元素有序程度不高或者数据规模较大的情况下，仍然要比插入排序要快的多。
【代码】
public class ShellSort {
public static int[] shellSort(int arr[]) {
if(arr.length<=1)
return arr;
int n=arr.length;
//将数组元素以h为间隔分组，开始时h通常取n/2.
for(int h=n/2;h>0;h=h/2) {
for(int i=h;i<n;i++)
{
//对arr[i]进行插入排序
insertsort(arr,i,h);
}
}
return arr;
}
//arr[i]所在的组为arr[i-2*h]、arr[i-h]、arr[i+h]...
public static void insertsort(int arr[],int i,int h) {
int t=arr[i];
//空出位置
for(int k=i-h;k>0&&arr[k]>t;k-=h) {
arr[k+h]=arr[k];
}
//插入
arr[k+h]=t;
}
}从代码中也可以看出，对各个组进行插入的时候并不是对一组排序完再对另一个组排，而是轮流对每个组进行插入排序。
性质：
- 时间复杂度：O（nlogn）
- 空间复杂度：O（1）
- 是否是稳定排序：否
- 是否是原地排序：是
这篇文章简单介绍了下插入排序和希尔排序，接下来还会继续写剩下的排序算法。如果有关于文章的任何问题，欢迎加我的微信交流哦。
最后，欢迎关注我的公众号【编程365】，学习更多算法+计算机基础知识。
