Shell Sort

Idea

Shell Sort (gap-based insertion) improves insertion sort: group elements by a gap, sort each group by insertion, shrink the gap, and finish with a final insertion sort when gap = 1.

希尔排序演示

231218345423

当前增量 gap: 4

下一步

Algorithm

1. Choose initial gap $gap$ and group the array.
2. Insertion sort within each group.
3. Shrink $gap$ and repeat grouping + sorting.
4. When $gap=1$, do a final insertion sort.

Pseudo-code:

for gap = n/2; gap >= 1; gap = gap/2:
    for i = gap to n-1:
        key = A[i]
        j = i - gap
        while j >= 0 and A[j] > key:
            A[j+gap] = A[j]
            j = j - gap
        A[j+gap] = key

Complexity

• Best: $O(n\log n)$
• Worst: $O(n^2)$ (depends on gap sequence)
• Space: $O(1)$
• Stability: unstable

Exercises

Exercise 1

Summarize the idea of Shell sort and how it differs from straight insertion sort.

参考答案

思路：分组插入 vs 直接插入。

步骤：

1. 希尔先分组插入，逐步缩小增量
2. 直接插入每次只插一个

答案：希尔分组插入，效率更高。

Exercise 2

What are Shell sort’s time and space complexities?

参考答案

思路：复杂度与空间。

步骤：

1. 时间复杂度 $O(n\log n)$（最好），$O(n^2)$（最坏）
2. 空间复杂度 $O(1)$

答案：时间 $O(n\log n)$~$O(n^2)$，空间 $O(1)$。

PreviousSelection SortSelection sort basics, algorithm flow, complexity, and practice. NextQuick SortQuick sort fundamentals, algorithm flow, complexity, and practice.