Hiểu Hợp nhất Sắp xếp Thông qua JavaScript
Trước đây, ta đã đề cập đến một số thuật toán sắp xếp dành cho người mới bắt đầu có thể hoàn thành công việc nhưng nhanh chóng vượt qua với các bộ dữ liệu lớn hơn. Bây giờ ta có thể bắt đầu đào sâu vào một số thuật toán lớn hiệu quả hơn, như sắp xếp hợp nhất . Với điều này, ta có thể chuyển từ thuật toán O(n^2) sang giải pháp O(nlogn) có thể mở rộng hơn nhiều.
Yêu cầu
Có thể suy nghĩ về độ phức tạp của thời gian và không gian thông qua Big O Notation sẽ vô cùng hữu ích. Ta cũng sẽ xem xét các ví dụ dựa trên đệ quy, vì vậy bạn có thể tìm hiểu về điều đó tại đây .
Ý tưởng
Tương tự như tìm kiếm binary , sắp xếp hợp nhất là một thuật toán chia và chinh phục . Mục đích là chia nhỏ vấn đề của ta thành các bài toán con và đệ quy tiếp tục chia nhỏ chúng cho đến khi ta có nhiều bài toán đơn giản mà ta có thể dễ dàng ghép lại với nhau.
Sắp xếp hợp nhất được xây dựng dựa trên ý tưởng so sánh toàn bộ mảng thay vì các mục riêng lẻ. Đầu tiên, ta cần lấy toàn bộ mảng và chia nó thành nhiều mảng con bằng cách liên tục tách mọi thứ ra làm đôi cho đến khi mọi thứ nằm riêng trong mảng của chính nó. Vì số lượng mảng con sẽ là bội số của số lượng mục trong mảng chính của ta , đó là những gì cung cấp cho ta log O(nlogn) .
Từ đó, ta có thể bắt đầu hợp nhất, vì cả hai mảng đã được sắp xếp, ta có thể dễ dàng so sánh số nào trong mỗi mảng nhỏ hơn và đặt chúng vào đúng vị trí. Đây là nơi bắt nguồn từ n trong O(nlogn) .
Như bạn thấy một nửa của mảng được hoàn thành trước nửa sau và nửa đầu của mỗi mảng trước nửa sau (các màu khác nhau đại diện cho các mảng khác nhau).
Graphic / Animation nhờ VisuAlgo.net
Dữ liệu thực hành
Đây là mảng gồm 50 mặt hàng chưa được sắp xếp mà tôi sẽ đề cập đến.
const unsortedArr = [31, 27, 28, 42, 13, 8, 11, 30, 17, 41, 15, 43, 1, 36, 9, 16, 20, 35, 48, 37, 7, 26, 34, 21, 22, 6, 29, 32, 49, 10, 12, 19, 24, 38, 5, 14, 44, 40, 3, 50, 46, 25, 18, 33, 47, 4, 45, 39, 23, 2]; Hợp nhất
Để đơn giản hóa vấn đề của ta , ta có thể bắt đầu bằng cách tạo một hàm tiện ích sẽ hợp nhất hai mảng đã sắp xếp. Có nhiều cách khác nhau để làm điều này nhưng tôi thấy cách này ngắn gọn nhất.
Miễn là có các mục trong một trong hai mảng, hãy kiểm tra xem mục đầu tiên trong một trong hai mảng có nhỏ hơn không, sau đó ném nó vào đã sắp xếp và xóa mục đó khỏi mảng bằng shift() . Khi điều đó xong, nếu còn bất cứ thứ gì còn sót lại, chẳng hạn như khi một mảng lớn hơn, hãy nối mảng đó vào phần cuối.
Vì vậy, cả hai mảng đang dần thu hẹp lại cho đến khi một trong số chúng trống rỗng với phần còn lại được ném vào cuối, vì nó đã được sắp xếp.
const merge = (arr1, arr2) => { let sorted = []; while (arr1.length && arr2.length) { if (arr1[0] < arr2[0]) sorted.push(arr1.shift()); else sorted.push(arr2.shift()); }; return sorted.concat(arr1.slice().concat(arr2.slice())); }; console.log(merge([2, 5, 10, 57], [9, 12, 13])); Sắp xếp
Đây là phần dễ dàng, ta có thể sử dụng một hàm đệ quy để liên tục cắt mảng của ta làm đôi, sử dụng slice() để lưu dữ liệu ở hai bên của tâm. Nó sẽ trở lại khi ta có các mảng 1 mục của bạn , sau đó ta sẽ sử dụng trình merge mình để bắt đầu xây dựng chúng trở lại thành một mảng lớn, với mỗi lần hợp nhất sẽ sắp xếp chúng theo cách.
const mergeSort = arr => { if (arr.length <= 1) return arr; let mid = Math.floor(arr.length / 2), left = mergeSort(arr.slice(0, mid)), right = mergeSort(arr.slice(mid)); return merge(left, right); }; console.log(mergeSort(unsortedArr)); Kết luận
Mặc dù Merge sort là thuật toán tốt nhất mà ta đã đề cập cho đến nay vì nó là O(nlogn) , nhưng tốt hơn hết là bạn nên nhớ rằng nó hoạt động tốt hơn với lượng dữ liệu lớn hơn. Nếu bạn không biết mình cần sắp xếp bao nhiêu dữ liệu, hãy xem xét sử dụng một thuật toán khác, như sắp xếp chèn, khi tập dữ liệu đủ nhỏ để tận dụng tối đa cả hai thế giới.
Các tin liên quan
Tạo biểu mẫu tùy chỉnh bằng API dữ liệu biểu mẫu JavaScript2020-02-06
Thuật toán sắp xếp cho người mới bắt đầu trong JavaScript: Bubble, Selection & Insertion Sort
2020-02-03
Tìm kiếm nhị phân tuyến tính Vs qua JavaScript
2020-01-29
Hiểu Đệ quy & Ghi nhớ qua JavaScript
2020-01-26
Đọc và xử lý tệp với API JavaScript FileReader
2020-01-23
Tìm hiểu ký hiệu Big O qua JavaScript
2020-01-20
Cách sử dụng API BroadcastChannel trong JavaScript
2020-01-13
Đa năng hóa chuỗi trong JavaScript bằng Simplur
2020-01-10
Hướng dẫn nhanh về phương pháp đối sánh chuỗi trong JavaScript
2020-01-07
Tham quan API quyền JavaScript
2020-01-05
