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

    Distribution Sort - Radix Sort

    Distribution Sort - Radix Sort là thuật toán sắp xếp độ phức tạp thấp.
    28/01/2017 18/08/2020 3 phút đọc
    Distribution Sort - Radix Sort

    Sắp xếp là quá trình biến đổi danh sách các đối tượng thành một danh sách thoả mãn một thứ tự nào đó. Thuật toán sắp xếp đóng vai trò quan trọng và được ứng dụng nhiều vào trong lập trình. Trong số đó, Radix Sort là thuật toán hay, độ phức tạp thấp và được sử dụng nhiều trong thực tiễn.

    Thuật toán Radix Sort

    Radix Sort là thuật toán sắp xếp tiếp cận theo một hướng hoàn toàn khác các thuật toán sắp xếp khác, cơ sở để sắp xếp luôn là việc so sánh giá trị của 2 phần tử thì Radix Sort lại dựa theo nguyên tắc phân loại thư của bưu điện (Postman's sort).

    Radix sort không quan tâm đến việc so sánh giá trị của 2 phần tử mà bản thân việc phân loại và thứ tự phân loại sẽ tạo ra thứ tự cho các phần tử.

    Ý tưởng

    Giả sử mỗi phần tử ai trong dãy a0, a1, …, an-1 là một số nguyên có tối đa m chữ số. Phân loại các phần tử này lần lượt theo các chữ số hàng đơn vị, hàng chục, hàng trăm, …, tương tự việc phân loại thư theo tỉnh thành, quận huyện, phường xã, …

    Ví dụ

    Mảng A cần sắp xếp gồm các phần tử sau:

    964 354 368 128 495 121

    Phân lô theo hàng đơn vị:

    121                  
    495                  
    128                  
    368                  
    354       354       128  
    964 121     964 495     368  
    A 1 2 3 4 5 6 7 8 9

    Phân lô theo hàng chục:

    128                  
    368                  
    495                  
    354                  
    964   128       368      
    121   121     354 964     495
    A 1 2 3 4 5 6 7 8 9

    Phân lô theo hàng trăm:

    495                  
    368                  
    964                  
    354                  
    128 128   368            
    121 121   354 495         964
    A 1 2 3 4 5 6 7 8 9

    Mảng sau khi đươc sắp xếp:

    121 128 354 368 495 964

    Hiện thực hàm Radix Sort

    void radixSort(int *a, int n)
    {
    	int i, b[MAX], m = a[0], exp = 1;
    	for (i = 0; i < n; i++)
    	{
    		if (a[i] > m)
    			m = a[i];
    	}
    	while (m / exp > 0)
    	{
    		int bucket[10] ={  0 };
    		for (i = 0; i < n; i++)
    			bucket[a[i] / exp % 10]++;
    		for (i = 1; i < 10; i++)
    			bucket[i] += bucket[i - 1];
    		for (i = n - 1; i >= 0; i--)
    			b[--bucket[a[i] / exp % 10]] = a[i];
    		for (i = 0; i < n; i++)
    			a[i] = b[i];
    		exp *= 10;
    	}
    }

    Code mẫu Radix Sort

    #include <iostream>
    using namespace std;
    
    #define MAX 5
    
    void printArray(int *a, int n)
    {
    	for (int i = 0; i < n; i++)
    		cout << a[i] << "\t";
    }
    
    void radixSort(int *a, int n)
    {
    	int b[MAX], m = a[0], exp = 1;
    
    	for (int i = 0; i < n; i++)
    		if (a[i] > m)
    			m = a[i];
    
    	while (m / exp > 0)
    	{
    		int bucket[10] = {0};
    		for (int i = 0; i < n; i++)
    			bucket[a[i] / exp % 10]++;
    		for (int i = 1; i < 10; i++)
    			bucket[i] += bucket[i - 1];
    		for (int i = n - 1; i >= 0; i--)
    			b[--bucket[a[i] / exp % 10]] = a[i];
    		for (int i = 0; i < n; i++)
    			a[i] = b[i];
    		exp *= 10;
    	}
    }
    
    int main()
    {
    	int arr[MAX] = {25, 5, 9, 10, 6};
    	int i, n;
    
    	cout << endl << "Before sort  : ";
    	printArray(&arr[0], n);
    
    	RadixSort(&arr[0], n);
    
    	cout << endl << "After sort : ";
    	printArray(&arr[0], n);
    
    	return 0;
    }

    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