Thuật toán sắp xếp đếm phân phối

T

thienvamai

quicksort độ phức tạp trung bình là O(nlogn) , độ phức tạp trường hợp xấu là O(n*n);
đếm phân phối đpt là O(Max+n) trong đó Max là giá trị lớn nhất dãy sắp xếp.
Nếu Max nhỏ thì có thể dùng đếm phân phối nhưng nếu Max lớn thì ko thể làm đc, hơn nữa bạn chỉ có thể đếm phân phối với dãy số, nhiều khi bạn ko chỉ phải sort 1 dãy số mà có thể là các xâu kí tự với nhau thì đếm phân phối ko thể thực hiện đc.
Quicksort thì ổn định với mọi cấu trúc dữ liệu.
theo mình thuật toán này khá đơn giản nên có thể xem trên wiki
http://en.wikipedia.org/wiki/Counting_sort
 
Last edited by a moderator:
M

mikelhpdatke

Cũng là 1 cách sort hay nhưng thường mình thấy dùng QS, BS hơn. Ứng dụng vào bài khác để làm thì hữu ích hơn :v
 
You must log in or register to reply here.
Top Bottom