STDIO
Tìm kiếm gần đây
    Nội dung
    0
    0
    Chia sẻ
    Nội dung
    0
    0
    Chia sẻ

    Distribution Sort - Bucket Sort

    Bucket Sort hữu dụng  khi cần sắp xếp các dãy số nằm trong một điều kiện nhất định, ví dụ sắp xếp dãy số với các phần tử nằm trong khoảng 0.1 đến 1.0 hay là từ 1 đến 100.
    21/08/2016 18/08/2020 1 phút đọc
    Distribution Sort - Bucket Sort

    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ự.

    Bucket_Sort

    Độ 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];
    }

    Bài chung Series

    0 Bình luận
    Giải Thuật Lập Trình

    Giải Thuật Lập Trình

    STDIO Training - Chia sẻ các giải thuật lập trình từ cổ điển đến hiện đại.

    Khi bạn nhấn vào sản phẩm do chúng tôi đề xuất và mua hàng, chúng tôi sẽ nhận được hoa hồng. Điều này hỗ trợ chúng tôi có thêm kinh phí tạo nhiều nội dung hữu ích. Tìm hiểu thêm.
    STDIO

    Trang chính

    Công ty TNHH STDIO

    • 30, Trịnh Đình Thảo, Hòa Thạnh, Tân Phú, Hồ Chí Minh
      +84 28.36205514 - +84 942.111912
      developer@stdio.vn
    • 383/1 Quang Trung, Phường 10, Quận Gò Vấp, Hồ Chí Minh
      Số giấy phép ĐKKD: 0311563559 do sở Kế hoạch và Đầu Tư TPHCM cấp ngày 23/02/2012
    ©STDIO, 2013 - 2021