Bagaimana untuk menulis algoritma pengisihan Hill dalam Python?

Bagaimana cara menulis algoritma pengisihan Hill dalam Python?

Shell Sort ialah algoritma isihan sisipan yang dipertingkatkan yang menggerakkan elemen dengan membandingkan elemen pada selang waktu tertentu, dengan itu mengurangkan bilangan pergerakan. Idea teras pengisihan Hill adalah untuk mengumpulkan elemen yang akan diisih mengikut selang tertentu, dan kemudian melakukan isihan sisipan pada setiap kumpulan, secara berterusan mengurangkan selang sehingga 1, dan akhirnya melakukan isihan sisipan yang lengkap.

Di bawah ini kami akan memperkenalkan secara terperinci cara menulis algoritma pengisihan Hill dalam Python.

Pertama, kita perlu menulis fungsi untuk melaksanakan isihan sisipan. Idea teras jenis sisipan adalah untuk memasukkan elemen semasa ke dalam urutan sebelumnya yang telah diisih.

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

Seterusnya, kami menulis fungsi isihan Bukit yang menerima senarai untuk diisih sebagai parameter.

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  # 缩小间隔

Akhir sekali, kami menulis fungsi ujian untuk mengesahkan ketepatan pengisihan Bukit.

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()

Selepas menjalankan fungsi ujian, jika tiada ralat dilaporkan dan gesaan "Ujian isihan bukit lulus adalah output, ini bermakna pelaksanaan isihan Bukit adalah betul.

Kerumitan masa pengisihan Bukit berkaitan dengan jujukan selang yang dipilih. Jujukan selang terbaik belum ditemui lagi. Purata kerumitan masa bagi jenis Bukit ialah kira-kira O(n^1.3), dan kerumitan masa terburuk ialah kira-kira O(n^2).

Pengisihan bukit ialah algoritma pengisihan yang cekap Berbanding dengan pengisihan sisipan, ia boleh menyusun sebahagian elemen pengisihan sisipan pada permulaan, dengan itu mengurangkan operasi perbandingan dan pergerakan seterusnya serta meningkatkan kecekapan pengisihan. Jika anda ingin mengisih senarai dengan cepat, cuba gunakan algoritma isihan Hill.

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