Triển khai (phần 2)
Bài học 6 trên 9 trong khóa học Sắp xếp cơ số, chuỗi DSA của Coddy.
Bây giờ, ta chạy thuật toán sắp xếp đếm theo từng chữ số một lần cho mỗi vị trí chữ số.
Thử thách
Trung bìnhBây 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à radixSort, nhận một mảng các số nguyên không âm và trả về mảng đã được sắp xếp theo thứ tự tăng dần, dùng thuật toán sắp xếp đếm theo từng chữ số một lần cho mỗi vị trí chữ số.
Tìm giá trị lớn nhất, sau đó lặp với exp = 1, 10, 100, ... Chừng nào vẫn còn chữ số ở vị trí đó, hãy chạy countingSortByDigit rồi nhân exp với 10.
Dùng lại thuật toán sắp xếp đếm từ bài học trước làm hàm hỗ trợ.
Tự làm thử
#include <stdlib.h>
int* radixSort(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 cơ số, chuỗi 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