排序算法——希尔排序

简单介绍

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

基本思想

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

思路图解图

image-20230219172508741

先根据不断分组来进行排序，最后当gap等于1进行插入排序

代码

算法代码

交换法

速度较慢，和冒泡时间差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * 希尔排序插入交换法（速度太慢）
 * @param arr
 */
public static void shellSorting1 ( int[] arr ) {
    int x = 1;
    for ( int gap = arr.length / 2 ; gap > 0 ; gap /= 2 ) {
        int temp ;
        for ( int i = gap ; i < arr.length ; i++ ) {
            //遍历各组中所有的元素（共gap组，每组10/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 ( "希尔排序第" + ( x++ ) + "轮" + Arrays.toString ( arr ) );
    }
    System.out.println ("交换法排序后"+ Arrays.toString (arr));
}

移动法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * 希尔排序插入移动法
 * @param arr
 */
public static void shellSorting2 ( int[] arr ) {
    //增量gap,并逐步的缩小增量
    for ( int gap = arr.length / 2 ; gap > 0 ; gap /= 2 ) {
        //从第gap个元素，逐个对所在的组进行直接插入排序
        for ( int i = gap ; i < arr.length ; i++ ) {
            int j = i;
            int temp = arr[j];  //用一个变量接收待变化的数
            if ( arr[ j ] < arr[ j - gap ] ) { //进入条件在这加比较，每次最多能省下2次判断
                while (j-gap >= 0 && temp < arr[ j-gap ] ) { //首先不能越界，其次这里比较是为了循环时j变化后进行再次比较判断
                    arr[ j ] = arr[ j - gap ];
                    j -= gap;

                }
                //当while退出后，即找到插入的位置
                //能到这肯定是已经变化了
                arr[ j ] = temp;

            }

        }
    }
    System.out.println ("移动法排序后"+ Arrays.toString (arr));
}

性能测试

依旧是用80000个数来进行排序比较时间

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
public class ShellSorting {
    public static void main ( String[] args ) {
//        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
//        shellSorting ( arr );
        int arr[] = new int[ 80000 ];
        int arr1[] = new int[ 80000 ];
        randomArr ( arr );
        randomArr ( arr1 );

        System.out.println ("希尔排序交换法所用时间" );
        String date1String = Date ( );
        System.out.println ("排序前时间是："+date1String );
        shellSorting1 ( arr );
        String date2String = Date ( );
        System.out.println ("排序后时间是："+date2String );

        System.out.println ("希尔排序移动法所用时间" );
        String date3String = Date ( );
        System.out.println ("排序前时间是："+date3String );
        shellSorting2 ( arr1 );
        String date4String = Date ( );
        System.out.println ("排序后时间是："+date4String );
    }


    /**
     * 希尔排序插入移动法
     * @param arr
     */
    public static void shellSorting2 ( int[] arr ) {
        //增量gap,并逐步的缩小增量
        for ( int gap = arr.length / 2 ; gap > 0 ; gap /= 2 ) {
            //从第gap个元素，逐个对所在的组进行直接插入排序
            for ( int i = gap ; i < arr.length ; i++ ) {
                int j = i;
                int temp = arr[j];  //用一个变量接收待变化的数
                if ( arr[ j ] < arr[ j - gap ] ) { //进入条件在这加比较，每次最多能省下2次判断
                    while (j-gap >= 0 && temp < arr[ j-gap ] ) { //首先不能越界，其次这里比较是为了循环时j变化后进行再次比较判断
                        arr[ j ] = arr[ j - gap ];
                        j -= gap;

                    }
                    //当while退出后，即找到插入的位置
                    //能到这肯定是已经变化了
                    arr[ j ] = temp;

                }

            }
        }
//        System.out.println ("移动法排序后"+ Arrays.toString (arr));
    }

    /**
     * 希尔排序插入交换法（速度太慢）
     * @param arr
     */
    public static void shellSorting1 ( int[] arr ) {
        int x = 1;
        for ( int gap = arr.length / 2 ; gap > 0 ; gap /= 2 ) {
            int temp ;
            for ( int i = gap ; i < arr.length ; i++ ) {
                //遍历各组中所有的元素（共gap组，每组10/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 ( "希尔排序第" + ( x++ ) + "轮" + Arrays.toString ( arr ) );
        }
//        System.out.println ("交换法排序后"+ Arrays.toString (arr));



        //先使用逐步推导来解决
        /*int temp = 0;
        //希尔排序的第一轮排序 10/2=5
        for ( int i = 5 ; i < arr.length ; i++ ) {
            //遍历各组中所有的元素（共五组，每组2个），步长5
            for ( int j = i - 5 ; j >= 0 ; j -= 5 ) {
                if ( arr[ j ] > arr[ j + 5 ] ) {
                    temp=arr[ j ];
                    arr[ j ] = arr[ j + 5 ];
                    arr[ j + 5 ] = temp;
                }
            }
        }
        System.out.println ( "希尔排序第1轮" + Arrays.toString ( arr ) );

        //希尔排序的第二轮排序 5/2=2
        for ( int i = 2 ; i < arr.length ; i++ ) {
            //遍历各组中所有的元素（共2组，每组5个），步长2
            for ( int j = i - 2 ; j >= 0 ; j -= 2 ) {
                if ( arr[ j ] > arr[ j + 2 ] ) {
                    temp=arr[ j ];
                    arr[ j ] = arr[ j + 2 ];
                    arr[ j + 2 ] = temp;
                }
            }
        }
        System.out.println ( "希尔排序第2轮" + Arrays.toString ( arr ) );

        //希尔排序的第二轮排序 2/2=1
        for ( int i = 1 ; i < arr.length ; i++ ) {
            //遍历各组中所有的元素（共1组，每组10个），步长1
            for ( int j = i - 1 ; j >= 0 ; j -= 1 ) {
                if ( arr[ j ] > arr[ j + 1 ] ) {
                                   temp=arr[ j ];
                    arr[ j ] = arr[ j + 1 ];
                    arr[ j + 1 ] = temp;
                }
            }
        }
        System.out.println ( "希尔排序第3轮" + Arrays.toString ( arr ) );*/
    }
    /**
     * 随机数组
     * @param arr
     */
    private static void randomArr ( int[] arr ) {
        for(int i = 0; i < arr.length;i++){
            arr[ i ] = (int) ( Math.random ( ) * 8000000 );  //会生成【0，8000000）直接的数
        }
    }

    /**
     * 将此时调用函数的时间格式化打出来
     * @return 年-月-日 时-分秒
     */
    private static String Date ( ) {
        Date date1 = new Date ( );  //调函数的当前时间
        SimpleDateFormat simpleFormatter = new SimpleDateFormat ( "HH:mm:ss" );//格式化
        return simpleFormatter.format(date1 );
    }
}

结果

两种方法进行比较，时间差距十分的大

image-20230219171738544