Sắp xếp trộn (merge sort) trong Python
Chia đôi list, sắp xếp từng nửa bằng đệ quy rồi trộn lại: luôn là O(n log n).
- Chia đôi đệ quy bằng slicing
- Trộn hai list đã sắp xếp
- Chi phí thời gian và bộ nhớ
[3, 27, 38, 43]đã trộn[27, 38][38][27]
[3, 43][43][3]
Chia nhỏ rồi trộn lại
Sắp xếp trộn (merge sort) áp dụng chiến lược chia để trị (divide and conquer). Thuật toán chia danh sách thành hai nửa, sắp xếp từng nửa bằng cách gọi đệ quy, rồi trộn hai nửa đã sắp xếp thành một danh sách hoàn chỉnh. Đây là một trong những thuật toán sắp xếp hiệu quả và ổn định nhất.
Những điểm quan trọng
- List có 0 hoặc 1 phần tử đã được sắp xếp: đó là trường hợp cơ sở.
- Trộn hai list đã sắp xếp bằng cách lặp lại việc lấy giá trị nhỏ hơn ở đầu.
- Có khoảng log n tầng, mỗi tầng tốn n bước:
O(n log n). - Cần thêm
O(n)bộ nhớ cho các list được trộn.
Khi nào nên sử dụng?
- Rèn luyện tư duy giải quyết vấn đề và hiểu cách thuật toán hoạt động qua từng bước.
- Chọn được cách giải phù hợp khi cần xử lý nhiều dữ liệu hoặc cần chương trình chạy nhanh hơn.
- Chuẩn bị cho các kỳ thi, bài tập và phỏng vấn lập trình.
Mô phỏng Sắp xếp trộn (merge sort) trong Python
O(n log n)Nhấn Phát hoặc Từng bước để theo dõi từng phép so sánh và thay đổi dữ liệu.
Code ví dụ
def merge_sort(values):
if len(values) <= 1:
return values
middle = len(values) // 2
left = merge_sort(values[:middle])
right = merge_sort(values[middle:])
result = []
left_index = right_index = 0
while left_index < len(left) and right_index < len(right):
if left[left_index] <= right[right_index]:
result.append(left[left_index])
left_index += 1
else:
result.append(right[right_index])
right_index += 1
return result + left[left_index:] + right[right_index:]
print(merge_sort([38, 27, 43, 3, 9, 82, 10]))Kết quả khi chạy
[3, 9, 10, 27, 38, 43, 82]Giải thích code
Hàm đệ quy chia danh sách cho đến khi mỗi phần chỉ còn một phần tử, vì danh sách một phần tử luôn được coi là đã sắp xếp. Sau đó, vòng lặp while trộn hai danh sách con bằng cách liên tục lấy phần tử nhỏ hơn ở đầu mỗi danh sách. Thuật toán luôn chạy trong thời gian O(n log n) và cần thêm O(n) bộ nhớ.
Thay đổi giá trị và chạy chương trình bằng trình chạy Python online của CodeUtility mà không cần cài Python.
Bài tập mở rộng
Hãy thử chỉnh sửa code theo các gợi ý dưới đây. Tự thay đổi và quan sát kết quả sẽ giúp bạn hiểu bài sâu hơn nhiều so với chỉ đọc code.
- Thử với danh sách rỗng, danh sách chỉ có một phần tử hoặc có giá trị trùng lặp.
- In ra trạng thái sau mỗi bước để quan sát thuật toán hoạt động.
- Đo thời gian chạy với 100, 1.000 và 10.000 phần tử, rồi so sánh với một cách giải khác.
Luyện tập với thử thách
Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.
Tất cả thử thách