Chương trình Java Counting Sort

Counting Sort đếm số đối tượng có giá trị khóa khác nhau. Hãy xem ví dụ:

Lưu ý - Mã dưới có thể dùng với số âm.

Ví dụ

import java.util.*; 
public class Demo{ 
    static void count_sort(int[] arr){ 
        int max_val = Arrays.stream(arr).max().getAsInt(); 
        int min_val = Arrays.stream(arr).min().getAsInt(); 
        int range = max_val - min_val + 1; 
        int count[] = new int[range]; 
        int result[] = new int[arr.length]; 
        for (int i = 0; i < arr.length; i++){ 
            count[arr[i] - min_val]++; 
        } 
        for (int i = 1; i < count.length; i++){ 
            count[i] += count[i - 1]; 
        } 
        for (int i = arr.length - 1; i >= 0; i--){ 
            result[count[arr[i] - min_val] - 1] = arr[i]; 
            count[arr[i] - min_val]--; 
        } 
        for (int i = 0; i < arr.length; i++){ 
            arr[i] = result[i]; 
        } 
    } 
    static void printVal(int[] arr){ 
        for (int i = 0; i < arr.length; i++){ 
            System.out.print(arr[i] + " "); 
        } 
        System.out.println(""); 
    } 
    public static void main(String[] args){ 
        int[] arr = {-5, 0, -3, 8, 34, 56, 89, -11, -95, -1, 10}; 
        System.out.println("Mảng chứa: "); 
        for (int i = 0; i < arr.length; i++){ 
            System.out.print(arr[i] + " "); 
        } 
        System.out.println(); 
        System.out.println("Triển khai Counting Sort trong Java cho kết quả: "); 
        count_sort(arr); 
        printVal(arr); 
    } 
}

Kết quả

Mảng chứa -5 0 -3 8 34 56 89 -11 -95 -1 10 
Triển khai Counting Sort trong Java cho kết quả: -95 -11 -5 -3 -1 0 8 10 34 56 89

Lớp Demo chứa hàm count_sort. Mảng duyệt qua và giá trị đếm tăng.

Mảng đếm duyệt qua và giá trị trước gán cho giá trị sau. Mảng duyệt lại và phần tử mảng gán cho mảng kết quả, mảng đếm giảm. Sau đó, mảng duyệt lại và phần tử mảng kết quả gán cho mảng. Hàm in định nghĩa in dữ liệu. Main định nghĩa phần tử mảng và gọi count sort.