Bagaimana untuk melaksanakan algoritma pengisihan gabungan menggunakan Python?

Bagaimana untuk menggunakan Python untuk melaksanakan algoritma isihan gabungan?

Merge Sort ialah algoritma pengisihan biasa yang menggunakan idea ​​bahagi dan takluk untuk membahagikan masalah besar kepada berbilang masalah kecil untuk diselesaikan, dan kemudian menggabungkan penyelesaian kepada masalah kecil. Kerumitan masa isihan gabungan ialah O(nlogn) dan sesuai untuk set data pelbagai saiz.

Di bawah ini kami akan memperkenalkan secara terperinci cara menggunakan Python untuk melaksanakan algoritma isihan gabungan dan memberikan contoh kod khusus.

Idea asas pengisihan gabungan ialah membahagikan tatasusunan untuk diisih kepada dua sub-tatasusunan, kemudian mengisih setiap sub-tatasusunan secara berasingan, dan akhirnya menggabungkan sub-tatasusunan yang telah diisih. Langkah-langkah khusus adalah seperti berikut:

1. Seruskan bahagikan tatasusunan untuk diisih kepada dua subtatasusunan sehingga setiap subtatasusunan hanya mempunyai satu elemen. Ini boleh dicapai melalui rekursi.
2. Isih setiap sub-tatasusunan, anda boleh menggunakan rekursi atau lelaran.
3. Gabungkan subarray yang diisih untuk membentuk tatasusunan tertib terakhir.

Berikut ialah kod contoh untuk melaksanakan pengisihan gabungan dalam Python:

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

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

# 测试
arr = [5, 2, 8, 1, 9, 3]
sorted_arr = merge_sort(arr)
print(sorted_arr)

Hasil larian ialah: [1, 2, 3, 5, 8, 9], Iaitu, tatasusunan disusun mengikut tertib dari kecil ke besar.

Dalam kod di atas, fungsi merge digunakan untuk menggabungkan dua subbarray yang diisih. Mula-mula, kami mentakrifkan tatasusunan kosong hasil untuk menyimpan tatasusunan tercantum yang digabungkan. Kemudian, gunakan dua penuding i dan j untuk menunjuk ke kedudukan permulaan subarray kiri dan subarray kanan masing-masing, dan bandingkan saiz elemen subarray kiri dan kanan. Jika unsur subarray kiri lebih kecil daripada unsur subarray kanan, tambahkan unsur subarray kiri pada tatasusunan result dan tambahkan i dengan 1; , tambahkan elemen subarray kanan pada tatasusunan result Elemen ditambahkan pada tatasusunan result dan j ditambah sebanyak 1. Akhir sekali, tambahkan elemen yang tinggal dalam subarray kiri atau subarray kanan pada tatasusunan result. Akhir sekali, fungsi merge mengembalikan tatasusunan tersusun yang digabungkan. merge函数用于合并两个已排序的子数组。首先，我们定义一个空数组result用于存放合并后的有序数组。然后，使用两个指针i和j分别指向左子数组和右子数组的起始位置，并比较左右子数组的元素大小。如果左子数组的元素小于右子数组的元素，将左子数组的元素加入result数组，并将i自增1；否则，将右子数组的元素加入result数组，并将j自增1。最后，将左子数组或右子数组中剩余的元素加入result数组。最后，merge函数返回合并后的有序数组。

merge_sort函数用于归并排序的递归操作。对于一个给定的待排序数组arr，首先判断数组的长度是否小于等于1，如果是，则直接返回该数组。否则，通过len(arr) // 2找到数组的中间位置，并将数组拆分为两个子数组left和right。然后，分别对left和right递归调用merge_sort

Fungsi merge_sort digunakan untuk operasi rekursif isihan gabungan. Untuk tatasusunan arr yang diberikan untuk diisih, tentukan dahulu sama ada panjang tatasusunan itu kurang daripada atau sama dengan 1, dan jika ya, kembalikan tatasusunan secara terus. Jika tidak, cari kedudukan tengah tatasusunan melalui len(arr) // 2 dan pisahkan tatasusunan kepada dua subarray kiri dan kanan. Kemudian, panggil secara rekursif fungsi merge_sort di left dan kanan untuk menggabungkan dua subarray diisih yang diperoleh dan mengembalikan tatasusunan Tertib yang digabungkan.

Di atas ialah langkah khusus dan contoh kod menggunakan Python untuk melaksanakan algoritma isihan gabungan. Saya harap ia akan membantu pembaca memahami algoritma isihan gabungan. #🎜🎜#

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