thucnq

Heap sort là thuật toán chậm nhất trong số các thuật toán sắp xếp thuộc nhóm có độ phức tạp O(n log n), nhưng không giống như Merge và Quick sort nó không đòi hỏi sự đệ quy phức tạp hay nhiều mảng dữ liệu để xử lý. Điều này làm cho nó trở thành một lựa chọn hấp dẫn với tập dữ liệu rất lớn hàng triệu phần tử. Tuy nhiên sự lựa chọn thích hợp lúc nào cũng còn tùy thuộc vào kết cấu hạ tầng và mục tiêu của ứng dụng.


Heap sort hoạt động cũng như sự gợi ý trong tên gọi - nó bắt đầu bằng việc xây dựng một heap out của tập dữ liệu, và sau đó loại phần tử lớn nhất và đặt nó vào vị trí cuối của mảng được sắp xếp. Sau việc xóa phần tử lớn nhất, nó tái cấu trúc heap và di chuyển phần tử lớn nhất kế tiếp còn lại và đặt nó vào vị trí mở kế cuối của mảng được sắp xếp. Thao tác này được lặp lại cho tới khi không còn phần tử bên trái trong heap và mảng được sắp xếp đã đầy. Cách triển khai căn bản đòi hỏi hai mảng dữ liệu - một giữ heap và một giữ những phần tử đã được sắp xếp.

Việc thực hiện tiến trình sắp xếp chỉ trong một mảng duy nhất nhằm tiết kiệm không gian của mảng thứ hai là cần thiết, giải thuật sau đây dùng một ít kỉ xảo để chỉ sử dụng cùng một mảng cho lưu trử Heap và mảng đã được sắp xếp. Bất cứ khi nào một phần tử được xóa khỏi Heap, nó giải phóng một không gian lưu trử ở cuối mảng mà phần tử bị xóa có thể được đặt vào.

Copy this link and send via YM,MSN,AOL,ICQ..... Thuật toán sắp xếp vun đống Heap sort http://www.laptrinhviet.com/showthread.php?t=19822 Hãy gửi link này cho bạn bè trong list của bạn giúp mình nhé ;) thank nhiều