Đang tải…
Đang tải…
Sắp xếp mà không so sánh lần nào bằng cách đếm số lần xuất hiện của mỗi khóa, rồi ghi lại theo thứ tự — O(n + k).
Khóa lớn nhất là 100, nên cấp một bảng đếm gồm 101 ô — mỗi ô cho một giá trị có thể có.
1void countingSort(int[] arr) {2 int k = 0;3 for (int x : arr) k = Math.max(k, x);4 int[] count = new int[k + 1]; // một ô đếm cho mỗi khóa5 for (int x : arr) count[x]++; // đếm trong một lượt6 int pos = 0;7 for (int v = 0; v <= k; v++) // theo thứ tự khóa tăng8 while (count[v]-- > 0) arr[pos++] = v; // với dữ liệu kèm theo, dùng đếm tích lũy và xếp từ phải sang để giữ tính ổn định9}