- Thùng đang dùng
- Vừa di chuyển
- Đã chép lại
- Đã đúng chỗ
Sắp xếp theo cơ số
Sắp xếp theo cơ số sắp xếp các số nguyên mà không bao giờ so sánh hai số với nhau. Nó sắp xếp danh sách theo chữ số hàng đơn vị, rồi hàng chục, rồi hàng trăm, mỗi lần chuyển các giá trị vào mười thùng và chép chúng trở lại theo thứ tự. Xem các thùng đầy dần ở hàng dưới danh sách, từng lần di chuyển một, và thấy danh sách được sắp xếp theo ngày càng nhiều chữ số. Nhấn Phát để xem quá trình sắp xếp, hoặc Bước và Lùi để đi từng lần di chuyển. Kéo thanh trượt bước để nhảy đến bất kỳ đâu. Các thùng 0 đến 9 nằm cạnh nhau ở hàng dưới danh sách. Các ô đếm số chữ số đã đọc, lần di chuyển và lượt. Chọn số cột, thứ tự ban đầu, hoặc tự nhập các số đến 999. Khi bảng được chọn, phím mũi tên đi từng bước, phím cách phát và tạm dừng, còn Home và End nhảy về đầu và cuối.
Cách nó hoạt động
- Chọn số cột và thứ tự ban đầu, hoặc tự nhập các số nguyên đến 999 để xem lượt hàng trăm.
- Nhấn Phát, hoặc dùng Bước và Lùi để chuyển từng giá trị một. Kéo thanh trượt bước để nhảy đến bất kỳ đâu trong quá trình sắp xếp.
- Theo dõi từng lượt: đếm các chữ số, chuyển mọi giá trị vào thùng của nó, rồi chép các thùng trở lại.
Cách sắp xếp theo cơ số hoạt động
Chỉ nhìn chữ số cuối của mỗi số và sắp xếp danh sách theo nó: đặt mỗi số vào một trong mười thùng, 0 đến 9, giữ nguyên thứ tự chúng đến, rồi chép lần lượt từng thùng trở lại. Làm tương tự với chữ số hàng chục, rồi hàng trăm. Vì mỗi lượt giữ thứ tự của các số có cùng chữ số, các lượt trước vẫn quyết định thứ tự giữa chúng, và sau lượt cuối cùng cả danh sách đã được sắp xếp.
Hoàn toàn không so sánh
Các thuật toán sắp xếp so sánh cần ít nhất khoảng n log₂ n phép so sánh trong trường hợp xấu nhất, dù dùng mẹo khéo léo nào. Sắp xếp theo cơ số tránh được giới hạn đó bằng cách đọc chữ số: mỗi lượt đọc một chữ số của mọi giá trị và di chuyển mọi giá trị hai lần, nên d chữ số cần d lượt và khối lượng công việc tăng theo n · d. Với danh sách dài gồm các khóa ngắn, điều này rất đáng: một triệu số đến 999 chỉ cần ba lượt, trong khi sắp xếp so sánh cần khoảng 20 triệu phép so sánh. Cái giá là nó chỉ dùng được cho khóa gồm chữ số hoặc ký tự, và cần chỗ cho các thùng.
Câu hỏi thường gặp
Sắp xếp theo cơ số hoạt động thế nào?
Nó sắp xếp các số theo chữ số cuối, rồi theo chữ số ngay trước đó, cứ thế đến chữ số đầu tiên. Mỗi lượt đặt các số vào mười thùng theo chữ số đó, giữ nguyên thứ tự, rồi chép các thùng trở lại. Sau lượt cho chữ số có nghĩa lớn nhất, danh sách đã được sắp xếp.
Vì sao bắt đầu từ chữ số cuối?
Vì mỗi lượt đều ổn định: các số có cùng chữ số giữ thứ tự mà các lượt trước đã tạo ra. Vì vậy lượt cuối, theo chữ số đầu tiên, quyết định thứ tự, và các số bằng nhau ở chữ số đó được phân định bởi các chữ số đã sắp xếp. Cách này gọi là sắp xếp theo cơ số LSD (chữ số có nghĩa nhỏ nhất).
Sắp xếp theo cơ số có nhanh hơn quicksort không?
Có thể, khi có nhiều khóa ngắn: khối lượng công việc tăng theo số giá trị nhân số chữ số, không có n log n. Với ít giá trị, khóa rất dài, hoặc dữ liệu không gồm chữ số, quicksort và merge sort thường nhanh hơn và đơn giản hơn.
Nó liên quan thế nào đến sắp xếp đếm?
Mỗi lượt của sắp xếp theo cơ số là một lần sắp xếp đếm trên một chữ số: đếm xem có bao nhiêu giá trị mang mỗi chữ số, tính xem mỗi thùng bắt đầu ở đâu, rồi chuyển các giá trị vào đó theo thứ tự.
Các số của tôi có bị gửi đi đâu không?
Không. Việc sắp xếp chạy trong trình duyệt của bạn, và các cài đặt gần nhất được lưu trong bộ nhớ cục bộ của trình duyệt này.
Sẵn sàng thử chưa?
Mở PictorX trong trình duyệt — không cần cài đặt, không cần thẻ tín dụng để bắt đầu.
Tới trình chỉnh sửa