8.1 Khái niệm về Merge Sort
Thuật toán Merge Sort là một thuật toán sắp xếp hiệu quả, ổn định và dựa trên so sánh, sử dụng phương pháp "chia để trị" để sắp xếp các phần tử. Thuật toán chia mảng thành hai nửa, đệ quy sắp xếp từng nửa, rồi hợp nhất các nửa đã sắp xếp thành một mảng đã sắp xếp hoàn chỉnh.
Nguyên tắc hoạt động:
Chia:
- Chia mảng gốc thành hai phần để tạo thành hai mảng con.
- Lặp lại quá trình cho từng mảng con cho đến khi mỗi mảng con chỉ còn một phần tử (hoặc rỗng).
Hợp nhất:
- Hợp nhất hai mảng con liền kề thành một mảng đã sắp xếp.
- Lặp lại quá trình hợp nhất cho đến khi có được một mảng đã sắp xếp duy nhất.
Độ phức tạp thời gian và không gian của Merge Sort
Độ phức tạp thời gian:
- Trường hợp xấu nhất:
O(n log n) - Trường hợp trung bình:
O(n log n) - Trường hợp tốt nhất:
O(n log n)
Độ phức tạp không gian:
O(n) — cần thêm bộ nhớ để lưu trữ tạm các mảng con.
8.2 Phương pháp Merge Sort từ trên xuống
Chuỗi ban đầu được chia đệ quy thành các nửa cho đến khi có được các chuỗi con với 1 phần tử. Từ các chuỗi con đó, tạo thành các cặp đã sắp xếp bằng phương pháp hợp nhất, rồi đến các bộ bốn đã sắp xếp và cứ thế tiếp tục.
Hãy xem ví dụ:
Chia chuỗi thành 2 nửa (đệ quy cho đến khi có được các cặp).
Sắp xếp từng chuỗi con bằng phương pháp hợp nhất và có được một chuỗi đã sắp xếp.
8.3 Thực thi thuật toán Merge Sort
Đây là lúc mà đệ quy trở nên hữu ích! Đây là một thuật toán rất tốt và nhanh so với các thuật toán trước. Nó chia mảng thành đôi, sắp xếp từng phần riêng lẻ, rồi nhanh chóng hợp nhất các phần đã sắp xếp lại.
Đây là cách mã của nó trông như thế:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Tìm trung điểm của mảng
left_half = arr[:mid] # Chia mảng thành hai phần
right_half = arr[mid:]
merge_sort(left_half) # Đệ quy sắp xếp nửa trái
merge_sort(right_half) # Đệ quy sắp xếp nửa phải
i = j = k = 0
# Hợp nhất các phần đã sắp xếp
while i < len(left_half) and j < len(right_half):
if left_half[i] < right_half[j]:
arr[k] = left_half[i]
i += 1
else:
arr[k] = right_half[j]
j += 1
k += 1
# Kiểm tra phần tử còn lại
while i < len(left_half):
arr[k] = left_half[i]
i += 1
k += 1
while j < len(right_half):
arr[k] = right_half[j]
j += 1
k += 1
return arr
# Ví dụ sử dụng:
arr = [38, 27, 43, 3, 9, 82, 10]
sorted_arr = merge_sort(arr)
print("Mảng đã sắp xếp:", sorted_arr)
# Output: Mảng đã sắp xếp: [3, 9, 10, 27, 38, 43, 82]
Điểm mấu chốt ở đây:
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2 # Tìm trung điểm của mảng
left_half = arr[:mid] # Chia mảng thành hai phần right_half = arr[mid:]
merge_sort(left_half) # Đệ quy sắp xếp nửa trái
merge_sort(right_half) # Đệ quy sắp xếp nửa phải
Đây là những gì đang diễn ra:
Chúng ta tìm trung điểm của mảngChia mảng thành 2 phầnSắp xếp từng phần một cách riêng biệt
Phương pháp này cực kỳ tăng tốc độ xử lý thuật toán.
GO TO FULL VERSION