2.4 希尔排序（Shell Sort）

一. 定义

​ 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，是突破O(n²)的第一批算法。

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

二. 代码实现

/**
 * 希尔排序
 * @author GreyPigeon mail:2371849349@qq.com
 * @since 2024-01-12-16:42
 **/
public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        shellSort(arr);

    }

    //希尔排序：在插入时采用交换法
    public static void shellSort(int[] arr){
        int temp = 0;
        int count = 0;
        for(int gap = arr.length/2; gap > 0; gap /=2){
            for(int i = gap; i < arr.length; i++){
                //遍历各组中的所有元素（共gap组，每组有arr.length/gap个元素），步长为gap
                for(int j = i - gap; j >= 0; j -= gap){
                    //如果当前元素大于加上步长后的那个元素，说明交换
                    if(arr[j] > arr[j + gap]){
                        temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            System.out.println("希尔排序第" + (++count) + "轮 = " + Arrays.toString(arr));
        }
    }
}