Isihan Gabung: Bahagi, Isih, Gabung
Laksanakan isihan gabung secara rekursif, jejaki pepohon bahagi-dan-takluk serta jelaskan sebabnya ia menjamin O(n log n) dalam semua keadaan.
Isihan Gabung: Bahagi, Isih, Gabung ialah pelajaran Persediaan Temu Duga Pengaturcaraan percuma di CoddyKit. Ini ialah pelajaran 2 daripada 4. Anda boleh membaca keseluruhan pelajaran di bawah secara percuma — kemudian berlatih secara praktikal dalam pelayar menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7. Pelajaran ini merupakan sebahagian daripada laluan pembelajaran Persediaan Temu Duga Pengaturcaraan, dan kemajuan anda disegerakkan merentas web serta aplikasi CoddyKit. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Intuisi Bahagi dan Takluk
Isihan gabung ialah algoritma bahagi dan takluk klasik: bahagikan tatasusunan kepada dua, isih setiap bahagian secara rekursif, kemudian gabungkan kedua-dua bahagian yang telah diisih menjadi satu hasil yang diisih. Pemerhatiannya ialah penggabungan dua tatasusunan yang telah diisih mengambil masa O(n) — jauh lebih murah daripada mengisih dari awal. Penguraian ini menghasilkan pepohon rekursi dengan log n aras, setiap satunya memerlukan kerja penggabungan O(n), lalu memberikan had optimum O(n log n) untuk pengisihan berasaskan perbandingan.
# High-level merge sort structure
def merge_sort(arr):
# Base case: 0 or 1 element already sorted
if len(arr) <= 1:
return arr
# Divide
mid = len(arr) // 2
left = merge_sort(arr[:mid]) # sort left half
right = merge_sort(arr[mid:]) # sort right half
# Conquer (merge)
return merge(left, right)
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))
# [3, 9, 10, 27, 38, 43, 82]Langkah Penggabungan Diterangkan
Untuk menggabungkan dua tatasusunan yang telah diisih: kekalkan dua penuding, satu untuk setiap bahagian. Bandingkan elemen hadapan; copy elemen yang lebih kecil ke output dan majukan penuding tersebut. Apabila salah satu bahagian habis, copy baki bahagian yang satu lagi terus ke output. Proses ini mengambil masa O(n) dan ruang O(n) untuk tatasusunan output. Langkah penggabungan ialah teras algoritma isihan gabung — fahaminya secara mendalam.
def merge(left, right):
result = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: # <= preserves stability
result.append(left[i])
i += 1
else:
result.append(right[j])
j += 1
# Append remaining elements
result.extend(left[i:])
result.extend(right[j:])
return result
print(merge([1,3,5,7], [2,4,6,8]))
# [1, 2, 3, 4, 5, 6, 7, 8]Pelaksanaan Lengkap Isihan Gabung
Menggabungkan pembahagian dan penggabungan: panggilan rekursif membahagikan masalah kepada separuh sehingga hanya elemen tunggal yang tinggal (yang sudah terisih secara jelas), kemudian panggilan penggabungan mencantumkannya semula. Setiap aras pepohon rekursi menggabungkan jumlah keseluruhan n elemen yang sama (yang diagihkan merentasi beberapa penggabungan). Kedalaman rekursi ialah log₂(n), lalu menghasilkan jumlah masa O(n log n) dan ruang tambahan O(n) untuk tatasusunan keluaran penggabungan, serta kedalaman timbunan panggilan O(log n).
def merge_sort_full(arr):
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_full(arr[:mid])
right = merge_sort_full(arr[mid:])
# Merge the two sorted halves
merged = []
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]: merged.append(left[i]); i += 1
else: merged.append(right[j]); j += 1
merged.extend(left[i:] + right[j:])
return merged
print(merge_sort_full([5,2,4,6,1,3,2,6]))
# [1, 2, 2, 3, 4, 5, 6, 6]Pepohon Rekursi Isihan Gabung
Bayangkan pepohon rekursi isihan gabung untuk n=8: Aras 0 mempunyai satu tatasusunan dengan 8 elemen; Aras 1 mempunyai dua tatasusunan dengan 4 elemen; Aras 2 mempunyai empat tatasusunan dengan 2 elemen; Aras 3 mempunyai lapan elemen tunggal (kes asas). Semasa bergerak semula ke atas, Aras 3→2 menggabungkan jumlah keseluruhan 8 elemen, Aras 2→1 menggabungkan jumlah keseluruhan 8 elemen, dan Aras 1→0 menggabungkan jumlah keseluruhan 8 elemen. Jadi, 3 aras × 8 elemen = 24 operasi ≈ 8 × log₂(8) = 24. Ini mengesahkan O(n log n).
# Trace the tree depth
level_work = []
def merge_sort_traced(arr, depth=0):
if depth >= len(level_work):
level_work.append(0)
if len(arr) <= 1:
return arr
mid = len(arr) // 2
left = merge_sort_traced(arr[:mid], depth+1)
right = merge_sort_traced(arr[mid:], depth+1)
level_work[depth] += len(arr) # track merge work
merged = sorted(left + right) # simplified merge
return merged
merge_sort_traced(list(range(8, 0, -1)))
for d, work in enumerate(level_work):
print(f'Level {d}: {work} elements merged')Isihan Gabung di Tempat
Isihan gabung rekursif standard memperuntukkan ruang tambahan O(n) untuk keluaran penggabungan. Isihan gabung di tempat memang wujud, tetapi rumit dan mempunyai faktor pemalar yang tinggi — jarang ditanya dalam temu duga. Soalan susulan temu duga yang biasa ialah: 'Bolehkah anda melaksanakan isihan gabung dengan ruang tambahan O(1)?' Jawapan yang betul: 'Secara teori, ya, tetapi pelaksanaan praktikal sama ada mengorbankan ruang O(n) atau menambah kerumitan; Timsort Python menggunakan ruang O(n) untuk penggabungan.'
# Bottom-up merge sort: iterative, avoids recursion stack
def merge_sort_bottomup(arr):
n = len(arr)
width = 1
while width < n:
for i in range(0, n, 2 * width):
left = arr[i:i+width]
right = arr[i+width:i+2*width]
# Merge and put back
merged = []
a, b = 0, 0
while a < len(left) and b < len(right):
if left[a] <= right[b]: merged.append(left[a]); a+=1
else: merged.append(right[b]); b+=1
merged += left[a:] + right[b:]
arr[i:i+len(merged)] = merged
width *= 2
return arr
print(merge_sort_bottomup([5,2,4,6,1,3]))
# [1, 2, 3, 4, 5, 6]Isihan Gabung Stabil
Isihan gabung adalah stabil: elemen yang sama dari separuh kiri sentiasa muncul sebelum elemen yang sama dari separuh kanan dalam keluaran yang digabungkan. Hal ini dijamin dengan menggunakan <= (bukan <) apabila mendahulukan elemen kiri. Kestabilan penting untuk pengisihan berbilang kunci. sorted() terbina dalam Python dan list.sort() menggunakan Timsort, yang juga stabil dan mempunyai kerumitan O(n log n), menjadikannya pilihan selamat untuk semua kod pengeluaran.
# Demonstrating stability: sort (value, original_index) pairs
items = [(3,'A'), (1,'B'), (3,'C'), (2,'D')]
# Sort by value only
result = merge_sort_full(items) # won't work directly
# Use Python's stable sort:
result = sorted(items, key=lambda x: x[0])
print(result)
# [(1,'B'),(2,'D'),(3,'A'),(3,'C')]
# 'A' comes before 'C' for value=3 (stable order)Gabungkan K Tatasusunan Terisih
Menggabungkan k tatasusunan terisih yang mengandungi jumlah keseluruhan n elemen boleh dilakukan dengan menggabungkan pasangan secara berulang kali (seperti kejohanan kalah mati), dengan masa O(n log k). Setiap aras penggabungan memproses n elemen, dan terdapat log k aras. Sebagai alternatif, gunakan timbunan minimum bersaiz k: masukkan elemen terkecil yang masih tinggal daripada setiap tatasusunan, keluarkan nilai minimum, kemudian masukkan elemen seterusnya daripada tatasusunan tersebut. Pendekatan timbunan juga mempunyai masa O(n log k), tetapi lebih cekap dari segi memori apabila k sangat besar.
import heapq
def merge_k_sorted(arrays):
result = []
heap = []
# Push first element from each array with array index
for i, arr in enumerate(arrays):
if arr:
heapq.heappush(heap, (arr[0], i, 0))
while heap:
val, arr_i, elem_i = heapq.heappop(heap)
result.append(val)
if elem_i + 1 < len(arrays[arr_i]):
next_val = arrays[arr_i][elem_i + 1]
heapq.heappush(heap, (next_val, arr_i, elem_i+1))
return result
arrs = [[1,4,7],[2,5,8],[3,6,9]]
print(merge_k_sorted(arrs)) # [1,2,3,4,5,6,7,8,9]Kira Inversi dengan Isihan Gabung
Mengira inversi (pasangan apabila a[i] > a[j] dan i < j) dalam O(n log n) menggunakan isihan gabung yang diubah suai. Semasa langkah penggabungan, apabila elemen daripada subtatasusunan kanan lebih kecil daripada elemen daripada subtatasusunan kiri, elemen itu membentuk inversi dengan setiap elemen yang masih tinggal dalam subtatasusunan kiri. Pada saat itu, tambahkan len(left) - i kepada kiraan.
def count_inversions(arr):
if len(arr) <= 1:
return arr, 0
mid = len(arr) // 2
left, l_inv = count_inversions(arr[:mid])
right, r_inv = count_inversions(arr[mid:])
merged = []
inversions = l_inv + r_inv
i = j = 0
while i < len(left) and j < len(right):
if left[i] <= right[j]:
merged.append(left[i]); i += 1
else:
merged.append(right[j]); j += 1
inversions += len(left) - i # all remaining left elements > right[j]
merged.extend(left[i:] + right[j:])
return merged, inversions
_, inv = count_inversions([3, 1, 2])
print(inv) # 2: (3,1) and (3,2)Isihan Gabung berbanding Isihan Pantas
Isihan gabung menjamin O(n log n) dalam semua keadaan, bersifat stabil, dan merupakan pilihan yang lebih baik untuk senarai terpaut serta pengisihan luaran. Isihan pantas mempunyai kes purata O(n log n) tetapi kes terburuk O(n²), dilakukan di tempat (ruang timbunan O(log n)), dan sering lebih pantas dalam amalan kerana kecekapan memori cache pada tatasusunan. sort terbina dalam Python menggunakan Timsort (varian isihan gabung) — sentiasa pilihan lalai yang tepat.
# Head-to-head complexity comparison:
# Algorithm | Best | Avg | Worst | Space | Stable
# Bubble sort | O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Insertion sort| O(n) | O(n^2) | O(n^2) | O(1) | Yes
# Merge sort | O(nlogn)| O(nlogn)| O(nlogn)| O(n) | Yes
# Quick sort | O(nlogn)| O(nlogn)| O(n^2) | O(logn)| No
# Heap sort | O(nlogn)| O(nlogn)| O(nlogn)| O(1) | No
print('Merge sort: stable, O(n log n) guaranteed, O(n) space')Isihan Luaran: Isihan Gabung pada Skala Besar
Isihan gabung ialah algoritma di sebalik pengisihan luaran (mengisih data yang terlalu besar untuk dimuatkan dalam RAM). Data dibaca dalam bahagian, setiap bahagian diisih dalam memori, dan bahagian-bahagian itu digabungkan daripada cakera. Langkah penggabungan membaca satu elemen pada satu-satu masa daripada setiap larian terisih, dengan hanya mengekalkan O(k) elemen dalam memori pada satu-satu masa (satu bagi setiap larian). Inilah sebabnya isihan gabung digunakan dalam pangkalan data, Hadoop MapReduce, dan algoritma pengisihan pita klasik.
# Simulated external sort: sort in chunks then merge
def external_sort(data, chunk_size):
chunks = []
for i in range(0, len(data), chunk_size):
chunk = sorted(data[i:i+chunk_size]) # sort in-memory
chunks.append(chunk)
print(f'Created {len(chunks)} sorted chunks')
# Merge all chunks
import heapq
heap = [(c[0], i, 0) for i, c in enumerate(chunks) if c]
heapq.heapify(heap)
result = []
while heap:
val, ci, ei = heapq.heappop(heap)
result.append(val)
if ei + 1 < len(chunks[ci]):
heapq.heappush(heap, (chunks[ci][ei+1], ci, ei+1))
return result
print(external_sort(list(range(20,0,-1)), 5)[:10])Ringkasan Isihan Gabung dan Petua Temu Duga
Dalam temu duga, melaksanakan isihan gabung dengan kemas menunjukkan pemahaman tentang rekursi, langkah penggabungan, dan pendekatan bahagi dan takluk. Soalan susulan yang biasa:
- Mengapa O(n log n), bukannya O(n²)? (log n aras × n kerja bagi setiap aras)
- Adakah ia stabil? (Ya, gunakan <= dalam penggabungan)
- Berapakah ruang yang diperlukan? (Tambahan O(n) + timbunan O(log n))
- Bolehkah anda melaksanakannya secara lelaran? (Ya, isihan gabung dari bawah ke atas)
- Bagaimanakah anda menggunakannya pada senarai terpaut? (Lebih mudah berbanding tatasusunan — tiada kos hirisan O(n); gunakan kaedah penuding perlahan-pantas untuk mencari titik tengah)
# One-shot merge sort for interview clarity:
def ms(a):
if len(a) <= 1: return a
m = len(a) // 2
l, r, res, i, j = ms(a[:m]), ms(a[m:]), [], 0, 0
while i < len(l) and j < len(r):
if l[i] <= r[j]: res.append(l[i]); i+=1
else: res.append(r[j]); j+=1
return res + l[i:] + r[j:]
print(ms([5,2,4,6,1,3])) # [1,2,3,4,5,6]Semakan Pantas
Uji pemahaman anda tentang konsep Struktur Data & Algoritma — Persediaan Temu Duga Pengekodan daripada pelajaran ini.
Imbas Kembali Pelajaran
Dalam pelajaran ini anda telah mempelajari: isihan gabung membahagikan tatasusunan pada titik tengah, mengisih setiap separuh secara rekursif, dan menggabungkan dua separuh yang telah diisih dalam O(n) — menghasilkan jumlah masa pelaksanaan O(n log n) merentasi log n aras rekursi, langkah penggabungan menggunakan <= untuk mengambil elemen kiri apabila nilainya sama, sekali gus menjamin kestabilan, dan isihan gabung ialah algoritma pilihan untuk senarai terpaut, pengisihan luaran, dan keadaan yang memerlukan kestabilan — manakala isihan pantas lebih sesuai untuk tatasusunan dalam memori apabila ruang terhad. Seterusnya, kita akan melaksanakan isihan pantas dan meneroka strategi pemilihan pangsi.
Pelajari Persediaan Temu Duga Pengaturcaraan dengan tutor kecerdasan buatan — percuma
Tulis dan jalankan kod sebenar dalam pelayar anda, dapatkan bantuan segera daripada tutor kecerdasan buatan yang tersedia 24/7, dan sambung semula dari tempat anda berhenti di web atau dalam aplikasi.
- Kursus
- 90
- Pelajaran
- 360
Soalan Lazim
Adakah pelajaran “Isihan Gabung: Bahagi, Isih, Gabung” percuma?
Ya — teks penuh “Isihan Gabung: Bahagi, Isih, Gabung” boleh dibaca secara percuma di web ini. Untuk berlatih secara interaktif menggunakan penyunting kod terbina dalam dan tutor kecerdasan buatan 24/7, serta membuka kunci baki kursus Persediaan Temu Duga Pengaturcaraan, tingkat taraf kepada CoddyKit PRO. Kursus Persediaan Temu Duga Pengaturcaraan merangkumi sejumlah 4 pelajaran.
Apakah yang akan saya pelajari dalam “Isihan Gabung: Bahagi, Isih, Gabung”?
Laksanakan isihan gabung secara rekursif, jejaki pepohon bahagi-dan-takluk serta jelaskan sebabnya ia menjamin O(n log n) dalam semua keadaan. Anda berlatih Persediaan Temu Duga Pengaturcaraan menggunakan kod praktikal yang dijalankan terus dalam pelayar, manakala tutor kecerdasan buatan 24/7 menjawab soalan anda semasa anda mengikuti pelajaran.
Adakah saya memerlukan pengalaman untuk memulakan Persediaan Temu Duga Pengaturcaraan?
Tiada pengalaman terdahulu diperlukan. Pembelajaran Persediaan Temu Duga Pengaturcaraan di CoddyKit disusun untuk pelajar daripada peringkat pemula hingga lanjutan, jadi anda boleh bermula di sini atau dari awal dan belajar mengikut kadar anda sendiri. Ini ialah pelajaran 2 daripada 4.
Berapa lamakah pelajaran “Isihan Gabung: Bahagi, Isih, Gabung” diambil?
Kebanyakan pelajaran CoddyKit mengambil masa kira-kira 5–10 minit. Setiap pelajaran ringkas dan interaktif, jadi anda boleh membuat kemajuan secara berterusan dan menyambung tepat dari tempat anda berhenti di web atau aplikasi.
Bolehkah saya menulis dan menjalankan kod dalam pelajaran Persediaan Temu Duga Pengaturcaraan ini?
Ya. Setiap pelajaran Persediaan Temu Duga Pengaturcaraan menyertakan penyunting kod terbina dalam, jadi anda boleh menulis dan menjalankan kod sebenar terus dalam pelayar serta menerima maklum balas kecerdasan buatan serta-merta — tanpa memerlukan persediaan setempat.
Semua pelajaran dalam kursus ini
- Isihan Buih dan Isihan Sisipan
- Isihan Gabung: Bahagi, Isih, Gabung
- Isihan Pantas dan Pemilihan Pangsi
- Isihan Tanpa Perbandingan dan sort() Python