排序算法之希尔算法java实现

定义

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment
Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。
希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

实现原理步骤

先取一个小于n的整数d1作为第一个增量，把文件的全部记录分组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量
=1( < …<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

代码实现

public static void shellsort(int[] arr){
        for(int i=arr.length/2;i>0;i=i/2){
            for(int j=i;j<arr.length;j++){
                for(int k=j-i;k>=0;k=k-i){
                    if(arr[k]>arr[k+i]){
                        int temp =arr[k];
                        arr[k]=arr[k+i];
                        arr[k+i]=temp;
                    }
                }
            }
        }
    }