Thực Hiện Sắp Xếp Đếm (Counting Sort) Trong JavaScript

Sắp xếp đếm (Counting Sort) là một thuật toán sắp xếp không so sánh, rất hiệu quả khi các giá trị trong mảng là số nguyên không âm và nằm trong một phạm vi giới hạn. Thuật toán này hoạt động bằng cách đếm số lần xuất hiện của mỗi giá trị trong mảng và sau đó tính toán vị trí chính xác của mỗi giá trị trong mảng đã sắp xếp.

Mã Nguồn:

function countingSort(arr) {
    if (arr.length === 0) return arr;

    // Tìm giá trị tối đa trong mảng để xác định kích thước của mảng đếm
    let max = Math.max(...arr);
    let count = new Array(max + 1).fill(0);
    let output = new Array(arr.length);

    // Đếm số lần xuất hiện của từng giá trị trong mảng
    for (let num of arr) {
        count[num]++;
    }

    // Tính toán vị trí chính xác của từng giá trị trong mảng đã sắp xếp
    for (let i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }

    // Xây dựng mảng đã sắp xếp
    for (let i = arr.length - 1; i >= 0; i--) {
        let num = arr[i];
        output[count[num] - 1] = num;
        count[num]--;
    }

    return output;
}

// Ví dụ kiểm tra
console.log(countingSort([4, 2, 2, 8, 3, 3, 1])); // [1, 2, 2, 3, 3, 4, 8]
console.log(countingSort([10, 7, 12, 5, 6, 8, 7])); // [5, 6, 7, 7, 8, 10, 12]

Giải Thích:

1. Tạo Mảng Đếm:

   • count: Một mảng để lưu số lần xuất hiện của từng giá trị trong mảng đầu vào. Kích thước của mảng count là max + 1, trong đó max là giá trị lớn nhất trong mảng.

2. Đếm Tần Suất:

   • Duyệt Mảng: Cập nhật số lần xuất hiện của mỗi giá trị trong mảng count.

3. Tính Toán Vị Trí:

   • Cộng Dồn Tần Suất: Tính toán vị trí chính xác của mỗi giá trị trong mảng đã sắp xếp bằng cách cộng dồn số lượng xuất hiện.

4. Xây Dựng Mảng Đã Sắp Xếp:

   • Duyệt Ngược: Xây dựng mảng đã sắp xếp từ mảng đầu vào bằng cách sử dụng thông tin từ mảng count.

Tổng Quan:

• Sắp Xếp Đếm: Phù hợp với các dữ liệu có giá trị không âm và trong phạm vi giới hạn.
• Hiệu Suất: Có thể đạt được hiệu suất tốt với độ phức tạp thời gian O(n + k), trong đó n là số lượng phần tử trong mảng và k là giá trị lớn nhất trong mảng.
• Ứng Dụng: Thích hợp cho các bài toán sắp xếp với các giá trị số nguyên có phạm vi hẹp.

Ví Dụ Thực Tế:

console.log(countingSort([4, 2, 2, 8, 3, 3, 1])); // [1, 2, 2, 3, 3, 4, 8]
console.log(countingSort([10, 7, 12, 5, 6, 8, 7])); // [5, 6, 7, 7, 8, 10, 12]

Trong ví dụ trên, mảng [4, 2, 2, 8, 3, 3, 1] và mảng [10, 7, 12, 5, 6, 8, 7] được sắp xếp theo thứ tự tăng dần bằng phương pháp sắp xếp đếm.