排序算法——希尔排序（Shell Sorting）

简单插入排序存在的问题

​ 当需要插入的数是较小的数时，后移次数明显增多，对效率有影响

希尔排序法介绍

​ 希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，他是简单插入排序经过改良后的一个更高效的版本，也称为缩小增量排序

基本思想

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

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4k7aqBzF-1657355579231)(C:Users15640AppDataRoamingTyporatypora-user-imagesimage-20220708174644934.png)]

代码演示

package com.crisp.Sort;

import java.text.SimpleDateFormat;
import java.util.Arrays;
import java.util.Date;

public class ShellSort {
    public static void main(String[] args) {
//        int[] arr = {8,9,1,7,2,3,5,4,6,0};
//        print(arr);
//        Shell(arr);
//        print(arr);

        //创建有100000个数据的数组
        int[] arr = new int[100000];
        for(int i = 0; i < arr.length; ++i){
            arr[i] = (int)(Math.random() * 100000);//生成一个[0,100000)的随机数
        }
        System.out.printf("原始数组为：");
        print(arr);
        Date data1 = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String data1Str = simpleDateFormat.format(data1);
        //ShellBySwitch(arr);
        ShellByMove(arr);
        Date data2 = new Date();
        String data2Str = simpleDateFormat.format(data2);
        System.out.printf("排序过后数组为：");
        print(arr);
        System.out.printf("排序前的时间是：%sn",data1Str);
        System.out.printf("排序后的时间是：%sn",data2Str);

    }

    //打印
    public static void print(int[] arr){
        System.out.println(Arrays.toString(arr));
    }

    //希尔排序法 从小到大 交换法
    public static void ShellBySwitch(int[] arr){
        int l = arr.length;
        while(l != 1){
            l /= 2;
            for(int i = l; i < arr.length; ++i){
                for(int j = i - l; j >= 0; j -= l){
                    if(arr[j] > arr[j+l]){
                        int tmp = arr[j];
                        arr[j] = arr[j+l];
                        arr[j+l] = tmp;
                    }
                }
            }
        }
    }

    //对交换式的希尔排序进行优化->移位法
    public static void ShellByMove(int[] arr){
        int l = arr.length;
        while(l != 1){
            l /= 2;
            for(int i = l; i < arr.length; ++i){
                int j = i;
                int temp = arr[j];
                if(arr[j] < arr[j-l]){
                    while(j-l >= 0 && temp < arr[j-l]){
                        arr[j] = arr[j-l];
                        j -= l;
                    }
                    arr[j] = temp;
                }
            }
        }
    }
}