<jupyter_start><jupyter_text>希尔排序(Shell Sort)>希尔排序属于插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本,>该方法的基本思想是：先将整个待排元素序列分割成若干个子序列>（由相隔某个“增量”的元素组成的）分别进行直接插入排序，>然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，>再对全体元素进行一次直接插入排序。因为直接插入排序在元素基本有序的情况下>（接近最好情况），效率是很高的，因此希尔排序在时间效率比直接插入排序有较大提高。 算法原理1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1(增量的取法：第一次增量的取法为： d=count/2; 第二次增量的取法为: d=(count/2)/2; 最后一直到: d=1;)；2. 按增量序列个数k，对序列进行k 趟排序；3. 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。 演示动画![希尔排序](/Sorting/image/shell_sort.gif)<jupyter_code>from typing import List

def shell_sort(arr:List[int]):
    """
    希尔排序
    :param arr: 待排序的List
    :return: 希尔排序是就地排序(in-place)
    """
    length = len(arr)
    dist = length // 2
    
    while dist > 0:
        for i in range(dist, length):
            temp = arr[i]
            j = i
            while j >= dist and temp < arr[j-dist]:
                arr[j] = arr[j-dist]
                j -= dist
            arr[j] = temp
        dist //= 2
if __name__ == '__main__':
    import random
    random.seed(54)
    arr = [random.randint(0,100) for _ in range(10)]
    print("原始数据：", arr)
    shell_sort(arr)
    print("希尔排序结果：", arr)<jupyter_output>原始数据： [17, 56, 71, 38, 61, 62, 48, 28, 57, 42]
希尔排序结果： [17, 28, 38, 42, 48, 56, 57, 61, 62, 71]
{'fraction_non_alphanumeric': 0.14972847168347556, 'fraction_numerical': 0.04809930178432894, 'mean_word_length': 3.463667820069204, 'pattern_counts': {'":': 0, '<': 5, '<?xml version=': 0, '>': 13, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 4, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '1', 'dir': 'jupyter-structured-clean-dedup', 'id': '344139', 'license': 'MIT', 'n_tokens_mistral': 820, 'n_tokens_neox': 874, 'n_words': 94, 'path': 'Sorting/shell_sort.ipynb', 'repo_name': 'lb971216008/Use-Python-to-Achieve', 'size': '1289'}