Trong khoa học máy tính, thuật toán MERG SORT (sắp xếp trộn) là một thuật toán được sử dụng để sắp xếp các danh sách (hoặc bất kỳ cấu trúc dữ liệu nào có thể truy cập tuần tự) theo một trật tự nào đó.Nó được xếp vào thể loại sắp xếp so sánh.Thuật toán này là một ví dụ tương đối điển hình của lối thuật toán chia để trị do John von Neumann đưa ra lần đầu năm 1945.

Bạn đang xem: Merge sort là gì

*
Thuật toán Merge Sort (Sắp xếp trộn)
Thuật toán Merge Sort là một trong những thuật toán có độ phức tạp ở mức trung bình và cùng sử dùng phương pháp chia để trị giống thuật toán sắp xếp nhanh Quick Sort.Thuật toán này không chỉ áp dụng trong sắp xếp mà còn ở nhiều bài toán khác.Ý tưởng của giải thuật này bắt nguồn từ việc trộn 2 danh sách đã sắp xếp thành 1 danh sách mới cũng được sắp xếp.Giả sử có hai danh sách đã được sắp xếp a<1 ... m> và b<1 ... n>.Ta có thể trộn chúng lại thành một danh sách mới c<1 ... m+n> được sắp xếp theo cách sau:So sánh hai phần tử đứng đầu của hai danh sách, lấy phần tử nhỏ hơn cho vào danh sách mới. Tiếp tục như vậy cho tới khi một trong hai danh sách là rỗng.Khi một trong hai danh sách là rỗng ta lấy phần còn lại của danh sách kia cho vào cuối danh sách mới.Độ phức tạp thuật toán: O(nlog(n))
Để giúp bạn hình dung rõ hơn, đây là sơ đồ minh họa tiến trình từng bước của thuật toán Merge sort áp dụng cho mảng {25, 30, 45, 6, 11, 90, 15}

Xem thêm: Thể Loại:Vũ Khí Khủng Trong Blade & Soul, Theo Anh Em, Ngoại Hình Vũ

*
Sơ đồ minh họa thuật toán Merge Sort
Nếu nhìn kỹ hơn vào sơ đồ này, chúng ta có thể thấy:Mảng ban đầu được lặp lại hành động chia cho tới khi kích thước các mảng sau chia là 1.Khi kích thước các mảng con là 1, tiến trình gộp sẽ bắt đầu.Thực hiện gộp lại các mảng này cho tới khi hoàn thành và chỉ còn một mảng đã sắp xếp.
Như các bài chia sẻ trước, chung ta đã có ý tưởng và giải thuật rồi. Bây giờ hãy cùng mình triển khai thuật toán Merge sort này trong Java xem như thế nào nhé.
Merge Sort là một trong những thuật toán sắp xếp nhanh được sử dụng rộng rãi.Giả sử có một máy tính giải được 109 bài toán trong 1 giây:Trong trường hợp đó, để sắp xếp một dãy số gồm 106 số thì Merge Sort tốn chưa tới 1 giâyNgoài ra, Merge Sort còn có tốc độ ổn định.Vẫn là một máy tính giải được 109 bài toán trong 1 giây:Trong khi đó nếu ta dùng Quick Sort sắp xếp 1 dãy chứa 106 số thì vẫn có trường hợp ta phải chờ 1000 giây để sắp xếp xongCòn Merge Sort thì luôn luôn chưa tới 1 giây.Như bạn thấy đó, sử dụng đúng thuật toán mang lại hiệu quả cực kỳ lớn.> Đây cũng chính là điểm khác nhau của Lập trình viên "THƯỜNG" và Lập trình viên "GIỎI". Nếu bạn là người mới và muốn trở thành một Lập trình viên giỏi thì hãy tham gia HỌC LẬP TRÌNH (Full Stack) ngay hôm nay!Không chỉ mang lại tốc độ cực kỳ tốt, Merge Sort còn giữ được thứ tự của các phần tử bằng nhau sau khi sắp xếp.Chẳng hạn như khi ta cần sắp xếp một mảng gồm các điểm theo trong hệ tọa độ Oxy theo chiều tăng dần của hoành độ x, nếu hoành độ bằng nhau thì sắp tăng dần theo tung độ y.Trong trường hợp đó, ta chỉ cần dùng Merge Sort sắp xếp tung độ sau đó lại dùng Merge Sort sắp xếp hoành độ.Thuật toán Merge sort là một giải thuật sắp xếp mà có thời gian thực hiện là O(NlogN) trong mọi trường hợp.Chính vì thế, với dữ liệu lớn và cần ít thao tác sắp xếp thì Merge Sort sẽ tối ưu hơn Quick sort. Nó chỉ có 1 nhược điểm đó là code hơi khó cài đặt.Nhưng bạn đã có bài viết này sử dụng để tham khảo. Hãy luyện tập và luyện tập, qua nhiều lần thì chắc chắn bạn sẽ nắm được thuật toán Merge sort thôi.---
Bài viết liên quan

Trả lời

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *