希尔排序（Java） 2022.01.01

希尔排序也是一种插入排序，它是简单插入排序经过改进后的更高效的排序，也成为缩小增量排序。

希尔排序的基本思想为：希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

希尔排序执行结果如图：

具体代码如下：

package DataStructures.sort;

import java.util.Arrays;


public class ShellSort {

    public static void main(String[] args) {
        int[] nums = {8,9,1,7,2,3,5,4,6,0};
        System.out.println("原始数组为："+Arrays.toString(nums));
        shellSort(nums);
    }

    public static void shellSort(int[] nums){

        int count = 0;
        //设置增量，并逐渐缩小增量
        for( int gap = nums.length / 2; gap > 0; gap /= 2 ){
            for( int i = gap; i < nums.length; i++ ){
                int j = i;
                int temp = nums[j];
                if( nums[j] < nums[j - gap] ){
                    while ( j - gap >= 0 && temp < nums[j - gap] ){
                        nums[j] = nums[j - gap];
                        j -= gap;
                    }
                    //退出while循环说明已经找到插入位置
                    nums[j] = temp;
                }
            }
            System.out.println("第"+(++count)+"轮希尔排序："+ Arrays.toString(nums));
        }
    }
}