Mastering Merge Sort: Hướng dẫn sắp xếp mảng bằng JavaScript

Chủ Nhật, 15/01/2023

Tram Ho

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 đối với bất kỳ ai muốn cải thiện kỹ năng viết mã của mình. 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 cách hoạt động của thuật toán này cũng như cách bạn có thể sử dụng thuật toán này trong các dự án JavaScript của riêng mình.

Hợp nhất sắp xếp là gì?

Hợp nhất Sắp xếp là một thuật toán lấy một mảng các phần tử và chia nó thành các mảng con nhỏ hơn. Các mảng con này sau đó được sắp xếp riêng lẻ và cuối cùng, các mảng con được hợp nhất lại với nhau để tạo thành một mảng được sắp xếp.

Lý do tại sao thuật toán này được gọi là “Sắp xếp hợp nhất” 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 lại thành một mảng duy nhất được sắp xếp. Quá trình này được lặp lại một cách đệ quy, chia mảng thành các phần nhỏ hơn và nhỏ hơn cho đến khi mỗi mảng con chỉ chứa một phần tử.

Ưu điểm chính của việc sử dụng Sắp xếp Hợp nhất là nó đảm bảo sắp xếp một mảng gồm n phần tử trong thời gian O(n * log n), làm cho nó hiệu quả hơn các thuật toán sắp xếp khác như Sắp xếp bong bóng hoặc sắp xếp chèn.

<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">&lt;</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">&lt;</span> left <span class="token punctuation">.</span> length <span class="token operator">&amp;&amp;</span> j <span class="token operator">&lt;</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">&lt;</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>

function mergeSort ( arr ) {

if ( arr . length < 2 ) {

return arr ;

}

let middle = Math . floor ( arr . length / 2 ) ;

let left = arr . slice ( 0 , middle ) ;

let right = arr . slice ( middle ) ;

return merge ( mergeSort ( left ) , mergeSort ( right ) ) ;

}

function merge ( left , right ) {

let result = [ ] ;

let i = 0 ;

let j = 0 ;

while ( i < left . length && j < right . length ) {

if ( left [ i ] < right [ j ] ) {

result . push ( left [ i ++ ] ) ;

} else {

result . push ( right [ j ++ ] ) ;

}

return result . concat ( left . slice ( i ) ) . concat ( right . slice ( j ) ) ;

}

Cách sử dụng Sắp xếp hợp nhất trong JavaScript

Bây giờ bạn đã hiểu các khái niệm cơ bản đằng sau Sắp xếp hợp nhất, hãy xem cách bạn có thể triển khai nó trong JavaScript. Đây là một ví dụ về triển khai cơ bản:

<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">&lt;</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">&lt;</span> left <span class="token punctuation">.</span> length <span class="token operator">&amp;&amp;</span> j <span class="token operator">&lt;</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">&lt;</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>

return arr ;

}

let i = 0 ;

let j = 0 ;

} else {

}

Trong ví dụ này, chúng ta có hai hàm: mergeSort và merge. Hàm 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. Sau đó, hàm hợp nhất lấy hai mảng con đã sắp xếp và hợp nhất chúng lại với nhau để tạo thành một mảng duy nhất đã được sắp xếp.

trường hợp sử dụng

Bây giờ bạn đã biết cách triển khai Sắp xếp hợp nhất trong JavaScript, hãy xem một số ví dụ thực tế về nơi bạn có thể 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 mà bạn cần sắp xếp theo thứ tự bảng chữ cái, bạn có thể sử dụng Hợp nhất Sắp xếp để thực hiện việc này một cách nhanh chóng và hiệu quả. Đây là một ví dụ:

<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>

let names = [ "Alice" , "Bob" , "Charlie" , "David" , "Eve" ] ;

console . log ( mergeSort ( names ) ) ;

// Output: ["Alice", "Bob", "Charlie", "David", "Eve"]

2. Sắp xếp danh sách số

Nếu bạn có một danh sách các số cần sắp xếp theo thứ tự tăng dần hoặc giảm dần, bạn cũng có thể sử dụng Sắp xếp Hợp nhất để thực hiện việc này. Đây là một ví dụ về cách bạn có thể sắp xếp danh sách các số theo thứ tự tăng dần:

<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>

let numbers = [ 4 , 2 , 5 , 1 , 3 ] ;

console . log ( mergeSort ( numbers ) ) ;

// Output: [1, 2, 3, 4, 5]

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 một thuộc tính cụ thể. Đây là một ví dụ về cách bạn có thể sắp xếp danh sách các đối tượng chứa thông tin về mọi người theo họ của họ:

<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">&lt;</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">&gt;</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>

let people = [

{ firstName : "John" , lastName : "Doe" } ,

{ firstName : "Jane" , lastName : "Smith" } ,

{ firstName : "Bob" , lastName : "Johnson" }

] ;

function compare ( a , b ) {

if ( a . lastName < b . lastName ) {

return - 1 ;

}

if ( a . lastName > b . lastName ) {

return 1 ;

}

return 0 ;

}

console . log ( mergeSort ( people , compare ) ) ;

/* Output:

[ { firstName: 'Bob', lastName: 'Johnson' },

{ firstName: 'John', lastName: 'Doe' },

{ firstName: 'Jane', lastName: 'Smith' } ]

*/

4. Sắp xếp danh sách cấu trúc dữ liệu tùy chỉnh

Ngoài các kiểu dữ liệu đơn giản như chuỗi và số, Hợp nhất Sắp xế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 hoặc cây nhị phân. Đây là một ví dụ về cách bạn có thể sử dụng Hợp nhất Sắp xếp để sắp xếp danh sách được liên kết:

<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>

class Node {

constructor ( value ) {

this . value = value ;

this . next = null ;

}

class LinkedList {

constructor ( ) {

this . head = null ;

this . tail = null ;

this . length = 0 ;

}

//.. push, mergeSort(linkedlist) methods

}

let list = new LinkedList ( ) ;

list . push ( 5 ) ;

list . push ( 2 ) ;

list . push ( 4 ) ;

list . push ( 1 ) ;

list . push ( 3 ) ;

list = mergeSort ( list ) ;

//.. traversing through linkedlist

5. Sắp xếp lượng lớn dữ liệu

Bởi vì Hợp nhất Sắp xếp có độ phức tạp về thời gian được đảm bảo là O(n * log n) , nên nó rất phù hợp để sắp xếp một lượng lớn dữ liệu. Điều này làm cho nó trở thành một lựa chọn tuyệt vời để sử dụng trong các ứng dụng khoa học dữ liệu hoặc dữ liệu lớn.

<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">=&gt;</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>

let largeData = Array . from ( { length : 1000000 } , ( ) => Math . floor ( Math . random ( ) * 100000 ) )

console . log ( "Before Sort: " , largeData . slice ( 0 , 5 ) ) ;

largeData = mergeSort ( largeData ) ;

console . log ( "After Sort: " , largeData . slice ( 0 , 5 ) ) ;

Phần kết luận

Hợp nhất Sắp xếp 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ừ các mảng số và chuỗi đơn giản đến các cấu trúc dữ liệu phức tạp hơn 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), khiến nó rất phù hợp để sắp xếp lượng lớn dữ liệu. Với hướng dẫn này và các ví dụ được cung cấp, giờ đây bạn đã có kiến thức để triển khai Sắp xếp Hợp nhất 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 mình.

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. Xin cảm ơn và hẹn gặp lại các bạn trong những bài viết tiếp theo!

Nếu các bạn thích bài viết này thì hãy cho mình 1 like và subscribe để ủng hộ mình nhé. Cảm ơn bạn.

Giới thiệu

https://tuan200tokyo.blogspot.com/2023/01/blog101-mastering-merge-sort-guide-to.html

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo