Cộng đồng công nghệ thông tin

Thuật toán HeapSort trong lập trình C++ *)Đối tượng hướng đến: +)các bạn mới học lập trình +)các bạn muốn ôn lại kiến thức về thuật toán *)Nội dung: -)Sắp xếp vun đống  ( Heapsort ) dựa trên một cấu trúc dữ liệu được gọi là đống nhị phân ( binary heap ), gọi đơn giản là đống. Trong mục này chỉ nói về đống trong bài toán sắp xếp. HeapSort được ứng dụng nhiều cho việc sắp xếp(trên mảng, trên list đơn,list kép,..), nhưng để làm quen với nó nên mình chỉ trình bày trên mảng và thực hiện sắp xếp tăng dần . Nghe có vẻ phức tạp thế thôi nhưng bắt tay vào code luôn cũng không khó mấy :)) Không dài dòng nữa bắt đầu thôi. Đầu tiên ta phải biết được cái "đống" này là một mảng có quy luật như sau: Array[i]>=Array[j] và  Array[i]>=Array[j+1], trong đó j=2*i+1. vậy việc đầu tiên của chúng ta là phải sắp xếp "sơ sơ" sao cho mảng thỏa mãn yêu cầu trên, để làm được điều này, mình cần dùng đến hai hàm, hàm thứ nhất là hàm shift(có nghĩa là sự thay đổi), hàm thứ hai là hàm ...