Bagaimana untuk melaksanakan pengisihan gabungan menggunakan Python

Isih Cantum ialah algoritma pengisihan klasik Idea terasnya ialah membahagikan tatasusunan untuk diisih kepada beberapa sub-tatasusunan, mengisih sub-tatasusunan ini dan akhirnya menggabungkan sub-tatasusunan ke dalam tatasusunan tertib. Isih Gabung ialah algoritma pengisihan yang agak cekap dengan kerumitan masa O(nlogn).

Dalam artikel ini, kami akan menerangkan cara melaksanakan isihan gabungan dalam Python.

1. Idea melaksanakan merge sort

Idea untuk melaksanakan merge sort merangkumi dua bahagian iaitu divide dan conquer dan merge. Langkah pelaksanaan khusus adalah seperti berikut:

1) Bahagikan tatasusunan untuk diisih kepada dua bahagian, dan isih bahagian kiri dan kanan secara rekursif; ke dalam Tatasusunan tertib.

Gunakan Python untuk melaksanakan divide and conquer

2. Divide and conquer ialah idea teras merge sort Kita perlu melaksanakan bahagian divide and conquer terlebih dahulu.

Kod adalah seperti berikut:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

Dalam fungsi ini, kita mula-mula menentukan sama ada panjang tatasusunan kurang daripada atau sama dengan 1, kemudian terus mengembalikan tatasusunan. Jika tidak, kita perlu membahagikan tatasusunan kepada dua, menyusun secara rekursif bahagian kiri dan kanan masing-masing, dan akhirnya menggabungkan bahagian kiri dan kanan yang disusun.

2.1 Melaksanakan Penggabungan

Atas dasar pembahagian dan penaklukan, kita perlu melaksanakan bahagian yang digabungkan.

Kodnya adalah seperti berikut:

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

Dalam fungsi ini, kita mula-mula memulakan penunjuk i dan j, yang menghala ke elemen untuk dibandingkan di bahagian kiri dan kanan masing-masing. Kemudian kami terus membandingkan elemen kiri dan kanan, tambah elemen yang lebih kecil pada senarai hasil, dan gerakkan penunjuk ke kanan. Akhir sekali, kami juga menambah semua elemen yang tinggal pada senarai yang terhasil supaya kami berakhir dengan tatasusunan yang diisih.

Kod lengkap

Menggabungkan bahagi dan menakluk serta menggabungkan bahagian, kod lengkap adalah seperti berikut:

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_arr = merge_sort(arr[:mid])
    right_arr = merge_sort(arr[mid:])
    return merge(left_arr, right_arr)

def merge(left_arr, right_arr):
    i, j = 0, 0
    result = []
    while i < len(left_arr) and j < len(right_arr):
        if left_arr[i] < right_arr[j]:
            result.append(left_arr[i])
            i += 1
        else:
            result.append(right_arr[j])
            j += 1
    result += left_arr[i:]
    result += right_arr[j:]
    return result

Ujian

Untuk mengesahkan bahawa kod isihan cantuman kami adalah betul, kami perlu mengujinya.

Kod adalah seperti berikut:

arr = [5, 3, 8, 6, 4, 7, 2, 1]
print(merge_sort(arr))

Hasil output ialah:

[1, 2, 3, 4, 5, 6, 7, 8]

Ujian Keputusan menunjukkan bahawa kod isihan gabungan kami adalah betul.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan pengisihan gabungan menggunakan Python. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!