Triển khai sắp xếp đếm trong JavaScript

Chúng tôi được yêu cầu viết một hàm JavaScript nhận vào một mảng số và sắp xếp nó bằng cách sử dụng thuật toán sắp xếp đếm.

Nếu chúng ta biết giá trị lớn nhất, chúng ta có thể sử dụng thuật toán sắp xếp đếm để sắp xếp một mảng Số theo thời gian và không gian tuyến tính. Sử dụng giá trị lớn nhất tạo một mảng có kích thước đó để đếm số lần xuất hiện của mỗi giá trị chỉ mục.

Sau đó, chúng tôi sẽ trích xuất tất cả các chỉ mục có số đếm khác 0 vào mảng kết quả của chúng tôi.

Trước tiên, chúng ta sẽ sử dụng một vòng lặp để tìm ra phần tử lớn nhất của mảng, khi có điều đó, chúng ta sẽ sử dụng tính năng sắp xếp đếm để sắp xếp mảng.

Ví dụ

const arr = [4, 3, 1, 2, 3];
const findMaximum = arr => arr.reduce((acc, val) => val > acc ? val: acc, Number.MIN_VALUE)
const countingSort = (arr = []) => {
   const max = findMaximum(arr);
   const counts = new Array(max + 1);
   counts.fill(0);
   arr.forEach(value => counts[value]++);
   const res = [];
   let resultIndex = 0;
   counts.forEach((count, index) => {
      for (let i = 0; i < count; i++) {
         res[resultIndex] = index;
         resultIndex++;
      };
   });
   return res;
};
console.log(countingSort(arr));

Đầu ra

Và đầu ra trong bảng điều khiển sẽ là -

[ 1, 2, 3, 3, 4 ]