Sắp xếp dữ liệu là một khái niệm cơ bản trong khoa học máy tính và học cách sắp xếp mảng là một bước quan trọng để cải thiện kỹ năng mã hóa của riêng bạn. Một trong những thuật toán sắp xếp phổ biến nhất được gọi là ‘sắp xếp hợp nhất’ và trong bài viết này, chúng ta sẽ xem xét kỹ hơn một chút về cách thức hoạt động của thuật toán này cũng như cách sử dụng nó trong các dự án JavaScript của riêng bạn.
sáp nhập là gì
Hợp nhất là một thuật toán chia một mảng các phần tử thành các mảng con nhỏ hơn. Các mảng con đó được sắp xếp riêng lẻ và cuối cùng các mảng con được đưa trở lại vào một mảng đã sắp xếp.
Lý do thuật toán này được gọi là “sáp nhập” là vì nó sử dụng một quy trình gọi là “hợp nhất” để kết hợp các mảng con nhỏ hơn thành một mảng được sắp xếp duy nhất. Quá trình này được lặp lại một cách đệ quy, phân rã mảng thành các phần nhỏ hơn, mỗi phần chỉ chứa một phần tử.
Ưu điểm chính của việc sử dụng sáp nhập là nó đảm bảo sắp xếp n phần tử trong thời gian O(n * log n)
, so với các cách sắp xếp khác như sắp xếp bong bóng và sắp xếp chèn.
Cách sử dụng sáp nhập trong JavaScript
Bây giờ chúng ta đã hiểu ý tưởng cơ bản của mergesort, hãy xem cách triển khai nó trong JavaScript. Đây là một ví dụ về triển khai cơ bản.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 | <span class="token keyword">function</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> <span class="token parameter">arr</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> arr <span class="token punctuation">.</span> length <span class="token operator"><</span> <span class="token number">2</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> arr <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">let</span> middle <span class="token operator">=</span> Math <span class="token punctuation">.</span> <span class="token function">floor</span> <span class="token punctuation">(</span> arr <span class="token punctuation">.</span> length <span class="token operator">/</span> <span class="token number">2</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token keyword">let</span> left <span class="token operator">=</span> arr <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> <span class="token number">0</span> <span class="token punctuation">,</span> middle <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token keyword">let</span> right <span class="token operator">=</span> arr <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> middle <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token keyword">return</span> <span class="token function">merge</span> <span class="token punctuation">(</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> left <span class="token punctuation">)</span> <span class="token punctuation">,</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> right <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">function</span> <span class="token function">merge</span> <span class="token punctuation">(</span> <span class="token parameter">left <span class="token punctuation">,</span> right</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">let</span> result <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> <span class="token keyword">let</span> i <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> <span class="token keyword">let</span> j <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> <span class="token keyword">while</span> <span class="token punctuation">(</span> i <span class="token operator"><</span> left <span class="token punctuation">.</span> length <span class="token operator">&&</span> j <span class="token operator"><</span> right <span class="token punctuation">.</span> length <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> left <span class="token punctuation">[</span> i <span class="token punctuation">]</span> <span class="token operator"><</span> right <span class="token punctuation">[</span> j <span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> result <span class="token punctuation">.</span> <span class="token function">push</span> <span class="token punctuation">(</span> left <span class="token punctuation">[</span> i <span class="token operator">++</span> <span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">else</span> <span class="token punctuation">{</span> result <span class="token punctuation">.</span> <span class="token function">push</span> <span class="token punctuation">(</span> right <span class="token punctuation">[</span> j <span class="token operator">++</span> <span class="token punctuation">]</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> result <span class="token punctuation">.</span> <span class="token function">concat</span> <span class="token punctuation">(</span> left <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> i <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">.</span> <span class="token function">concat</span> <span class="token punctuation">(</span> right <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> j <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> |
Trong ví dụ này, chúng ta có hai hàm: mergeSort
và merge
. mergeSort
lấy một mảng làm đầu vào và sử dụng đệ quy để chia mảng đó thành các mảng con nhỏ hơn. Hàm merge
lấy hai mảng con được sắp xếp và đặt chúng trở lại thành một mảng được sắp xếp duy nhất.
Ví dụ sử dụng
Bây giờ chúng ta đã học cách triển khai sắp xếp hợp nhất trong JavaScript, hãy xem một ví dụ thực tế về việc sử dụng nó.
1. Sắp xếp danh sách tên
Nếu bạn có một danh sách các tên cần được sắp xếp theo thứ tự bảng chữ cái, bạn có thể thực hiện việc này một cách nhanh chóng và hiệu quả bằng cách sử dụng sắp xếp hợp nhất. Ví dụ.
1 2 3 4 | <span class="token keyword">let</span> names <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token string">"Alice"</span> <span class="token punctuation">,</span> <span class="token string">"Bob"</span> <span class="token punctuation">,</span> <span class="token string">"Charlie"</span> <span class="token punctuation">,</span> <span class="token string">"David"</span> <span class="token punctuation">,</span> <span class="token string">"Eve"</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> names <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// Output: ["Alice", "Bob", "Charlie", "David", "Eve"]</span> |
2. Sắp xếp danh sách các số
Khi xử lý danh sách các số cần được sắp xếp theo thứ tự tăng dần hoặc giảm dần, có thể đạt được điều đó bằng cách sử dụng sắp xếp hợp nhất. Dưới đây là một ví dụ về cách sắp xếp danh sách các số theo thứ tự tăng dần.
1 2 3 4 | <span class="token keyword">let</span> numbers <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token number">4</span> <span class="token punctuation">,</span> <span class="token number">2</span> <span class="token punctuation">,</span> <span class="token number">5</span> <span class="token punctuation">,</span> <span class="token number">1</span> <span class="token punctuation">,</span> <span class="token number">3</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> numbers <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">// Output: [1, 2, 3, 4, 5]</span> |
3. Sắp xếp danh sách đối tượng
Hợp nhất sắp xếp cũng có thể được sử dụng để sắp xếp danh sách các đối tượng dựa trên các thuộc tính nhất định. Dưới đây là một ví dụ về cách sắp xếp danh sách các đối tượng có thông tin về mọi người theo họ.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | <span class="token keyword">let</span> people <span class="token operator">=</span> <span class="token punctuation">[</span> <span class="token punctuation">{</span> firstName <span class="token operator">:</span> <span class="token string">"John"</span> <span class="token punctuation">,</span> lastName <span class="token operator">:</span> <span class="token string">"Doe"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> firstName <span class="token operator">:</span> <span class="token string">"Jane"</span> <span class="token punctuation">,</span> lastName <span class="token operator">:</span> <span class="token string">"Smith"</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">{</span> firstName <span class="token operator">:</span> <span class="token string">"Bob"</span> <span class="token punctuation">,</span> lastName <span class="token operator">:</span> <span class="token string">"Johnson"</span> <span class="token punctuation">}</span> <span class="token punctuation">]</span> <span class="token punctuation">;</span> <span class="token keyword">function</span> <span class="token function">compare</span> <span class="token punctuation">(</span> <span class="token parameter">a <span class="token punctuation">,</span> b</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> a <span class="token punctuation">.</span> lastName <span class="token operator"><</span> b <span class="token punctuation">.</span> lastName <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">if</span> <span class="token punctuation">(</span> a <span class="token punctuation">.</span> lastName <span class="token operator">></span> b <span class="token punctuation">.</span> lastName <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">return</span> <span class="token number">1</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token keyword">return</span> <span class="token number">0</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> people <span class="token punctuation">,</span> compare <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">/* Output: [ { firstName: 'Bob', lastName: 'Johnson' }, { firstName: 'John', lastName: 'Doe' }, { firstName: 'Jane', lastName: 'Smith' } ] */</span> |
4. Sắp xếp danh sách cấu trúc dữ liệu tùy chỉnh
Bên cạnh các kiểu dữ liệu đơn giản như chuỗi và số, sáp nhập cũng có thể được sử dụng để sắp xếp các cấu trúc dữ liệu tùy chỉnh như danh sách được liên kết và cây nhị phân. Dưới đây là một ví dụ về cách sắp xếp một danh sách được liên kết.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 | <span class="token keyword">class</span> <span class="token class-name">Node</span> <span class="token punctuation">{</span> <span class="token function">constructor</span> <span class="token punctuation">(</span> <span class="token parameter">value</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">this</span> <span class="token punctuation">.</span> value <span class="token operator">=</span> value <span class="token punctuation">;</span> <span class="token keyword">this</span> <span class="token punctuation">.</span> next <span class="token operator">=</span> <span class="token keyword">null</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token punctuation">}</span> <span class="token keyword">class</span> <span class="token class-name">LinkedList</span> <span class="token punctuation">{</span> <span class="token function">constructor</span> <span class="token punctuation">(</span> <span class="token punctuation">)</span> <span class="token punctuation">{</span> <span class="token keyword">this</span> <span class="token punctuation">.</span> head <span class="token operator">=</span> <span class="token keyword">null</span> <span class="token punctuation">;</span> <span class="token keyword">this</span> <span class="token punctuation">.</span> tail <span class="token operator">=</span> <span class="token keyword">null</span> <span class="token punctuation">;</span> <span class="token keyword">this</span> <span class="token punctuation">.</span> length <span class="token operator">=</span> <span class="token number">0</span> <span class="token punctuation">;</span> <span class="token punctuation">}</span> <span class="token comment">//.. push, mergeSort(linkedlist) methods</span> <span class="token punctuation">}</span> <span class="token keyword">let</span> list <span class="token operator">=</span> <span class="token keyword">new</span> <span class="token class-name">LinkedList</span> <span class="token punctuation">(</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> list <span class="token punctuation">.</span> <span class="token function">push</span> <span class="token punctuation">(</span> <span class="token number">5</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> list <span class="token punctuation">.</span> <span class="token function">push</span> <span class="token punctuation">(</span> <span class="token number">2</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> list <span class="token punctuation">.</span> <span class="token function">push</span> <span class="token punctuation">(</span> <span class="token number">4</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> list <span class="token punctuation">.</span> <span class="token function">push</span> <span class="token punctuation">(</span> <span class="token number">1</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> list <span class="token punctuation">.</span> <span class="token function">push</span> <span class="token punctuation">(</span> <span class="token number">3</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> list <span class="token operator">=</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> list <span class="token punctuation">)</span> <span class="token punctuation">;</span> <span class="token comment">//.. traversing through linkedlist</span> |
5. Sắp xếp lượng lớn dữ liệu
Độ phức tạp về thời gian được đảm bảo của sắp xếp hợp nhất là O(n * log n)
, làm cho nó phù hợp để sắp xếp lượng lớn dữ liệu. Do đó, nó phù hợp để sử dụng trong các ứng dụng khoa học dữ liệu và dữ liệu lớn.
1 2 3 4 5 | <span class="token keyword">let</span> largeData <span class="token operator">=</span> Array <span class="token punctuation">.</span> <span class="token function">from</span> <span class="token punctuation">(</span> <span class="token punctuation">{</span> length <span class="token operator">:</span> <span class="token number">1000000</span> <span class="token punctuation">}</span> <span class="token punctuation">,</span> <span class="token punctuation">(</span> <span class="token punctuation">)</span> <span class="token operator">=></span> Math <span class="token punctuation">.</span> <span class="token function">floor</span> <span class="token punctuation">(</span> Math <span class="token punctuation">.</span> <span class="token function">random</span> <span class="token punctuation">(</span> <span class="token punctuation">)</span> <span class="token operator">*</span> <span class="token number">100000</span> <span class="token punctuation">)</span> <span class="token punctuation">)</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token string">"Before Sort: "</span> <span class="token punctuation">,</span> largeData <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">5</span> <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> largeData <span class="token operator">=</span> <span class="token function">mergeSort</span> <span class="token punctuation">(</span> largeData <span class="token punctuation">)</span> <span class="token punctuation">;</span> console <span class="token punctuation">.</span> <span class="token function">log</span> <span class="token punctuation">(</span> <span class="token string">"After Sort: "</span> <span class="token punctuation">,</span> largeData <span class="token punctuation">.</span> <span class="token function">slice</span> <span class="token punctuation">(</span> <span class="token number">0</span> <span class="token punctuation">,</span> <span class="token number">5</span> <span class="token punctuation">)</span> <span class="token punctuation">)</span> <span class="token punctuation">;</span> |
Phần kết luận
Mergesort là một thuật toán sắp xếp mạnh mẽ và hiệu quả, có thể được sử dụng để sắp xếp nhiều loại dữ liệu, từ mảng số và chuỗi đến các cấu trúc dữ liệu phức tạp như danh sách được liên kết và cây nhị phân. Ưu điểm chính của sắp xếp hợp nhất là độ phức tạp về thời gian được đảm bảo của nó là O(n * log n)
, làm cho nó phù hợp để sắp xếp một lượng lớn dữ liệu. Với hướng dẫn và các ví dụ này, bạn sẽ có kiến thức để triển khai sáp nhập trong các dự án JavaScript
của riêng mình và cải thiện kỹ năng mã hóa của riêng bạn.
Như mọi khi, tôi hy vọng bạn thích bài viết này và học được điều gì đó mới.
Cảm ơn rất nhiều. Hẹn gặp lại các bạn trong bài viết tiếp theo!
Nếu các bạn thích bài viết này, hãy ủng hộ chúng tôi bằng cách like và subscribe. Cảm ơn rất nhiều.