Thuật toán Sắp xếp trộn (Merge Sort)

thucnq · 07-02-2010, 12:19 PM

Merge sort chia danh sách dữ liệu cần được sắp xếp thành hai nữa bằng nhau, và đặt chúng vào các vùng chứa dữ liệu riêng biệt (list, array,...). Mỗi mảng dữ liệu được sắp xếp một cách đệ quy, sau đó trộn lẫn vào nhau tạo thành danh sách dữ liệu được sắp xếp cuối cùng. Giống như hầu hết các phương pháp sắp xếp đệ quy, Merge sort có độ phức tạp là O(n log n).

Cách triển khai cơ bản của Merge sort là dùng ba mảng dữ liệu - mỗi mảng để chứa mổi nữa của tập dữ liệu cần sắp xếp và một mảng chứa danh sách được sắp xếp cuối cùng. Thuật toán được giới thiệu sau đây trộn các mảng lại thành một, vì vậy chỉ sử dụng hai mảng cho toàn bộ quá trình xử lý. Hiện nay cũng tồn tại phiên bản không đệ quy của Merge sort, nhưng chúng không thu được bất kì một cải tiến tốc độ nào so với phiên bản đệ quy qua thử nghiệm trên hầu hết các kiến trúc xử lý.

Merge sort thì nhanh hơn một ít so với Heap sort với các tập dữ liệu lớn, nhưng nó đòi hỏi 2 lần bộ nhớ so với Heap sort vì vậy nó không được ưa chuộng trong việc triển khai ứng dụng dù cho mục đích là gì - Quick sort là lựa chọn tốt hơn cho thời gian và Heap sort thì lại là lựa chọn tốt hơn với các tập dữ liệu rất lớn.

Giống như Quick sort, Merge sort là phương pháp dựa trên đệ quy, điều này khiến nó sẽ là lựa chọn tồi với các ứng dụng chạy trên máy tính bị giới hạn về bộ nhớ.

Binh Nguyen - Bioz - ieev.org

devilstd · 16-03-2010, 02:30 PM

Cho em hỏi cái!"....dữ liệu cần được sắp xếp thành hai nữa bằng nhau..." nếu mình nhập 1 mảng 4pt
[1][2][3][4] thì sắp xếp chia bằng nhau đc! còn nếu ta nhập!! 5pt thì sao????[1][2][3][4][5] sao chia bằng nhau đc???? trả lời nhanh dùm em
-----Thanks-----

thucnq · 16-03-2010, 04:01 PM

nói là chia thành 2 phần bằng nhau là mang tính tương đối thôi em à. khi chia đôi người ta dùng kỹ thuật làm tròn (có thể tròn lên hoặc tròn xuống) ví dụ danh sách có 5 phần tử thì vị trí chia đôi sẽ là 2.5 (hiểu theo nghĩa chính xác) tuy nhiên áp dụng làm tròn người ta cho vị trí chia đôi là 2 (tròn xuống) như vậy ta sẽ dc 2 mảng tương đối.

em còn thắc mắc j cứ pm ở đây

5 Chủ đề mới nhất của thucnq
Chủ đề	Chuyên mục	Người gởi sau cùng	Trả lời	Lần đọc	Bài mới gửi
Ebook Tạo web động với PHP và Mysql ví dụ cụ thể...	Bài tập lớn - Đồ án - ebook PHP	thucnq	0	665	25-05-2010 10:14 AM
pascal programming guide.pdf tài liệu học pascal...	Bài tập lớn - Đồ án - ebook Pascal/Delphi	thucnq	0	187	25-05-2010 10:05 AM
4 Bài tập và lời giải thực hành ASP (hướng dẫn...	Bài tập - Thực hành ASP/ASP.NET	thucnq	0	641	25-05-2010 09:28 AM
Bài tập thực hành html javascript asp	Bài tập - Thực hành ASP/ASP.NET	thucnq	0	460	25-05-2010 09:20 AM
Bài tập lớn môn cấu trúc dữ liệu và giải thuật	Cấu trúc dữ liệu và giải thuật	thucnq	0	557	25-05-2010 08:45 AM

Ðang đọc: 1 (0 thành viên và 1 khách)