Data Structures Algorithms 简明教程

Shell Sort Algorithm

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

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

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

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

Shell Sort Algorithm

以下是希尔排序的算法。

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

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

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