Comment écrire un algorithme de tri par bucket en Python ?

Comment écrire un algorithme de tri par bucket en Python ?

Introduction :
Bucket Sort est un algorithme de tri non comparatif. Son principe est de diviser les éléments à trier en différents buckets, puis de trier les éléments dans chaque bucket, et enfin de trier tous les buckets. séquence pour obtenir le résultat trié. Le tri par compartiments convient aux situations où les éléments à trier se situent dans une certaine plage et sont uniformément répartis. La complexité temporelle est O(n+k), n représente le nombre d'éléments à trier et k représente le nombre de compartiments.

Étapes spécifiques :

1. Déterminez la valeur min_value minimale et la valeur max_value maximale des éléments à trier ;
2. Calculez le nombre de buckets bucket_num La méthode la plus simple consiste à diviser la plage des éléments triés en parties égales en fonction du nombre. de buckets à diviser ;
3. Créez des buckets bucket_num, représentés par des listes, et chaque bucket est initialisé à une liste vide
4. Mettez les éléments à trier dans les buckets correspondants. buckets selon les règles.Dans cet exemple, nous diviserons les éléments par (max_value-min_value+1), puis arrondirons, puis soustrairons la valeur minimale pour obtenir l'indice du bucket
5. Trier les éléments dans chaque non-; videz le seau, et vous pouvez utiliser n'importe quel algorithme de tri ;
6. Versez tous les seaux afin d'obtenir les résultats triés ;

Implémentation du code :

def bucket_sort(arr):
    min_value, max_value = min(arr), max(arr)
    bucket_num = len(arr)
    bucket_size = (max_value - min_value + 1) // bucket_num + 1  # 计算桶的大小，加1是为了包含最大值
    buckets = [[] for _ in range(bucket_num)]  # 创建桶

    # 将元素放入桶中
    for val in arr:
        index = (val - min_value) // bucket_size  # 计算桶的下标
        buckets[index].append(val)

    # 对每个桶中的元素进行排序
    for bucket in buckets:
        bucket.sort()

    # 将所有桶中的元素依次取出
    sorted_arr = []
    for bucket in buckets:
        sorted_arr.extend(bucket)

    return sorted_arr

Test :

arr = [4, 1, 9, 6, 3, 7, 5, 8, 2]
sorted_arr = bucket_sort(arr)
print(sorted_arr)  # 输出：[1, 2, 3, 4, 5, 6, 7, 8, 9]

Résumé :
Le tri par seau est un algorithme de tri simple et efficace qui peut atteindre une complexité temporelle linéaire lorsque les éléments sont répartis uniformément. Cependant, l’inconvénient du tri par compartiments est qu’il occupe de l’espace mémoire supplémentaire, ce qui peut ne pas être applicable lorsque la consommation de mémoire est importante. Dans les applications pratiques, il est essentiel de choisir un algorithme de tri approprié basé sur la distribution des éléments à trier.

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!