Thuật toán Bucket Sort
Ý tưởng
Đặt các phần tử của mảng cần sắp xếp input vào các xô (bucket) thích hợp, sau khi đặt hết tất cả các phần tử vào trong các xô thì trong mỗi xô sắp xếp các phần tử trong xô theo thứ tự. Cuối cùng liên kết các xô lại trở thành mảng các phần tử đã được sắp xếp theo thứ tự.
Độ phức tạp của thuật toán là O(n log n).
Hiện thực
void bucketSort(float arr[], int n)
{
// Tạo các Bucket rỗng
vector<int> b[n];
// Đặt các phần tử vào các Bucket
for (int i = 0; i < n; i++)
{
int bi = n * arr[i]; // Địa chỉ của Bucket
b[bi].push_back(arr[i]);
}
// Sắp xếp trong từng Bucket
for (int i=0; i<n; i++)
sort(b[i].begin(), b[i].end());
// Liên kết tất cả các Bucket lại
int index = 0;
for (int i = 0; i < n; i++)
for (int j = 0; j < b[i].size(); j++)
arr[index++] = b[i][j];
}