Triển khai (phần 1)
Bài học 5 trên 9 trong khóa học Merge Sort: loạt bài về DSA của Coddy.
Chúng ta sẽ xây dựng Merge Sort từ thao tác cốt lõi trở lên.
Thử thách
DễCốt lõi của Merge Sort là gộp hai danh sách đã được sắp xếp thành một danh sách đã sắp xếp. Trước tiên, hãy xây dựng phần đó.
Viết một hàm (function) tên là merge, nhận hai mảng số nguyên đã sắp xếp, left và right, rồi trả về một mảng đã sắp xếp duy nhất chứa tất cả phần tử của cả hai mảng.
Duyệt đồng thời cả hai mảng: liên tục lấy phần tử nhỏ hơn trong hai phần tử đầu. Khi một mảng hết phần tử, nối tất cả phần tử còn lại trong mảng kia vào cuối.
Tự làm thử
#include <stdlib.h>
int* merge(int* left, int left_size, int* right, int right_size, int* returnSize) {
// Viết code tại đây
*returnSize = 0;
return left;
}
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 Merge Sort: loạt bài về DSA
2Thuật toán
Cách hoạt động?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