Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Sắp xếp nhanh: chuỗi DSA của Coddy.
Bây giờ, chúng ta kết hợp pivot, partition và đệ quy thành thuật toán hoàn chỉnh.
Thử thách
DễGiờ 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 (function) tên là quickSort, 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.
Dùng phần tử cuối cùng làm chốt, chia các phần tử còn lại thành nhóm nhỏ hơn và nhóm lớn hơn, gọi đệ quy quickSort cho từng nhóm rồi kết hợp chúng theo thứ tự nhóm nhỏ hơn đã sắp xếp + chốt + nhóm lớn hơn đã sắp xếp. Mảng có 0 hoặc 1 phần tử vốn đã được sắp xếp, vì vậy hãy trả về nguyên mảng.
Bạn có thể dùng lại cách chia nhóm từ bài học trước.
Tự làm thử
#include <stdlib.h>
int* quickSort(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 Sắp xếp nhanh: chuỗi DSA
2Thuật toá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