关于希尔排序的理解
今天复习希尔排序的时候，对希尔排序有了新的理解
首先希尔排序是什么：希尔排序（Shell Sort）是一种基于插入排序的排序算法，又称缩小增量排序（Diminishing Increment Sort），是直接插入排序的一种更高效的改进版本。希尔排序通过将数组元素按一定增量分组，对每组使用直接插入排序算法排序，随着增量逐渐减少，每组包含的元素越来越多，当增量减至1时，整个数组恰被分成一组，算法便终止。
希尔排序的核心在于选择初始增量和后续减少增量的策略。常用的增量选择策略有希尔增量（Shell's original increment sequence）、希伯特增量（Hibbard increment sequence）、Sedgewick增量等
说人话就是希尔排序是插入排序的升级，具体内容是把数据分成一个个组，然后每个组进行希尔排序，然后再把整体进行排序，这样尽量把小数据往前放，提高效率。
然后是代码实现：
private static void shellSort(int[] arr) {
int length = arr.length;
int position = 0;
//分组，i是组数也是步长
for (int step = length / 2; step > 0; step = step / 2) {
//循环每个组第一个元素，然后后续通过第一个元素遍历所有元素
for (position = 0; position < step; position++) {
insertStep(arr,length,position,step);
}
}
}
/**
* @param arr 数组
* @param length 长度
* @param iPosition 当前位置
* @param step 步长，也就是几个组
*/
private static void insertStep(int[] arr, int length, int iPosition, int step) {
Integer j=0;
for (int i = iPosition + step; i < length; i = i + step) {
int temp=arr[i];
for (j = i-step; j >= 0; j = j - step) {
if(arr[j]>arr[i]){
arr[j+step]=arr[j];
}else{
break;
}
}
arr[j+step]=temp;
}
}
然后很多人在写这部分代码的时候表示很难写清楚，我告诉大家一个好方法：
把这个算法分成两部分，第一部分只负责分组及操作（不具体排序），第二部分只负责排序，
首先第一部分：
分组，我们需要不断分组，比如一共10个数排序，先除以2，分成5份(也就是步长是5，下边回会用)，每份下标就是[0,5]，[1,6]，[2,7]，[3,8]，[4,9],(注意这是下标，不是值),然后再除以2，分成2份，以此类推，直到分成一份；然后我们要每个组进行操作：
分组：
int length = arr.length;
//这里分组数就是步长(每组下个元素需要跳的步长)，大家试着理解一下
for(int step=length/2;step>;step=step/2)
分组后每个组进行操作：
for (int step = length / 2; step > 0; step = step / 2) {
//循环每个组第一个元素，然后后续通过第一个元素遍历所有元素
for (position = 0; position < step; position++)
}
到这里大家先不要管排序的事，只管这里分组和要怎么操作分组。
然后第二部分，排序：
排序就是排序，大家不要管分组的事，只要记得这里有个步长，也就是分几组就行，后边会用
我们分析不分组的插入和分组的插入有什么区别
不分组的时候我们插入每个值的时候是这样：
for(int i=1;i<n;i++)
也就是起始位置是，第一个，然后每次增加的位置是1，也就是i+1
分组的时候，只有间隙不一样，也就是增加的位置不一样，不是+1，而是+step也就是步长：
比如第一个组：
for(int i=0+step;i<n;i=i+step)；
当然第二个组就是
for(int i=1+step;i<n;i=i+step)；
这个i就是第一个组第几个元素，先记下，后边会说
然后再看插入排序第二层循环，有什么区别：
for(int j=i-1;i>0;j=j-1)；
同理，分组后：
for(int j=i-step;i>0;j=j-step)；
然后我们将两部分综合起来，发现排序的第一步也就是
for(int i=0+step;i<n;i=i+step)；这里i=0+step，这个0就是分组后的第几个元素，也就是分组后的内层循环 for (position = 0; position < step; position++) 里的position，所以我们可以将两部分合起来：
//分组，i是组数也是步长
for (int step = length / 2; step > 0; step = step / 2) {
//循环每个组第一个元素，然后后续通过第一个元素遍历所有元素
for (position = 0; position < step; position++) {
insertStep(arr,length,position,step);
}
}
排序：
private static void insertStep(int[] arr, int length, int iPosition, int step) {
Integer j=0;
for (int i = iPosition + step; i < length; i = i + step) {
int temp=arr[i];
for (j = i-step; j >= 0; j = j - step) {
if(arr[j]>arr[i]){
arr[j+step]=arr[j];
}else{
break;
}
}
arr[j+step]=temp;
}
}
这里iPosition就是分组传过来的参数