Đang tải…
Đang tải…
Sắp xếp từng chữ số một, từ thấp tới cao, mỗi chữ số một lượt chia thùng ổn định — O(d · n), không so sánh.
Giá trị lớn nhất là 100, nên 3 lượt theo chữ số là đủ. Mỗi lượt sắp theo MỘT chữ số và phải ổn định.
1void radixSort(int[] arr) {2 int max = Arrays.stream(arr).max().orElse(0);3 for (int exp = 1; exp <= max; exp *= 10) { // một lượt cho mỗi chữ số4 List<List<Integer>> buckets = new ArrayList<>();5 for (int b = 0; b < 10; b++) buckets.add(new ArrayList<>());6 for (int x : arr)7 buckets.get((x / exp) % 10).add(x); // tính ổn định là bắt buộc — nó giữ thứ tự của chữ số trước8 int i = 0;9 for (List<Integer> b : buckets) // nối 0…910 for (int x : b) arr[i++] = x;11 }12}