Ý tưởng
Radix Sort dựa trên nguyên tắc phân loại thư của bưu điện. Nó không quan tâm đến việc so sánh giá trị của phần tử và bản thân việc phân loại và trình tự phân loại sẽ tạo ra thứ tự cho các phần tử.
Giải thuật thực hiện như sau:
Giải thuật
Bước 1: // k cho biết chữ số dùng để phân loại hiện hành.
k = 0; // k = 0: hàng đơn vị; k = 1: hàng chục;…
Bước 2: // Tạo các lô chứa các loại phần tử khác nhau.
Khởi tạo 10 lô B0, B1,…, B9 rỗng;
Bước 3: For i = 1..n do
Đặt ai vào lô Bt với t = chữ số thứ k của ai ;
Bước 3: Nối B0, B1,…, B9 lại theo đúng trình tự thành a.
Bước 4: k = k + 1.
Nếu k < m: lặp lại bước 2.
Ngược lại: Dừng
Ví dụ
701 1725 999 9170 3252 4518 7009 1424 428 1239 8425 7013
1
2
3
4
5
6
7
8
9
10
11
12
B0
9170
B1
701
B2
3252
B3
7013
B4
1424
B5
1725
8425
B6
B7
B8
4518
428
B9
999
7009
1239
Sau khi nối:
9170 701 3252 7013 1424 1725 8425 4518 428 999 7009 1239
701 7009 7013 4518 1424 1725 8425 428 1239 3252 9170 999
7009 7013 9170 1239 3252 1424 8425 428 4518 701 1725 999
428 701 999 1239 1424 1725 3252 4518 7009 7013 8425 9170
Kết quả