Thuật toán sắp xếp cho người mới bắt đầu trong JavaScript: Bubble, Selection & Insertion Sort
Việc sắp xếp tất cả các bộ dữ liệu sẽ chỉ làm tăng thêm thời gian và tài nguyên để quản lý và tìm kiếm. Dữ liệu có được sắp xếp hay không sẽ ảnh hưởng trực tiếp đến những phương pháp tìm kiếm bạn có thể sử dụng và có thể nghĩa là sự khác biệt giữa tìm kiếm thực hiện một triệu thao tác hoặc thực hiện 10, như với Tìm kiếm binary .
Vì lý do đơn giản, ta sẽ chỉ tập trung vào việc sắp xếp một mảng số từ ít nhất đến lớn nhất, nhưng các thuật toán này có thể dễ dàng sửa đổi cho các mục tiêu sắp xếp khác. Lưu ý đây là những khái niệm và mẫu chung chung hơn và không phải là “cách thực hiện” để phân loại dữ liệu vì cách triển khai cụ thể của bạn có thể khác nhiều nhưng cuối cùng thì nó có thể giống những mẫu này về mặt khái niệm.
Đây là mảng thực hành gồm 50 số ngẫu nhiê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]; Yêu cầu
Tôi sẽ xem xét mọi thứ qua lăng kính của Big O Notation , vì vậy hiểu được mức độ phức tạp phát triển theo thời gian sẽ rất hữu ích.
Sắp xếp bong bóng
Đây là “Xin chào thế giới” của các phương pháp sắp xếp, không có gì điên rồ nhưng nó hoàn thành công việc.
Đối với mỗi mục trong mảng, ta muốn kiểm tra xem mục tiếp theo có lớn hơn không, nếu có thì swap index của chúng trong mảng. Để tránh tính toán lại các số đã sắp xếp, ta sẽ bắt đầu từ phía sau của mảng trong khi một for loop khác lấy số ở trước. Bằng cách này, tất cả các giá trị lớn nhất đều tích tụ, hoặc "bong bóng", về cuối cùng.
Graphic / Animation nhờ VisuAlgo.net
Phiên bản của ta hoạt động ngược lại so với hoạt ảnh, nhưng nó đủ gần.
const bubble = arr => { const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]]; for (let i = arr.length; i > 0; i--) { for (let j = 0; j < i - 1; j++) { if (arr[j] > arr[j + 1]) swap(arr, j, j + 1); }; }; return arr; }; console.log(bubble(unsortedArr)); Sắp xếp lựa chọn
Sắp xếp lựa chọn hoạt động giống như ngược lại với Sắp xếp bong bóng, trong khi sắp xếp bong bóng đang đẩy tất cả các giá trị lớn nhất xuống cuối, bây giờ ta sẽ đẩy các giá trị nhỏ nhất lên đầu.
Mỗi khi nó lặp qua mảng, nó sẽ chọn giá trị nhỏ nhất, nếu nó tìm thấy giá trị thấp hơn thì giá trị đó trở thành giá trị thấp nhất mới. Khi vòng lặp được thực hiện, nó sẽ lấy mức tối thiểu đó và đặt nó ở phía trước của mảng trước khi bắt đầu lại vòng lặp. Bằng cách này, giá trị thấp nhất của mỗi lần lặp được xếp chồng lên phía trước cho đến khi toàn bộ mảng được sắp xếp.
Graphic / Animation nhờ VisuAlgo.net
const selection = arr => { const swap = (list, a, b) => [list[a], list[b]] = [list[b], list[a]]; arr.forEach((item, i) => { let min = i; for (let j = i + 1; j < arr.length; j++) { if (arr[j] < arr[min]) min = j; }; swap(arr, i, min); }); return arr; }; console.log(selection(unsortedArr)); Sắp xếp chèn
Yêu thích cá nhân của tôi và là người hoạt động tốt nhất trong ba, sắp xếp chèn , giống với cách bạn sắp xếp thứ gì đó bằng tay hơn.
Ta xem mảng như hai phần, phần được sắp xếp và phần chưa được sắp xếp, với mỗi lần ta tìm thấy một giá trị mới, ta lặp lại để tìm vị trí của nó trong nửa đã sắp xếp. Với mỗi lần bổ sung, group được sắp xếp của ta sẽ phát triển cho đến khi nó là toàn bộ mảng.
Graphic / Animation nhờ VisuAlgo.net
const insertion = arr => { arr.forEach((item, i) => { let num = arr[i]; let j; for (j = i - 1; j >= 0 && arr[j] > num; j--) { arr[j + 1] = arr[j]; }; arr[j + 1] = num; }); return arr; }; console.log(insertion(unsortedArr)); So sánh
Một vấn đề với việc sử dụng Ký hiệu Big O để so sánh các thuật toán là nó dựa trên tình huống xấu hơn, có thể giống nhau giữa các thuật toán tạo ra ảo giác sai rằng chúng bằng nhau. Mặc dù các loại Bong bóng, Lựa chọn và Chèn đều là O (n ^ 2), điều đó không cho ta biết nhiều về trường hợp trung bình hoặc trường hợp tốt nhất hoặc cách chúng thay đổi theo cấu trúc dữ liệu.
Sắp xếp chèn thắng mọi lúc. Nó cũng có lợi ích là không cần phải có toàn bộ mảng trước khi bắt đầu, cho phép bạn sắp xếp mọi thứ theo thời gian thực khi có dữ liệu.
Hãy nhớ điều này vì bạn không nên quyết định thuật toán nào là "tốt nhất" trước khi xem xét cách dữ liệu đã được tổ chức.
Kết luận
Ba giải pháp này không phải là giải pháp tốt nhất để phân loại hiệu quả lượng lớn dữ liệu, nhưng chúng là một số giải pháp trực quan nhất để nhúng ngón chân của bạn vào những gì có thể là một đại dương choáng ngợp. 🌊
Các tin liên quan
Tìm kiếm nhị phân tuyến tính Vs qua JavaScript2020-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
V8 của V8: Chuỗi liên kết tùy chọn và kết hợp Nullish trong JavaScript
2019-12-29
Phân tích cú pháp, xác thực, thao tác và hiển thị ngày và giờ trong JavaScript với Day.js
2019-12-28
