Merge Sort Là Gì

Trong bài xích này bản thân sẽ trình làng đến các bạn thuật toán thu xếp trộn (Merge Sort). Đây là giữa những thuật toán sắp xếp trong C++.

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

*


*

Chúng ta sẽ cùng nhau tìm hiều về thu xếp trộn là gì với cách thực hiện thuật toán thu xếp trộn vào C++. Ở cuối bài xích viết, mình sẽ giải một bài bác toán ví dụ để chúng ta hiểu hơn về kiểu cách áp dụng thuật toán vào thực tế.

1. Bố trí trộn là gì?

Sắp xếp trộn là một thuật toán sắp xếp dựa trên giải thuật Divide and Conquer (Chia nhằm trị).

Thuật toán này sẽ chia mảng thành nhị nữa rồi bố trí trên từng nữa một. Tiếp nối kết hợp bọn chúng lại với nhau thành một mảng đang được chuẩn bị xếp.

Bài viết này được đăng trên


Ví dụ minh họa:

Như chúng ta đã thấy nghỉ ngơi hình trên, hàng số thuở đầu bao gôm các số: 38 27 43 3 9 82 10.

Chúng ta sẽ phân thành hai phần là 1 trong những bên 4 số và một bên 3 số. Rồi thường xuyên chia 4 số kia thành hai phần là mỗi bên 2 số. Cứ chia như vậy cho tới khi được hiệu quả như loại thứ 4.

Sau khi phân tách xong, hiện thời chúng ta bước đầu vào việc so sinh từng phần nhỏ. Rồi gom bọn chúng lại thành một dãy số hoàn hảo đã thu xếp ở các dòng 5, 6, 7 như trong hình.

Xem thêm: Các Tháng 12 Cung Gì ? Vận Mệnh Người Sinh Tháng 12 Ra Sao

Sau khi gom lại với so sánh chấm dứt ta được hàng số mới đã sắp xếp: 3 9 10 27 38 43 82.

2. Thuật toán sắp xếp trộn (Merge Sort) trong C++

Trong phần này mình sẽ gửi ra công việc để viết thuật toán, tiếp nối mình đang để thuật toán vẫn viết sẵn cho chúng ta dễ hình dung.

Giải thích thuật toán

Trong thuật toán sẽ sở hữu được hai bước đó là chia phần tử và gộp thành phần (kèm theo sắp xếp). Ví dụ trong thuật toán mình viết hàm mergeSort() để chia thành phần và hàm merge() nhằm gộp, sắp xếp phần tử.

Sử dụng đệ qui nhằm chia menu thành nhì nửa cho đến khi không chia thêm được nữa (hàm mergeSorrt()).Tạo nhị mảng trong thời điểm tạm thời để cất các thành phần sau lúc chia, cùng với sẽ là hai mảng bé L với R.Trường đúng theo chỉ có một trong những phần tử thì xem như đã được sắp tới xếp.Sau khi chia xong, đã gộp các thành phần ở mảng bé R cùng L vào mảng thiết yếu arr.Kết hợp các list bé dại đã sắp xếp với nhau thành một danh mục mới. Sau khi kết hợp tiến hành bố trí chúng để liên tiếp cho lần phối hợp kế tiếp.

Code thuật toán thu xếp trộn

Trong thuật toán mình đã chú thích nuốm thể, các chúng ta cũng có thể đọc để dễ hiểu hơn.


void merge(int arr<>, int l, int m, int r) int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L, R;//tạo 2 mảng trong thời điểm tạm thời để cất các thành phần sau khi phân chia // Copy dữ liệu sang những mảng trợ thời for (i = 0; i

3. Ví dụ bố trí trộn vào mảng

Chúng ta sẽ vận dụng thuật toán đang viết ngơi nghỉ trên, để viết một chương trình thu xếp các thành phần trong mảng được nhập từ bàn phím.

Tương từ như các bài trước, chỉ việc thay thế các thuật toán khác bởi thuật toán mergeSort() là được.

Code mẫu:


#include#include#include using namespace std;// họ cần có hai mảng bé vì vậy buộc phải tạo nhị mảng nhỏ arr cùng arr. Kế tiếp gộp bọn chúng lạivoid merge(int arr<>, int l, int m, int r) int i, j, k; int n1 = m - l + 1; int n2 = r - m; int L, R;//tạo 2 mảng tạm thời để đựng các thành phần sau khi phân tách // Copy dữ liệu sang những mảng lâm thời for (i = 0; i > n; while(n > a; ; cout
Kết quả:

Như vậy là bọn họ đã thực hiện xong chương trình bố trí các phần tử trong mảng, sử dụng phương thức bố trí trộn. Cũng như xong hướng dẫn thuật toán sắp xếp trộn trong C++. Chúc các bạn thực hiện thành công!!!