Sắp xếp hợp nhất: Giải thích đơn giản

May 08 2022
Trong Java Hãy bắt đầu học Sắp xếp hợp nhất Đầu tiên, chúng ta sẽ thấy hoạt động của sắp xếp Hợp nhất Tại đây Màu đỏ có nghĩa là -> chia & Màu xanh lá cây có nghĩa là -> chinh phục Phân tích từng bước của thuật toán Sắp xếp hợp nhất 1) Lấy một mảng số 2) Bây giờ lấy giữa mảng này Ở đây trong trường hợp này Kích thước của mảng này là 7. vì vậy chỉ số bắt đầu và kết thúc sẽ là 0 & 6 (tương ứng).

Trong Java

  1. Sắp xếp hợp nhất là một thuật toán sắp xếp
  2. Merge sort được tạo ra bởi John von Neumann vào năm 1945
  3. Sắp xếp hợp nhất sử dụng phương pháp Chia và Chinh phục để sắp xếp các phần tử trong một mảng
  1. Chia và Chinh phục là một cách tiếp cận để giải quyết vấn đề
  2. Có 3 bước liên quan đến cách tiếp cận Chia và Chinh phục
    1. Chia: Chia vấn đề đã cho thành các bài toán con
    2. Chinh phục: Giải các bài toán con
    3. Kết hợp: Kết hợp các câu trả lời một cách thích hợp

Hãy bắt đầu học Merge sort

Đầu tiên, chúng ta sẽ thấy hoạt động của loại Hợp nhất

Sắp xếp hợp nhất đang hoạt động (nguồn ảnh: Wikipedia)

Ở đây Màu đỏ có nghĩa là -> phân chia
& Màu xanh lá cây có nghĩa là -> chinh phục

Phân tích từng bước của thuật toán Sắp xếp hợp nhất

1) Lấy một mảng số

2) Bây giờ lấy phần giữa của mảng này
Ở đây trong trường hợp này
Kích thước của mảng này là 7.
vì vậy chỉ số bắt đầu và kết thúc sẽ là 0 & 6 (tương ứng).
Bây giờ để tìm giá trị giữa của mảng , có một công thức đơn giản: (l + r) / 2.
ở đây l là bên trái của mảng này là đầu của mảng = 0.
r là bên phải của mảng này là = a.length-1 = 7–1 = 6.

mid = (l + r) / 2
mid = (0 + 6) / 2 = 3
phần tử ở chỉ mục “3” là 3

3) Chia mảng thành mảng tráiphải Chia mảng
cho đến khi chỉ còn lại 1 phần tử trong mỗi mảng
nghĩa là l <r

Nếu chỉ có 1 phần tử trong mảng có nghĩa là mảng đã được sắp xếp

Hãy xem sự phân chia của mảng trong hoạt động

Lưu ý: chúng tôi không lấy giá trị float trong l, r & mid

Lưu ý: đây là các chỉ mục mà l, r & mid trỏ tới

Bước 1:

l = 0
r = a. chiều dài-1 = 6
giữa = (l + r) / 2 = 3

Đây là 2 mảng " trái" và " phải"

Kích thước của mảng "bên trái" là: (giữa l) +1
(3–0) + 1 = 4

Kích thước của mảng "bên phải" là: (r-mid)
(6–3) = 3

left [] = {28, 27, 43, 3}
right [] = {9, 82, 10}

Bây giờ như được mô tả trong điểm (3) ở trên
" Chia mảng cho đến khi chỉ còn lại 1 phần tử trong mỗi mảng"

Bước 2:

Bây giờ chúng ta sẽ chia mảng " bên trái"

l = 0
r = a. chiều dài-1 = 3
giữa = (l + r) / 2 = 1

Đây là 2 mảng " trái" và " phải"

Kích thước của mảng "bên trái" là: (giữa l) +1
(1–0) + 1 = 2

Kích thước của mảng "bên phải" là: (r-mid)
(3–1) = 2

left [] = {38, 27}
right [] = {43, 3}

Bước 3:

Bây giờ chúng ta sẽ chia mảng " bên phải"

l = 0
r = a. chiều dài-1 = 2
giữa = (l + r) / 2 = 1

Đây là 2 mảng " trái" và " phải"

Kích thước của mảng "bên trái" là: (giữa l) +1
(1–0) + 1 = 2

Kích thước của mảng "bên phải" là: (r-mid)
(2–1) = 1

left [] = {9, 82}
right [] = {10}

Như thế này, chúng tôi đã chia các mảng này thành trái và phải

Sau khi chia mảng được chia cuối cùng là

Bây giờ đã đến lúc hợp nhất các mảng đã sắp xếp này

Các mảng này được sắp xếp như thế nào?

Nếu một mảng chỉ chứa một phần tử thì hiển nhiên là tất cả các mảng này đều được sắp xếp

Hợp nhất là một quá trình kết hợp các mảng đã được sắp xếp thành một mảng đã được sắp xếp Ở đây chúng ta đã sử dụng phương pháp hợp nhất 2 chiều nếu có 4 mảng thì chúng ta sắp xếp 2 đầu tiên rồi đến 2 sau đó sắp xếp kết quả của cả 2 mảng đã sắp xếp

Được rồi, Bây giờ hãy hợp nhất các mảng đã sắp xếp này

" Quy trình hợp nhất "

Tìm kích thước của mảng bên trái và bên phải

giữa = (l + r) / 2

leftArraySize = (mid-l) +1

rightArraySize = (r-mid)

Lấy các con trỏ i & j tương ứng trên mảng bên trái và mảng bên phải.
lấy một con trỏ k = l (ở đây l = bên trái của mảng) cũng để chỉ nơi lưu phần tử tiếp theo trong mảng chính (hãy lấy mảng chính có tên là a )

kiểm tra bây giờ

1) if left [i] <right [j] if it is then a [k] = left [i]

2) sau đó tăng ki

3) else a [k] = right [j]

4) sau đó tăng dần kj

lặp lại 4 bước này cho đến khi

tôi <leftArraySize && j <rightArraySize

bây giờ điều gì xảy ra nếu điều kiện này được đáp ứng và vòng lặp dừng lại và vẫn còn các phần tử còn lại trong mảng, đối với điều này, chúng tôi sẽ sao chép các phần tử còn lại từ mảng (còn lại các phần tử)

Tiếng hoan hô! Việc hợp nhất được thực hiện

Hãy xem Hợp nhất của mảng trong hoạt động

Ở đây chúng ta có 2 mảng
left = {38}
right = {27}

đã hợp nhất chúng bằng cách sử dụng quy trình đã cho ở trên

a [] = {27, 38}

Được rồi, hãy lấy một ví dụ phức tạp và hiểu nó

left = {27, 38}
right = {3, 43)

Bước 2:

left [i] = 27 and right [j] = 43

left [i] <right [j] = true
right [j] <left [i] = false

a [k] = left [i]
i ++ và k ++

a = {3, 27}

Bước 3:

left [i] = 38 and right [j] = 43

left [i] <right [j] = true
right [j] <left [i] = false

a [k] = left [i]
i ++ và k ++

a = {3, 27, 38}

bây giờ chúng ta đã đi đến phần cuối, của cả hai mảng
vì vậy chỉ cần sao chép tất cả các phần tử còn lại từ mảng bên phải sang mảng chính a

a = {3, 27, 38, 43}

Như vậy, chúng tôi đã hợp nhất tất cả các mảng bên trái và bên phải còn lại

và kết quả sẽ như thế này

Vì vậy, đây là phần khái niệm của Sắp xếp Hợp nhất đã hoàn thành

Bây giờ đây là mã cho thuật toán sắp xếp Hợp nhất

Ví dụ về mã sắp xếp hợp nhất

Các đặc điểm quan trọng của Sắp xếp Hợp nhất:

  • Merge Sort không phải là một thuật toán tại chỗ: Nó cần các mảng phụ trợ để thực hiện sắp xếp
  • Độ phức tạp về thời gian của sắp xếp Hợp nhất là O (N log N) - cơ số 2. Chúng tôi liên tục chia mảng làm đôi trong giai đoạn tách
  • Merge Sort rất hữu ích để sắp xếp các danh sách được liên kết.
  • Merge Sort là một sắp xếp ổn định có nghĩa là cùng một phần tử trong một mảng duy trì vị trí ban đầu của chúng đối với nhau.
  • Độ phức tạp không gian của sắp xếp Hợp nhất là O (n). Điều này có nghĩa là thuật toán này chiếm nhiều dung lượng và có thể làm chậm hoạt động đối với các tập dữ liệu cuối cùng.

Cảm ơn vì đã đọc bài viết này ️


Do Krishna Wadhwani viết kịch bản

© Copyright 2021 - 2022 | vngogo.com | All Rights Reserved