Sắp xếp theo cơ số (radix sort) trong Python
Bài 20/20 · Chương 23
Cấu trúc dữ liệu và giải thuật
- 8 phút
- Trung cấp
- Python 3.14
- Cập nhật
Trong bài này · 12
Sắp xếp theo cơ số (radix sort) là thuật toán xếp số nguyên theo từng chữ số, bắt đầu từ hàng đơn vị rồi lên hàng chục, hàng trăm. Mỗi lượt là một lần sắp xếp đếm ổn định theo mười chữ số 0 đến 9, nên không cần list đếm khổng lồ. Nó hợp với rất nhiều số nguyên ngắn, như số vé của hàng nghìn chuyến xe.
Cần biết trước: sắp xếp đếm và toán tử số học.
Lấy một chữ số bằng // và %
Chia nguyên cho 10 ** k bỏ đi k chữ số cuối, rồi lấy dư khi chia cho 10 giữ lại đúng một chữ số. Với k = 0 đó là hàng đơn vị, k = 1 là hàng chục:
x = 318
for k in range(3):
print("Hàng", 10 ** k, ":", (x // 10 ** k) % 10)KẾT QUẢ
Hàng 1 : 8
Hàng 10 : 1
Hàng 100 : 3Toán tử ** được tính trước //, nên x // 10 ** k là x // (10 ** k). Cặp ngoặc quanh phép chia nguyên chỉ để dễ đọc, vì // và % cùng mức ưu tiên và được tính từ trái sang phải. Đổi range(3) thành range(4) rồi chạy lại: dòng cuối in Hàng 1000 : 0, vì số có ít chữ số được coi như có các số 0 ở đầu.
Xếp từ hàng đơn vị lên
Danh sách dưới đây là số vé đã bán trong ngày của bảy tuyến xe. Số lớn nhất có ba chữ số, nên radix sort chạy ba lượt. Để thấy riêng thứ tự các lượt, ví dụ này tạm dùng sorted() với key= cho mỗi lượt, vì sorted() cũng ổn định. Mục sau thay nó bằng counting sort:
ds = [318, 74, 205, 9, 147, 380, 61]
so_luot = len(str(max(ds)))
for k in range(so_luot):
ds = sorted(ds, key=lambda x: (x // 10 ** k) % 10)
print("Sau hàng", 10 ** k, ":", ds)KẾT QUẢ
Sau hàng 1 : [380, 61, 74, 205, 147, 318, 9]
Sau hàng 10 : [205, 9, 318, 147, 61, 74, 380]
Sau hàng 100 : [9, 61, 74, 147, 205, 318, 380]Sau lượt hàng chục, 61 đứng trước 74 vì hàng chục 6 nhỏ hơn 7. Hai số 205 và 9 cùng hàng chục 0, nên chúng giữ thứ tự của lượt trước, là thứ tự theo hàng đơn vị. Lượt sau chỉ phân xử các số khác nhau ở hàng của nó, còn các số bằng nhau ở hàng đó giữ nguyên thứ tự mà các lượt trước đã xếp. Đó là lý do mỗi lượt bắt buộc phải ổn định.
Mỗi lượt là một lần sắp xếp đếm ổn định
Một lượt đếm theo chữ số chỉ cần list dem mười ô. Vị trí đầu của mỗi chữ số tính như bài sắp xếp đếm, rồi các số được đặt vào chỗ theo thứ tự cũ, nên lượt này ổn định:
def mot_luot(ds, k):
dem = [0] * 10
for x in ds:
dem[(x // 10 ** k) % 10] += 1
vi_tri = [0] * 10
for c in range(1, 10):
vi_tri[c] = vi_tri[c - 1] + dem[c - 1]
ket_qua = [0] * len(ds)
for x in ds:
c = (x // 10 ** k) % 10
ket_qua[vi_tri[c]] = x
vi_tri[c] += 1
return ket_qua
print(mot_luot([318, 74, 205, 9, 147, 380, 61], 0))KẾT QUẢ
[380, 61, 74, 205, 147, 318, 9]Kết quả giống dòng đầu của ví dụ trước. Tính ổn định cũng giữ đúng thứ tự cho bản ghi. Hàm luot_theo_km dưới đây là mot_luot đọc chữ số của t[1] thay cho của x. Hai lượt của nó xếp các tuyến (ten, so_km) theo số km:
def luot_theo_km(tuyen, k):
dem, vi_tri = [0] * 10, [0] * 10
for t in tuyen:
dem[(t[1] // 10 ** k) % 10] += 1
for c in range(1, 10):
vi_tri[c] = vi_tri[c - 1] + dem[c - 1]
ket_qua = [None] * len(tuyen)
for t in tuyen:
ket_qua[vi_tri[(t[1] // 10 ** k) % 10]] = t
vi_tri[(t[1] // 10 ** k) % 10] += 1
return ket_qua
tuyen = [("A", 28), ("B", 21), ("C", 18), ("D", 25)]
for k in range(2):
tuyen = luot_theo_km(tuyen, k)
print(tuyen)KẾT QUẢ
[('B', 21), ('D', 25), ('A', 28), ('C', 18)]
[('C', 18), ('B', 21), ('D', 25), ('A', 28)]Ở lượt hai, ba tuyến 21, 25, 28 cùng hàng chục 2. Chúng giữ thứ tự 1, 5, 8 của lượt một nên ra đúng thứ tự tăng dần. Một lượt không ổn định có thể đổi chỗ chúng và làm hỏng kết quả.
Số lượt, số âm và list rỗng
Với d là số chữ số của số lớn nhất, radix sort chạy d lượt, mỗi lượt tốn O(n + 10). Tổng cộng là O(d · n), theo cách đếm của bài Big O. Khi d nhỏ, ví dụ số vé dưới một nghìn, nó tốn d lượt, mỗi lượt chỉ mười ô đếm, thay cho list đếm một nghìn ô của counting sort.
Cách lấy chữ số của bài chỉ đúng với số không âm. Phép // của Python làm tròn xuống, nên chữ số hàng đơn vị của -5 thành 5:
ds = [12, -5, 3]
for k in range(len(str(max(ds)))):
ds = sorted(ds, key=lambda x: (x // 10 ** k) % 10)
print(ds)
print("Chữ số hàng đơn vị của -5:", (-5 // 1) % 10)KẾT QUẢ
[3, 12, -5]
Chữ số hàng đơn vị của -5: 5Với dữ liệu có số âm, hãy cộng mọi số với -min(ds) trước khi xếp rồi trừ lại sau, giống cách dời theo số nhỏ nhất của counting sort.
Kiểm tra nhanh
Biểu thức
(4721 // 10 ** 2) % 10cho kết quả bao nhiêu?2747
Những điều nào đúng với radix sort của bài?
- Lượt cuối xếp theo chữ số cao nhất của số lớn nhất
- Mỗi lượt có thể dùng bất kỳ cách xếp nào, kể cả không ổn định
- Số lượt bằng số chữ số của số lớn nhất
- Nó xếp đúng số âm mà không cần sửa gì
Xếp
[31, 13, 22]theo hàng chục trước rồi mới theo hàng đơn vị, mỗi lượt ổn định. Kết quả là gì?[13, 22, 31][31, 22, 13][22, 31, 13]
Gọi
len(str(max([])))thì sao?- Trả về
0 - Trả về
1 - Báo lỗi ValueError
- Trả về
Bài tập
Ghi lại từng lượt của radix sort
Mỗi số trong ds là số vé, nguyên và không âm. Viết thân hàm cac_luot_radix(ds) xếp tăng dần bằng radix sort, từ hàng đơn vị lên, và ghi lại list sau mỗi lượt. Số lượt bằng số chữ số của số lớn nhất, chữ số hàng thứ k là (x // 10 ** k) % 10. Mỗi lượt là một lần sắp xếp đếm ổn định theo chữ số đó, làm trên kết quả của lượt trước. List rỗng thì không có lượt nào. Không dùng phép so nào (<, <=, >, >=, ==, !=), không dùng min(), tham số key, sorted() hay sort(), và không sửa ds.
Ví dụ: cac_luot_radix([318, 74, 205, 9, 147, 380, 61]) trả về [[380, 61, 74, 205, 147, 318, 9], [205, 9, 318, 147, 61, 74, 380], [9, 61, 74, 147, 205, 318, 380]].
Trả về: các list sau từng lượt theo thứ tự, một list.
def cac_luot_radix(ds):
pass # Viết thân hàm thay cho dòng nàyTóm tắt
Radix sort xếp số nguyên theo từng chữ số, từ hàng đơn vị lên tới chữ số cao nhất của số lớn nhất.
Chữ số hàng thứ
klà(x // 10 ** k) % 10; số ngắn được coi như có các số 0 ở đầu.Mỗi lượt phải ổn định, thường là một lần counting sort với mười ô đếm.
Xếp từ chữ số cao xuống bằng cách này cho kết quả sai mà không báo lỗi.
Thời gian là O(d · n) với
dchữ số; cần xử lý riêng list rỗng và số âm.
Câu hỏi thường gặp
Sắp xếp theo cơ số (radix sort) là gì và khi nào nên dùng?
Đó là cách xếp số nguyên bằng nhiều lượt sắp xếp đếm, mỗi lượt theo một chữ số. Nó hợp với nhiều số nguyên có ít chữ số, như mã vé hay mã bưu chính, khi khoảng giá trị quá rộng để đếm trực tiếp.
Vì sao radix sort phải bắt đầu từ hàng đơn vị?
Vì lượt cuối quyết định thứ tự chính, nên chữ số quan trọng nhất phải được xếp sau cùng. Các lượt trước chỉ phân xử những số bằng nhau ở các hàng cao hơn, nhờ tính ổn định của mỗi lượt. Có một biến thể xếp từ hàng cao xuống, nhưng nó phải chia dãy thành từng nhóm theo chữ số đầu rồi xếp riêng từng nhóm.
Có xếp được chuỗi bằng radix sort không?
Có, nếu các chuỗi cùng độ dài và chỉ gồm một tập ký tự nhỏ, ví dụ mã vé gồm sáu chữ số. Mỗi lượt xếp theo một vị trí ký tự, từ vị trí cuối lên vị trí đầu, tương tự hàng đơn vị lên hàng cao. Với chuỗi tùy ý, hãy dùng sorted() như bài tổng quan thuật toán sắp xếp.
Cơ số 10 có phải là lựa chọn duy nhất không?
Không. Cơ số là số ô đếm của mỗi lượt: cơ số 10 dùng chữ số thập phân, còn cơ số 256 xếp theo từng byte. Cơ số lớn hơn cho ít lượt hơn nhưng list đếm dài hơn, nên lựa chọn phụ thuộc vào dữ liệu.
Chủ đề
Bài này có hữu ích?
Hỏi đáp
Tham vấn chuyên môn
Nhà sáng lập AIDev và VietPlatform · Thạc sĩ AI MSE
- Tốt nghiệp thủ khoa xuất sắc Thạc sĩ AI MSE.
- Đồng sáng lập, CTO E-University, SVOnline: số hóa 10+ đại học, 40.000+ sinh viên.
- Xây hệ thống AI cho doanh nghiệp tại VietPlatform.