Cùng một bài, đọc bằng chữ. Nhanh hơn và tìm lại được bằng Ctrl+F.
Sắp điểm của 1000 sinh viên
- Tạo ôĐiểm từ 0 đến 10, nên tạo 11 ô đếm
- ĐếmGặp một điểm thì tăng ô tương ứng lên một
- Rải lạiĐi từ ô 0 đến ô 10, ghi ra theo thứ tự
- XongKhông so hai sinh viên nào với nhau
k là độ rộng khoảng giá trị
k không phải số phần tử, cũng không phải số giá trị thực sự xuất hiện. Nó là giá trị lớn nhất trừ nhỏ nhất rồi cộng một. Điểm 0 đến 10 cho k bằng 11.
Công thức
Thời gian chạy là O(n + k)
Vì sao đi vòng qua được n log n
Giới hạn n log n là một định lý, nhưng nó chỉ áp cho thuật toán sắp xếp bằng cách so sánh các phần tử. Counting sort không so sánh, nó dùng thẳng giá trị để đếm.
Counting sort được gì, mất gì
Ưu điểm
O(n + k), nhanh hơn khi khoảng giá trị hẹp
Ổn định nếu cài đúng, dùng được cho radix sort
Không đệ quy, code ngắn và đi thẳng
Nhược điểm
Khoá phải là số nguyên, hoặc ánh xạ được
Tốn O(k) bộ nhớ, k rộng là hỏng
Không sắp được theo thứ tự tự định nghĩa
Hết loạt bảy thuật toán sắp xếp
Lưu cả loạt lại, khi nào quên thì mở bài bản đồ ra xem trước.
