Shell Sort in Java – 在Java中的外壳排序

最后修改: 2019年 7月 28日

中文/混合/英文(键盘快捷键：t)

1. Introduction

1.介绍

In this tutorial, we’ll describe the Shell sort algorithm in Java.

在本教程中，我们将介绍Java中的Shell排序算法。

2. The Shell Sort Overview

2.贝壳排序概述

2.1. Description

2.1.描述

Let’s first describe the Shell sort algorithm so we know what we’re trying to implement.

让我们首先描述一下Shell排序算法，以便我们知道我们要实现的是什么。

Shell sort is based on the Insertion sorting algorithm, and it belongs to the group of very efficient algorithms. In general, the algorithm breaks an original set into smaller subsets and then each of those is sorted using Insertion sort.

Shell排序是基于插入式排序算法，它属于非常高效的算法组。一般来说，该算法将一个原始集合分成更小的子集，然后使用插入排序对其中的每一个子集进行排序。

But, how it makes the subsets is not straightforward. It doesn’t choose neighboring elements to form a subset as we might expect. Rather, shell sort uses the so-called interval or gap for subset creation. For example, if we have the gap I, it means that one subset will contain the elements that are I positions apart.

但是，它是如何制作子集的，并不直接了当。它并不像我们所期望的那样选择相邻的元素来形成一个子集。相反，shell sort使用所谓的interval或gap来创建子集。例如，如果我们有间隙I，这意味着一个子集将包含元素，它们相隔I位。

Firstly, the algorithm sorts the elements that are far away from each other. Then, the gap becomes smaller and closer elements are compared. This way, some elements that aren’t in a correct position can be positioned faster than if we made the subsets out of the neighboring elements.

首先，该算法对彼此距离较远的元素进行排序。然后，差距变小，较近的元素被比较。这样一来，一些位置不正确的元素就可以比我们用相邻的元素做子集更快地被定位。

2.2. An Example

2.2.一个例子

Let’s see this in the example with the gaps of 3 and 1 and the unsorted list of 9 elements:

让我们在有3和1的间隙和9个元素的未排序列表的例子中看到这一点：。

unsorted list of 9 elements

If we follow the above description, in the first iteration, we’ll have three subsets with 3 elements (highlighted by the same color):

如果我们按照上面的描述，在第一次迭代中，我们将有三个子集，其中有3个元素（用相同的颜色突出显示）：。

three subsets with 3 elements

After sorting each of the subsets in the first iteration, the list would look like:

在第一次迭代中对每个子集进行排序后，该列表将看起来像：。

sorting each of the subsets in the first iteration

We can note that, although we don’t have a sorted list yet, the elements are now closer to desired positions.

我们可以注意到，尽管我们还没有一个排序的列表，但现在的元素已经更接近于理想的位置。

Finally, we need to do one more sort with the increment of one and it’s actually a basic insertion sort. The number of shifting operations that we need to perform to sort a list is now smaller than it would be the case if we didn’t do the first iteration:

最后，我们需要再做一次增量为1的排序，这实际上是一个基本的插入排序。现在我们需要执行的移位操作的数量比我们不做第一次迭代的情况下要少：

one more sort

2.3. Choosing the Gap Sequences

2.3.选择空隙序列

As we mentioned, the shell sort has a unique way of choosing gap sequences. This is a difficult task and we should be careful not to choose too few or too many gaps. More details can be found in the most proposed gap sequences listing.

正如我们所提到的，壳排序有一种独特的方式来选择间隙序列。这是一项困难的任务，我们应该注意不要选择太少或太多间隙。更多细节可以在最建议的间隙序列列表中找到。。

3. Implementation

3.实施

Let’s now take a look at the implementation. We’ll use Shell’s original sequence for interval increments:

现在让我们来看看实现的情况。我们将使用Shell的原始序列来实现区间增量。

N/2, N/4, …, 1 (continuously dividing by 2)

The implementation itself is not too complex:

实施本身并不太复杂。

public void sort(int arrayToSort[]) {
    int n = arrayToSort.length;

    for (int gap = n / 2; gap > 0; gap /= 2) {
        for (int i = gap; i < n; i++) {
            int key = arrayToSort[i];
            int j = i;
            while (j >= gap && arrayToSort[j - gap] > key) {
                arrayToSort[j] = arrayToSort[j - gap];
                j -= gap;
            }
            arrayToSort[j] = key;
        }
    }
}

We first created a gap sequence with a for loop and then did the insertion sort for each gap size.

我们首先用for循环创建了一个间隙序列，然后对每个间隙大小进行插入排序。

Now, we can easily test our method:

现在，我们可以轻松地测试我们的方法。

@Test
public void givenUnsortedArray_whenShellSort_thenSortedAsc() {
    int[] input = {41, 15, 82, 5, 65, 19, 32, 43, 8};
    ShellSort.sort(input);
    int[] expected = {5, 8, 15, 19, 32, 41, 43, 65, 82};
    assertArrayEquals("the two arrays are not equal", expected, input);
}

4. Complexity

4.复杂性

Generally, the Shell sort algorithm is very efficient with medium-sized lists. The complexity is difficult to determine since it depends a lot on the gap sequence, but the time complexity varies between O(N) and O(N^2).

一般来说，壳牌排序算法对于中等规模的列表是非常有效的。复杂度很难确定，因为它在很大程度上取决于间隙序列，但时间复杂度在O(N)和O(N^2)之间变化。

The worst-case space complexity is O(N) with O(1) auxiliary space.

最坏情况下的空间复杂度是O(N)与O(1)辅助空间。

5. Conclusion

5.总结

In this tutorial, we described Shell sort and illustrated how we can implement it in Java.

在本教程中，我们描述了Shell排序，并说明了我们如何在Java中实现它。

As usual, the entire code could be found over on GitHub.

像往常一样，整个代码可以在GitHub上找到超过。