Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Heap Sort, chuỗi DSA của Coddy.
Bây giờ, chúng ta kết hợp việc xây dựng đống và liên tục lấy phần tử lớn nhất.
Thử thách
Trung bìnhGiờ hãy kết hợp tất cả thành thuật toán hoàn chỉnh.
Viết một hàm có tên heapSort, nhận một mảng số nguyên và trả về mảng đã được sắp xếp theo thứ tự tăng dần.
Trước tiên, hãy tạo max-heap bằng cách vun xuống mọi nút không phải nút lá, từ chỉ số n/2 - 1 xuống 0. Sau đó, liên tục đổi chỗ nút gốc (giá trị lớn nhất) với phần tử cuối cùng của heap, giảm kích thước heap đi một đơn vị rồi vun nút gốc mới xuống.
Dùng hàm hỗ trợ vun xuống nhận
sizecủa heap hiện tại để bạn có thể thu nhỏ heap trong quá trình thực hiện.
Tự làm thử
#include <stdlib.h>
int* heapSort(int* arr, int arr_size, int* returnSize) {
// Viết code ở đây
*returnSize = arr_size;
return arr;
}
Tự kiểm traBài học này có một bài trắc nghiệm ngắn. Bắt đầu bài học để trả lời và theo dõi tiến độ.
Tất cả bài học trong Heap Sort, chuỗi DSA
2Thuật toán
Nó hoạt động như thế nào?Mã giảTriển khai (phần 1)Triển khai (phần 2)
Độ phức tạp thời gian và không gianTự luyện tập: Trình biên dịch C online