希尔排序（缩小增量排序）

希尔排序

-- 插入排序中的一种，也叫缩小增量排序，是不稳定排序。 适用于顺序存储

排序思想

1、将乱序元素分成 d1 组（组内元素和往后数d1个的元素为一组，每一组组内元素并不相邻）

2、对每一分组内元素进行直接插入排序

3、将全部元素再分成 d1/2 组（取下界）

4、对每一分组元素进行直接插入排序

5、再分组，重复上述步骤直到 d=1

d一般取长度的一半（取下界）   例 7个元素，则 d1 = 7/2 （取下界）  d1=3

#：  3　　6　　5　　2　　5　　1　　4　　7个元素分为3组, d1=3 （相应元素往后数 3 个为一组），相同颜色的元素为一组，对 [3,2,4] [6,5] [5,1] 分别进行插入排序

得到　　2　　5　　1　　3　　6　　5　　4　　

->　　2　　5　　1　　3　　6　　5　　4　　d2 = 3/2（取下界）d2 = 1 ,缩小增量,　对整个序列分别进行插入排序

得到　　1　　2　　3　　4　　5　　5　　6

其中在第一次排序的时候，由于分组， 第一个5 和第二个 5 交换了位置，因此，希尔排序是不稳定的排序。

import java.util.Arrays;

public class ShellsSort{
    public static void main(String[] args) {
        int[] arr = {5, 7, 8, 4, 2, 7, 1, 8, 12, 25, 10};
        shellsSort(arr, arr.length);
    }

    public static void shellsSort(int[] arr, int n) {
        //三层循环。分组——组内插入排序
        int i,j,group;
        int count = 0;

        for(group=n/2; group>0; group/=2){            //分组  

            for(i = group; i<n; i+=group){               //分的组就循环次数，也代表每组第一个元素所在位置
                int temp = arr[i];
                for(j=i; j>0 && arr[j-group]>temp; j-=group){       //插入排序，要记住中间隔了group个元素
                    arr[j] = arr[j-group];
                }
                arr[j] = temp;
            }

            count++;
            System.out.println("第"+(count)+"次排序之后，元素序列为："+Arrays.toString(arr));
            
        }
    }
}