Radix sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó nó còn có tên là Postman’s sort. Nó không hề quan tâm đến việc so sánh giá trị của phần tử 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ử. | Sắp xếp bằng cơ số Radix sort Sắp xếp theo phương pháp cơ số Radix sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó nó còn có tên là Postman’s sort. Nó không hề quan tâm đến việc so sánh giá trị của phần tử 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ử. To: Lê Văn An hệ thống phân loại thư phân cấp Nước tỉnh, thành phố quận, huyện phường xã đường số nhà Thuật toán phân loại dựa theo thứ tự hàng của số tỉ triệu ngàn tram chục đơn vị Mô phỏng lại qui trình trên, để sắp xếp dãy a1, a2, ., an, giải thuật Radix Sort thực hiện như sau: ? Trước tiên, ta có thể giả sử mỗi phần tử ai trong dãy a1, a2, ., an là một số nguyên có tối đa m chữ số. ? Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, . Qua mỗi bước phân loại ta có được các phần tử có thứ tự theo hàng của nó. Khi ta phân loại đến số hạng thứ m thì tất cả các phần tử đã được sắp xếp Các bước thực hiện thuật toán như sau: 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 4 : Nối B0, B1, ., B9 lại (theo đúng trình tự) thành a. Bước 5 : k = k+1; Nếu k < m thì trở lại bước 2. Ngược lại: Dừng Ví dụ: Sắp xếp dãy số sau: 2134,6120,35,234,932,1034,9181,2288,5404,6771,0009 Phân theo hàng ngàn 0009 9 6771 8 5404 7 2288 6 9181 5 1034 4 0932 3 0234 2 0035 1 6120 0 2134 cs A 0 1 2 3 4 5 6 7 8 9 Phân theo hàng đơn vị Phân theo hàng ngàn Phân theo hàng đơn vị 0009 9 6771 8 5404 7 2288 6 9181 5 1034 4 0932 3 0234 5404 2 0035 1034 1 6120 6771 0234 0 2134 6120 9181 0932 2134 0035 2288 0009 cs A 0 1 2 3 4 5 6 7 8 9 Phân theo hàng ngàn Phân theo hàng chục 10 0009 9 2288 8 0035 7 5404 6 1034 5 0234 4 2134 3 0932 2 6771 1 9181 0 6120 cs A 0 1 2 3 4 5 6 7 8 9 Phân theo hàng ngàn Phân theo hàng chục 0009 9 2288 8 . | Sắp xếp bằng cơ số Radix sort Sắp xếp theo phương pháp cơ số Radix sort lại dựa trên nguyên tắc phân loại thư của bưu điện. Vì lý do đó nó còn có tên là Postman’s sort. Nó không hề quan tâm đến việc so sánh giá trị của phần tử 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ử. To: Lê Văn An hệ thống phân loại thư phân cấp Nước tỉnh, thành phố quận, huyện phường xã đường số nhà Thuật toán phân loại dựa theo thứ tự hàng của số tỉ triệu ngàn tram chục đơn vị Mô phỏng lại qui trình trên, để sắp xếp dãy a1, a2, ., an, giải thuật Radix Sort thực hiện như sau: ? Trước tiên, ta có thể giả sử mỗi phần tử ai trong dãy a1, a2, ., an là một số nguyên có tối đa m chữ số. ? Ta phân loại các phần tử lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, . Qua mỗi bước phân loại ta có được các phần tử có thứ tự theo hàng của nó. Khi ta phân loại đến số hạng thứ m thì tất cả các phần tử đã được sắp xếp Các bước thực hiện thuật toán như sau: Bước 1 :
