希尔排序（Shell Sort）

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n2）的第一批算法之一。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序是把记录按下表的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

算法描述

我们来看下希尔排序的基本步骤，在此我们选择增量gap=length/2，缩小增量继续以gap = gap/2的方式，这种增量选择我们可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：
选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
按增量序列个数k，对序列进行k 趟排序；
每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法分析

最佳情况：T(n) = O(nlog2 n)
最坏情况：T(n) = O(nlog2 n)
平均情况：T(n) = O(nlog2 n)

代码实现

Java

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
import java.util.Arrays;

public class ShellSort {

    public static void shellSort(int[] arr) {
        for (int step = arr.length / 2; step > 0; step /= 2) {
            for (int i = step; i < arr.length; i++) {
                if (arr[i] < arr[i - step]) {
                    int temp = arr[i];
                    int index = i;
                    while (index >= step && temp < arr[index - step]) {
                        arr[index] = arr[index - step];
                        index -= step;
                    }
                    arr[index] = temp;
                }
                System.out.println(Arrays.toString(arr));
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
        System.out.printf("原始数组：%s\n", Arrays.toString(arr));
        shellSort(arr);
        System.out.printf("排序后数组：%s\n", Arrays.toString(arr));
    }
}

Python

Python 实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def shell_sort(arr):
    step = int(len(arr) / 2)
    while step > 0:
        for i in range(step, len(arr)):
            if arr[i] < arr[i - step]:
                temp = arr[i]
                index = i
                while index >= step and temp < arr[index - step]:
                    arr[index] = arr[index - step]
                    index -= step
                arr[index] = temp
            print('分成%d组第%2d次排序第%d组后数组为：%s' % (step, i / step, (i % step) + 1, arr))
        step = int(step / 2)


if __name__ == '__main__':
    arr = [3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48]
    print('原始数组：', arr)
    shell_sort(arr)
    print('排序后数组：', arr)

Go

Go 实现
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
package main

import (
    "fmt"
)

func ShellSort(arr *[15]int) {
    for step := len(arr) / 2; step > 0; step /= 2 {
        for i := step; i < len(arr); i++ {
            if arr[i] < arr[i-step] {
                temp := arr[i] // 记录要插入的数
                index := i     // 记录要插入的位置
                for ; index >= step && temp < arr[index-step]; index -= step {
                    arr[index] = arr[index-step]
                }
                arr[index] = temp
            }
            fmt.Printf("分成%d组第%2d次排序第%d组后数组为：%v\n", step, i/step, (i%step)+1, *arr)
        }
    }
}

func main() {
    arr := [15]int{3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48}
    fmt.Printf("原始数组：%v\n", arr)
    ShellSort(&arr)
    fmt.Printf("排序后数组：%v\n", arr)
}