希尔排序

发表于 分类于 ， 阅读次数： 本文字数： 1.9k 阅读时长 ≈ 2 分钟

希尔排序

希尔排序是简单插入排序的改进，它是一种不稳定排序算法。由D.L.Shell在1959年提出。希尔排序实质上是一种分组插入方法。

算法描述

1、对于n个待排序的数列，取一个小于n的整数gap(称为步长)将待排序元素分成若干个组子序列，所有距离为gap的倍数的记录放在同一个组中。
2、然后对各组内的元素进行直接插入排序，这一趟排序完成之后，每一个组的元素都是有序的。
3、接下来减小gap的值，并重复执行上述的分组和排序。
4、重复这样的操作，当gap=1时，整个数列就是有序的。

图文演示

下面以数列{23,20,32,45,6,8,9,15}为例，演示它的希尔排序过程。
第1趟：(gap=4)
在这里插入图片描述
当gap=4时,意味着将数列分为4个组： {23,6}，{20,8}，{32,9}，{45,15}。 对应数列： {23,20,32,45,6,8,9,15}
对这4个组分别进行排序，排序结果： {6,23}，{8,20}，{9,32}，{15,45}。 对应数列： {6,8,9,15,23,20,32,45}
第2趟：(gap=2)
在这里插入图片描述
当gap=2时,意味着将数列分为2个组：{6,9,23,32}, {8,15,20,45}。 对应数列： {6,8,9,15,23,20,32,45}
注意：{6,9,23,32}实际上是上一步中的两个有序数列{6,23}和{9,32}组成。
{8,15,20,45}实际上是上一步中的两个有序数列{8,20}和{15,45}组成。
对这2个组分别进行排序，排序结果：{6,9,23,32}, 8,15,20,45}。 对应数列： {6,8,9,15,23,20,32,45}。
这一步其实啥都没做，这也可以看出希尔排序的不稳定性。
第3趟：(gap=1)
在这里插入图片描述
当gap=1时,意味着将数列分为1个组：{6,8,9,15,23,20,32,45}
注意：{6,8,9,15,23,20,32,45}实际上是上一步中的两个有序数列{6,9,23,32},和{8,15,20,45}组成。
对这1个组分别进行排序，排序结果：{6, 8, 9, 15, 20, 23, 32, 45}

代码实现

Java

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
package com.test;

import java.util.Arrays;

public class ShellSort {
    public static void main(String[] args) {
        int[] arr = new int[]{23,20,32,45,6,8,9,15};
        shellSort(arr);
        System.out.println("排序结果："+ Arrays.toString(arr));
    }

    /**
     * 希尔排序
     * 用了三层循环，最外层循环控制排序趟数;后两层循环相当于插入排序的1改为了gap
     * i=1 -> i=gap、j>0 -> j>=gap
     * @param arr
     */
    public static  void shellSort(int[] arr){
        for(int gap = arr.length/2;gap > 0;gap = gap/2) {
            for (int i = gap; i < arr.length; i += gap) {
                int tmp = arr[i];
                int j;
                for (j = i; j >= gap && tmp < arr[j-gap]; j -= gap){
                    arr[j] = arr[j-gap];
                }
                arr[j] = tmp;
            }
        }
    }
}

排序结果：[6, 8, 9, 15, 20, 23, 32, 45]

JavaScript

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function shellSort(arr){
       for(var gap = Math.floor(arr.length/2);gap > 0;gap = Math.floor(gap/2)) {
           for (var i = gap; i < arr.length; i += gap) {
               var tmp = arr[i];
               var j;
               for (j = i; j >= gap && tmp < arr[j-gap]; j -= gap){
                   arr[j] = arr[j-gap];
               }
               arr[j] = tmp;
           }
       }	
}
var arr = [23,20,32,45,6,8,9,15];
shellSort(arr);
console.log(arr);

(8) [6, 8, 9, 15, 20, 23, 32, 45]