排序算法之希尔排序(Java)

发表于   |   分类于   |     |   阅读次数

希尔排序简介

希尔排序（Shell Sort），也称递减增量排序算法，是Donald Shell在1959年提出来的一种排序算法。它是插入排序的一种更高效的改进版本。

希尔排序思想

希尔排序通过将比较的全部元素分为几个区域来提升插入排序的性能。这样可以让一个元素可以一次性地朝最终位置前进一大步。然后算法再取越来越小的步长进行排序，算法的最后一步就是普通的插入排序，但是到了这步，需排序的数据几乎是已经排好的了。

步长序列

步长的选择是希尔排序的重要部分。只要最终步长为1任何步长序列都可以工作。算法最开始以一定的步长进行排序。然后会继续以一定步长进行排序，最终算法以步长为1进行排序。

希尔排序过程

具体排序过程如下图所示：

算法实现

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
/**
 * @description 对顺序表L作希尔排序
 * @author GongchuangSu
 * @since 2016.04.01
 * @version v1.0
 */
public class ShellSort {
    public static void main(String[] args) {
        // sqList[0]用作哨兵或临时变量
        int[] sqList = {
            1000, 50, 10, 90, 30, 70, 40, 80, 60, 20
        };
        shellSort(sqList);
        // 输出打印
        for (int i = 1; i < sqList.length; i++)
            System.out.println(String.valueOf(sqList[i]));
    }

    /**
     * 功能：希尔排序
     */
    private static void shellSort(int[] sqList) {
        int i, j;
        int increment = sqList.length - 1;
        do {
        	// 增量序列
            increment = increment / 3 + 1;
            for (i = increment + 1; i < sqList.length; i++) {
                if (sqList[i] < sqList[i - increment]) {
                	// 需将sqList[i]插入有序增量子表
                    sqList[0] = sqList[i]; // 暂存sqList[0]
                    // 记录后移，查找插入位置
                    for (j = i - increment; j > 0 && sqList[0] < sqList[j]; j -= increment)
                        sqList[j + increment] = sqList[j];
                    sqList[j + increment] = sqList[0];
                }
            }
        } while (increment > 1);
    }
}

算法分析

时间复杂度

在最好的情况下，其时间复杂度为$\Theta(n^1.3)$；
在最坏的情况下，其时间复杂度为$\Theta(n^2)$。

空间复杂度

很明显，其空间复杂度为$\Theta(1)$。

稳定性

希尔排序是不稳定的。