Hiểu Radix Sắp xếp Thông qua JavaScript
Do bản chất của sắp xếp dựa trên so sánh, về mặt toán học không thể cải thiện nhiều ngoài O(nlogn) , giống như sắp xếp hợp nhất và sắp xếp nhanh . Thay vào đó, ta có thể khéo léo hơn một chút và tránh so sánh tất cả với nhau để đạt được thứ gì đó gần hơn với O(n * m) .
Yêu cầu
Hiểu biết cơ bản về Ký hiệu Big O là cần thiết để suy nghĩ về sắp xếp cơ số so với các thuật toán khác.
Ý tưởng
Radix sort, còn gọi là sắp xếp theo group , là một trong những thuật toán sắp xếp lâu đời nhất và thậm chí cả những máy tính đã tồn tại từ trước. Nó được sử dụng để phân loại thẻ đục lỗ vào những năm 1880.
Nó dựa trên ý tưởng về việc có một mảng con hoặc group , cho mỗi loại dữ liệu mà ta cần so sánh, như AZ hoặc trong trường hợp của ta là 0-9. Ta lấy ký tự / chữ số đầu tiên trong mỗi mục, thêm toàn bộ mục vào group tương ứng, sau đó đặt chúng trở lại một mảng trong khi vẫn giữ nguyên thứ tự mới của chúng.
Sau đó, ta có thể chuyển sang ký tự / chữ số tiếp theo và lặp lại quá trình. Khi một mục hết ký tự / chữ số, ta sẽ thêm nó vào group đầu tiên, vì mọi thứ khác rõ ràng là lớn hơn / dài hơn. Khi ta đã thực hiện điều này nhiều lần với số chữ số / ký tự của mục lớn nhất, mảng của ta sẽ được sắp xếp hoàn toàn mà không thực hiện bất kỳ so sánh khó khăn nào.
Graphic / Animation nhờ VisuAlgo.net
Dữ liệu thực hành
Vì các số đơn giản hơn nhiều nên ta có thể thực hành với một mảng từ 1 đến 50.
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]; Tiện ích
Vì ta đang làm việc với các con số, ta muốn bắt đầu với vị trí số nhỏ nhất và tăng dần lên, vì vậy ta cần một cách để lấy mỗi số ở một index bắt đầu từ bên phải.
Cách trực quan nhất mà tôi đã tìm thấy là lấy số ta muốn, chuyển nó thành một chuỗi và chọn từ nó dưới dạng một mảng có chỉ số âm. Nếu một số không ở index đó, ta chỉ có thể trả về số 0 để nó sẽ được đặt ở phía trước của mảng đã sắp xếp của ta .
const getNum = (num, index) => { const strNum = String(num); let end = strNum.length - 1; const foundNum = strNum[end - index]; if (foundNum === undefined) return 0; else return foundNum; }; console.log(getNum(4353, 2)); Bởi vì ta đang làm việc trở lại một chữ số tại một thời điểm, ta cần thuật toán chạy bao nhiêu lần số dài nhất, vì vậy nếu ta có một mục có 8 chữ số, nó cần phải chạy 8 lần. Độ phức tạp trung bình của Radix sort là O(n * m) vì nó là số lượng mục nhân với số lần nó cần được chạy.
Để biết nó sẽ chạy bao nhiêu lần, ta có thể tìm kiếm số lớn nhất trong mảng, sau đó trả về độ dài của nó.
const largestNum = arr => { let largest = "0"; arr.forEach(num => { const strNum = String(num); if (strNum.length > largest.length) largest = strNum; }); return largest.length; }; Radix Sort
Việc triển khai khá đơn giản, đối với mọi vị trí chữ số, ta có thể sử dụng Array.from để tạo 10 group trống. Đối với mỗi mục, chúng sẽ được đặt trong group tương ứng, khi điều đó xong, ta sẽ san phẳng mảng group thành một mảng duy nhất để bắt đầu lại với vị trí ký tự tiếp theo. Khi ta đi đến cuối chữ số dài nhất của bạn , mảng được sắp xếp đầy đủ của ta có thể được trả lại.
const radixSort = arr => { let maxLength = largestNum(arr); for (let i = 0; i < maxLength; i++) { let buckets = Array.from({ length: 10 }, () => []); for (let j = 0; j < arr.length; j++) { let num = getNum(arr[j], i); if (num !== undefined) buckets[num].push(arr[j]); }; arr = buckets.flat(); }; return arr; }; console.log(radixSort(unsortedArr)); Kết luận
Trong khi nghịch ngợm với thứ này, tôi đã thử nó trên một loạt 5.000 mặt hàng, tôi thực sự ngạc nhiên khi nó được thực hiện chỉ trong 23 mili giây! Tôi không biết về bạn, nhưng tôi nghĩ đó là một cải tiến đáng kinh ngạc so với các thuật toán khác mà ta đã đề cập cho đến nay.
Các tin liên quan
Cách xây dựng PWA trong Vanilla JavaScript2020-02-17
Hiểu về Sắp xếp nhanh qua JavaScript
2020-02-14
Hiểu bản đồ và thiết lập đối tượng trong JavaScript
2020-02-12
Hiểu Hợp nhất Sắp xếp Thông qua JavaScript
2020-02-08
Tạo biểu mẫu tùy chỉnh bằng API dữ liệu biểu mẫu JavaScript
2020-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
