CodeGym /Các khóa học /Python SELF VI /Thuật toán Merge Sort

Thuật toán Merge Sort

Python SELF VI
Mức độ, Bài học
Có sẵn

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:

  1. Chúng ta tìm trung điểm của mảng
  2. Chia mảng thành 2 phần
  3. Sắ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.

2
Nhiệm vụ
Python SELF VI, mức độ, bài học
Đã khóa
Hợp nhất mảng
Hợp nhất mảng
2
Nhiệm vụ
Python SELF VI, mức độ, bài học
Đã khóa
Sắp xếp trộn
Sắp xếp trộn
Bình luận
TO VIEW ALL COMMENTS OR TO MAKE A COMMENT,
GO TO FULL VERSION