Comment écrire l'algorithme de tri Hill en Python ?

Comment écrire l'algorithme de tri Hill en Python ?

Shell Sort est un algorithme de tri par insertion amélioré qui déplace les éléments en comparant les éléments à un certain intervalle, réduisant ainsi le nombre de déplacements. L'idée principale du tri Hill est de regrouper les éléments à trier selon un certain intervalle, puis d'effectuer un tri par insertion sur chaque groupe, en réduisant continuellement l'intervalle jusqu'à ce qu'il soit 1, et enfin d'effectuer un tri par insertion complet.

Ci-dessous, nous présenterons en détail comment écrire l'algorithme de tri Hill en Python.

Tout d’abord, nous devons écrire une fonction pour implémenter le tri par insertion. L'idée principale du tri par insertion est d'insérer l'élément actuel dans la séquence précédente déjà triée.

def insertion_sort(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key

Ensuite, nous écrivons une fonction de tri Hill qui reçoit une liste à trier en paramètre.

def shell_sort(arr):
    n = len(arr)
    gap = n // 2  # 初始间隔设置为列表长度的一半
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap = gap // 2  # 缩小间隔

Enfin, nous écrivons une fonction de test pour vérifier l'exactitude du tri Hill.

def test_shell_sort():
    arr = [12, 34, 55, 23, 8, 17, 45, 91]
    shell_sort(arr)
    assert arr == [8, 12, 17, 23, 34, 45, 55, 91]
    print("希尔排序测试通过！")

if __name__ == "__main__":
    test_shell_sort()

Après avoir exécuté la fonction de test, si aucune erreur n'est signalée et que l'invite "Test de tri Hill réussi !" est affichée, cela signifie que l'implémentation du tri Hill est correcte.

La complexité temporelle du tri Hill est liée à la séquence d'intervalles sélectionnée. La meilleure séquence d'intervalles n'a pas encore été trouvée. La complexité temporelle moyenne du tri Hill est d'environ O(n^1,3), et la complexité temporelle dans le pire des cas est d'environ O(n^2).

Le tri par colline est un algorithme de tri efficace. Par rapport au tri par insertion, il peut trier partiellement les éléments du tri par insertion au début, réduisant ainsi les opérations de comparaison et de déplacement ultérieures et améliorant l'efficacité du tri. Si vous souhaitez trier une liste rapidement, essayez d'utiliser l'algorithme de tri Hill.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!