希尔排序

刺骨的言语ヽ痛彻心扉 2021-09-18 07:10 431阅读 0赞

# 插入排序的问题 #

![18721752-7da6fa07c682dd24.png][]

image.png

# Introduce #

![18721752-13b82d591b8ab0cb.png][]

image.png

# 核心思想 #

![18721752-bad55cde54e5798b.png][]

image.png

# 公式 #

for分组
    for 插入分组遍历
    当前值，索引位
    while寻找插入位置

# code #

package com.pl.arithmetic.sort;
    
    import java.time.Duration;
    import java.time.Instant;
    import java.util.Arrays;
    
    /**
     * <p>
     *
     * @Description: TODO
     * </p>
     * @ClassName ShellSort
     * @Author pl
     * @Date 2020/12/4
     * @Version V1.0.0
     */
    public class ShellSort {
        public static void main(String[] args) {
           /* int[] arr = new int[80000];
            for(int i =0; i < 80000;i++) {
                arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
            }
            Instant befor = Instant.now();
            selectSort(arr);
            Instant after = Instant.now();
            Duration between = Duration.between(befor, after);
            System.out.println(between.toMillis());*/
            int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
            selectSort(arr);
            System.out.println(Arrays.toString(arr));
    
        }
    
    
        /**
         * 代码核心
         *
         * @param arr
         * @return void
         * @exception
         * @author silenter
         * @date 2020/12/4 6:56
        */
        public static void selectSort(int[] arr){
            //todo 分组遍历，每组步长不同
            //循环log2 arr.length ,该层遍历，组内遍历，
            for (int grap = arr.length/2; grap >0; grap/=2) {
                //todo 和插入排序一样，默认分为两组，无序组和有序组比较
                for (int j=grap;j<arr.length;j++){
                    int temp = arr[j];
                    int index = j;
                    if (arr[j] <arr[j-grap]){
                        //todo 点前值和同组内前一个元素比较，寻找自己超插入的位置
                        while (index -grap>=0 && temp <arr[index-grap] ){
                            arr[index] = arr[index-grap];
                            index -= grap;
                        }
                        arr[index] = temp;
                    }
                }
            }
        }
    }

![18721752-036df61dea97a2e0.png][]

image.png

80000排序

package com.pl.arithmetic.sort;
    
    import java.time.Duration;
    import java.time.Instant;
    import java.util.Arrays;
    
    /**
     * <p>
     *
     * @Description: TODO
     * </p>
     * @ClassName ShellSort
     * @Author pl
     * @Date 2020/12/4
     * @Version V1.0.0
     */
    public class ShellSort {
        public static void main(String[] args) {
            int[] arr = new int[80000];
            for(int i =0; i < 80000;i++) {
                arr[i] = (int)(Math.random() * 8000000); //生成一个[0, 8000000) 数
            }
            Instant befor = Instant.now();
            selectSort(arr);
            Instant after = Instant.now();
            Duration between = Duration.between(befor, after);
            System.out.println(between.toMillis());
            /*int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
            selectSort(arr);
            System.out.println(Arrays.toString(arr));*/
    
        }
    
    
        /**
         * 代码核心
         *
         * @param arr
         * @return void
         * @exception
         * @author silenter
         * @date 2020/12/4 6:56
        */
        public static void selectSort(int[] arr){
            //todo 分组遍历，每组步长不同
            //循环log2 arr.length ,该层遍历，组内遍历，
            for (int grap = arr.length/2; grap >0; grap/=2) {
                //todo 和插入排序一样，默认分为两组，无序组和有序组比较
                for (int j=grap;j<arr.length;j++){
                    int temp = arr[j];
                    int index = j;
                    if (arr[j] <arr[j-grap]){
                        //todo 点前值和同组内前一个元素比较，寻找自己超插入的位置
                        while (index -grap>=0 && temp <arr[index-grap] ){
                            arr[index] = arr[index-grap];
                            index -= grap;
                        }
                        arr[index] = temp;
                    }
                }
            }
        }
    }

![18721752-aaf2fb9d285cb720.png][]

image.png

14毫秒

[18721752-7da6fa07c682dd24.png]: /images/20210918/c3827390bb7f48838f2df03cea50dcc0.png
[18721752-13b82d591b8ab0cb.png]: /images/20210918/d540bd5589b94c30a8fee196e385f80b.png
[18721752-bad55cde54e5798b.png]: /images/20210918/fef9d18ddab9412bbecd9156c8e779b9.png
[18721752-036df61dea97a2e0.png]: /images/20210918/80b8b99a4c1e42fd841935b0a1cb4834.png
[18721752-aaf2fb9d285cb720.png]: /images/20210918/87f118dfcee34ada8947576be6e89508.png