整理定义

中文名称：希尔排序

英文名称：shellsort

复述展开

希尔排序 (Shell Sort) 希尔排序是希尔 (Donald Shell) 于 1959 年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为递减增量排序算法，同时该算法是冲破 O(n²) 的第一批算法之一。

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录 “基本有序” 时，再对全体记录进行依次直接插入排序。

算法步骤我们来看下希尔排序的基本步骤，在此我们选择增量 gap=length/2，缩小增量继续以 gap = gap/2 的方式，这种增量选择我们可以用一个序列来表示，{n/2, (n/2)/2, …, 1}，称为增量序列。希尔排序的增量序列的选择与证明是个数学难题，我们选择的这个增量序列是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述： 1.选择一个增量序列 {t1, t2, …, tk}，其中 (ti>tj, i<j, tk=1)； 2.按增量序列个数 k，对序列进行 k 趟排序； 3.每趟排序，根据对应的增量 t，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

算法分析

稳定性：不稳定
时间复杂度：最佳：O(nlogn)，最差：O(n2) 平均：O(n^1.3)
空间复杂度：O(n)

class ShellSort:
    def shell_sort(self, nums):
        n = len(nums)
        gap = n // 2
        while gap > 0:
            for i in range(gap, n):
                current = i - gap
                insert_value = nums[i]
                while current >= 0 and insert_value < nums[current]:
                    # 调整需要插入的值，找到需要插入的位置，其到 current ~ i 统一右移
                    nums[current + gap] = nums[current]
                    current -= gap
                nums[current + gap] = insert_value
            gap //= 2
        return nums


if __name__ == '__main__':
    nums = [10, 13, 2, 33, 3, 4, 4, 7, 9]
    solution = ShellSort()
    print(solution.shell_sort(nums))

理解体会

希尔排序（Shell Sort）是一种基于插入排序的算法，由Donald Shell于1959年提出，因此得名。插入排序在几乎已经排序的数据集上表现良好，但在大规模乱序数据集上效率较低。希尔排序通过对数据进行预排序，使得插入排序可以工作在”几乎排序”的数据集上，从而提高效率。

算法概述

希尔排序的基本思想是将待排序的数据集分成多个子序列，然后对每个子序列进行插入排序。这些子序列是通过选择一个增量（通常是数据集大小的一半）来创建的，每个子序列包含原始数据集中相隔增量距离的元素。然后，增量被减半，重复上述过程，直到增量为1，此时进行一次完整的插入排序。

评价

希尔排序的性能取决于增量序列的选择。在最坏的情况下，希尔排序的时间复杂度可以达到O(n^2)，但是对于某些增量序列，时间复杂度可以降低到O(n^(3/2))，甚至更低。希尔排序是一种原地排序算法，不需要额外的存储空间，空间复杂度为O(1)。然而，希尔排序不是稳定的排序算法，因为相等的元素可能会因为分组而改变相对顺序。

使用场景

希尔排序适用于中等大小的数据集。由于其相对简单的实现和良好的平均性能，它在一些需要快速原地排序且不需要稳定性的场景中是一个很好的选择。例如，嵌入式系统和老旧系统，这些系统可能没有足够的资源来执行更复杂的排序算法。

总的来说，希尔排序是一种有效的排序算法，尤其适用于中等大小的数据集。虽然它在最坏的情况下可能不如其他更复杂的排序算法，但是由于其简单的实现和在平均情况下的良好性能，它仍然是一种有用的排序工具。