tailieunhanh - Cấu trúc dữ liệu : Một số phương pháp sắp xếp part 2

Khi thêm phần tử có khóa key vào bảng băm, hàm băm h(key) sẽ xác định địa chỉ i trong khoảng từ 0 đến M-1. · Nếu chưa bị xung đột thì thêm phần tử mới vào địa chỉ i này. · Nếu bị xung đột thì hàm băm lại lần 1 h1 sẽ xét địa chỉ cách i là 12, nếu lại bị xung đột thì hàm băm lại lần 2 h2 sẽ xét địa chỉ cách i 22 , , quá trình cứ thế cho đến khi nào tìm được trống và thêm phần tử vào địa chỉ này | 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ụ Cho dãy số a 701 1725 999 9170 3252 4518 7009 1424 428 1239 8425 7013 Phân lô theo hàng đơn vị 12 0701 11 1725 10 0999 9 9170 8 3252 7 4518 6 7009 5 1424 4 0428 3 1239 0999 2 8425 1725 4518 7009 1 7013 9170 0701 3252 7013 1424 8425 0428 1239 CS A 0 1 2 3 4 5 6 7 8 9 6 Các lô B dùng đê phân loại Phân lô theo hàng chục 12 0999 11 7009 10 1239 9 4518 8 0428 7 1725 6 8425 5 1424 4 7013 0428 3 3252 1725 2 0701 7009 4518 8425 1 9170 0701 7013 1424 1239 3252 9170 0999 CS A 0 1 2 3 4 5 6 7 8 9 Phân lô theo hàng trăm 12 0999 11 9170 10 3252 9 1239 8 0428 7 1725 6 8425 5 1424 7 4 4518 3 7013 0428 2 7009 7013 3252 8425 1725 1 0701 7009 9170 1239 1424 4518 0701 0999 CS A 0 1 2 3 4 5 6 7 8 9 Phân lô theo hàng ngàn 12 0999 11 1725 10 0701 9 4518 8 0428 7 8425 6 1424 5 3252 4 1239 3 9170 0999 1725 2 7013 0701 1424 7013 1 7009 0428 1239 3252 4518 7009 8425 9170 CS A 0 1 2 3 4 5 6 7 8 9 Lấy các phần tử từ các lô B0 B1 . B9 nối lại thành a 12 9170 11 8425 10 7013 9 7009 8 4518