Triển khai (phần 1)
Bài học 5 trên 9 trong khóa học Sắp xếp cơ số, chuỗi DSA của Coddy.
Chúng ta sẽ xây dựng Radix Sort từ phép toán cốt lõi trở lên.
Thử thách
Trung bìnhMỗi lượt của Radix Sort là một lần sắp xếp đếm ổn định theo một chữ số. Trước tiên, hãy xây dựng thuật toán đó.
Viết một hàm có tên countingSortByDigit nhận một mảng số nguyên không âm arr và một giá trị hàng exp (1 cho hàng đơn vị, 10 cho hàng chục, 100 cho hàng trăm, ...), rồi trả về một mảng mới được sắp xếp theo chữ số (x / exp) % 10. Phép sắp xếp phải ổn định: các phần tử có cùng chữ số giữ nguyên thứ tự ban đầu.
Ví dụ, countingSortByDigit([170, 45, 75, 90, 2, 802, 24, 66], 1) trả về [170, 90, 2, 802, 24, 45, 75, 66] (được sắp xếp theo chữ số hàng đơn vị).
Tự làm thử
#include <stdlib.h>
int* countingSortByDigit(int* arr, int arr_size, int exp, 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