Data Structures Algorithms 简明教程

Shell Sort Algorithm

希尔排序是一种高效的排序算法，基于插入排序算法。该算法避免了插入排序情况下的大量移动，即当较小的值位于最右侧并且必须移动到最左侧时。

Shell sort is a highly efficient sorting algorithm and is based on insertion sort algorithm. This algorithm avoids large shifts as in case of insertion sort, if the smaller value is to the far right and has to be moved to the far left.

该算法对范围较广的元素使用插入排序，先对它们进行排序，再对间隔较小的元素进行排序。这种间距被称为 interval 。该间隔是根据克努斯公式计算的：

This algorithm uses insertion sort on a widely spread elements, first to sort them and then sorts the less widely spaced elements. This spacing is termed as interval. This interval is calculated based on Knuth’s formula as −

h = h * 3 + 1
where −
   h is interval with initial value 1

它针对中等规模的数据集具有相当高的效率，因为它的平均和最坏情况复杂度为 O(n)，其中 n 是项目的数量。

This algorithm is quite efficient for medium-sized data sets as its average and worst case complexity are of O(n), where n is the number of items.

Shell Sort Algorithm

以下是希尔排序的算法。

Following is the algorithm for shell sort.

1. Initialize the value of h.
2. Divide the list into smaller sub-list of equal interval h.
3. Sort these sub-lists using insertion sort.
4. Repeat until complete list is sorted.

Pseudocode

以下是希尔排序的伪代码。

Following is the pseudocode for shell sort.

procedure shellSort()
   A : array of items

   /* calculate interval*/
   while interval < A.length /3 do:
      interval = interval * 3 + 1
   end while

   while interval > 0 do:
      for outer = interval; outer < A.length; outer ++ do:

         /* select value to be inserted */
         valueToInsert = A[outer]
         inner = outer;

            /*shift element towards right*/
            while inner > interval -1 &&  A[inner - interval]
			>= valueToInsert do:
               A[inner] = A[inner - interval]
               inner = inner – interval
            end while

         /* insert the number at hole position */
         A[inner] = valueToInsert
         end for

   /* calculate interval*/
   interval = (interval -1) /3;
   end while
end procedure

Example

让我们考虑以下示例，了解希尔排序是如何工作的。我们使用在之前示例中使用过的同一个数组。为理解方便起见，我们采用 4 的间隔。创建一个虚拟子列表，其中包含所有位于 4 个位置间隔处的值。此处的这些值是 {35、14}、{33、19}、{42、27} 和 {10、14}

Let us consider the following example to have an idea of how shell sort works. We take the same array we have used in our previous examples. For our example and ease of understanding, we take the interval of 4. Make a virtual sub-list of all values located at the interval of 4 positions. Here these values are {35, 14}, {33, 19}, {42, 27} and {10, 14}