Bagaimana untuk menulis algoritma jenis baldi dalam Python?

Bagaimana untuk menulis algoritma isihan baldi dalam Python?

Pengenalan:
Isih Baldi ialah algoritma pengisihan bukan perbandingan Prinsipnya ialah membahagikan elemen untuk diisih ke dalam baldi yang berbeza, kemudian mengisih elemen dalam setiap baldi, dan akhirnya menyusun semua baldi urutan untuk mendapatkan hasil yang disusun. Pengisihan baldi sesuai untuk situasi di mana unsur yang hendak diisih berada dalam julat tertentu dan diagihkan secara sekata Kerumitan masa ialah O(n+k), n mewakili bilangan elemen yang akan diisih dan k mewakili bilangan baldi.

Langkah khusus:

1. Tentukan nilai_min minimum dan nilai_maks maksimum unsur-unsur yang hendak diisih
2. Kira bilangan baldi_bilangan daripada baldi untuk dibahagikan;
3. Buat baldi_bilangan, diwakili oleh senarai, dan setiap baldi dimulakan ke senarai kosong
4. Letakkan elemen untuk diisih ke dalam baldi yang sepadan baldi mengikut peraturan Dalam contoh ini, kami akan membahagikan elemen dengan (nilai_maks-min_nilai+1), kemudian bulatkan, dan kemudian tolak nilai minimum untuk mendapatkan subskrip baldi
5. Isih elemen dalam setiap bukan- baldi kosong, dan anda boleh menggunakan sebarang algoritma pengisihan;
6. Tuangkan semua baldi untuk mendapatkan hasil yang disusun.

Pelaksanaan kod:

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

Ujian:

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]

Ringkasan:
Isih baldi ialah algoritma pengisihan yang mudah dan berkesan yang boleh mencapai kerumitan masa linear apabila elemen diagihkan secara sama rata. Walau bagaimanapun, kelemahan pengisihan baldi ialah ia mengambil ruang memori tambahan, yang mungkin tidak boleh digunakan apabila penggunaan memori adalah besar. Dalam aplikasi praktikal, adalah penting untuk memilih algoritma pengisihan yang sesuai berdasarkan pengedaran elemen untuk diisih.

Atas ialah kandungan terperinci Bagaimana untuk menulis algoritma jenis baldi dalam Python?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!