基數(Radix)排序

基數(Radix)排序處理元素的方式與姓名按字母順序排序的方式相同。在這種情況下有26個基數，因為英語中有26個字母。 在第一遍中，姓名根據名字的第一個字母的昇冪進行分組。

在第二遍中，名稱根據第二個字母的昇冪進行分組。 同樣的過程一直持續到我們找到已排序的名稱列表。 存儲桶用於存儲每次傳遞中生成的名稱。 傳遞次數取決於具有最大字母的名稱的長度。

在整數的情況下，基數排序根據數字對數字進行排序。 比較從LSB到MSB的數字之間進行。 通過次數取決於具有最多位數的數字的長度。

複雜性

示例

考慮下麵給出的長度為6的數組。 使用基數(Radix)排序對數組進行排序。

A = {10, 2, 901, 803, 1024}

第1步 : 根據0位置的數字對列表進行排序。

10, 901, 2, 803, 1024

第2步 : 根據10位的數字對列表進行排序。

02, 10, 901, 803, 1024

第3步 : 根據100位的數字對列表進行排序。

02, 10, 1024, 803, 901

第4步 : 根據1000位的數字對列表進行排序。

02, 10, 803, 901, 1024

因此，在第4步中生成的列表是從基數排序序列的排序列表。

演算法

第1步 : 在ARR中找到最大的數字作為LARGE
第2步 : [INITIALIZE] SET NOP = LARGE 中的位數
第3步 : SET PASS =0
第4步 : 當 PASS <= NOP-1時， 重複第5步

第5步 : SET I = 0 並初始化存儲桶

第6步 : 當 I<A的長度時， 重複第5步至第7步

第7步 : SET DIGIT = A [I]中第PASS位的數字
第8步 : 將A[I]添加到編號為 DIGIT 的存儲桶中

第9步 : 增量DIGIT桶數
        [結束迴圈]
第10步 : 收集桶中的數字

        [結束迴圈]
第11步 : 結束

使用C語言來實現基數(Radix)排序的代碼如下 -

#include <stdio.h>
int largest(int a[]);
void radix_sort(int a[]);
void main()
{
    int i;
    int a[10]={90,23,101,45,65,23,67,89,34,23};
    radix_sort(a);
    printf("The sorted array is: \n");
    for(i=0;i<10;i++)
        printf(" %d\t", a[i]);
}

int largest(int a[])
{
    int larger=a[0], i;
    for(i=1;i<10;i++)
    {
        if(a[i]>larger)
        larger = a[i];
    }
    return larger;
}
void radix_sort(int a[])
{
    int bucket[10][10], bucket_count[10];
    int i, j, k, remainder, NOP=0, divisor=1, larger, pass;
    larger = largest(a);
    while(larger>0)
    {
        NOP++;
        larger/=10;
    }
    for(pass=0;pass<NOP;pass++) // Initialize the buckets
    {
        for(i=0;i<10;i++)
        bucket_count[i]=0;
        for(i=0;i<10;i++)
        {
            // sort the numbers according to the digit at passth place
            remainder = (a[i]/divisor)%10;
            bucket[remainder][bucket_count[remainder]] = a[i];
            bucket_count[remainder] += 1;
        }
        // collect the numbers after PASS pass
        i=0;
        for(k=0;k<10;k++)
        {
            for(j=0;j<bucket_count[k];j++)
            {
                a[i] = bucket[k][j];
                i++;
            }
        }
        divisor *= 10;

    }
}

執行上面示例代碼，得到以下結果 -

The sorted array is:
23
23
23
34
45
65
67
89
90
101

使用Java語言來實現基數(Radix)排序的代碼如下 -

public class Radix_Sort {
public static void main(String[] args) {
        int i;
        Scanner sc = new Scanner(System.in);
        int[] a = {90,23,101,45,65,23,67,89,34,23};
        radix_sort(a);
        System.out.println("\n The sorted array is: \n");
        for(i=0;i<10;i++)
            System.out.println(a[i]);
    }

    static int largest(inta[])
    {
        int larger=a[0], i;
        for(i=1;i<10;i++)
        {
            if(a[i]>larger)
            larger = a[i];
        }
        returnlarger;
    }
    static void radix_sort(inta[])
    {
        int bucket[][]=newint[10][10];
        int bucket_count[]=newint[10];
        int i, j, k, remainder, NOP=0, divisor=1, larger, pass;
        larger = largest(a);
        while(larger>0)
        {
            NOP++;
            larger/=10;
        }
        for(pass=0;pass<NOP;pass++) // Initialize the buckets
        {
            for(i=0;i<10;i++)
            bucket_count[i]=0;
            for(i=0;i<10;i++)
            {
                // sort the numbers according to the digit at passth place
                remainder = (a[i]/divisor)%10;
                bucket[remainder][bucket_count[remainder]] = a[i];
                bucket_count[remainder] += 1;
            }
            // collect the numbers after PASS pass
            i=0;
            for(k=0;k<10;k++)
            {
                for(j=0;j<bucket_count[k];j++)
                {
                    a[i] = bucket[k][j];
                    i++;
                }
            }
            divisor *= 10;
        }
    }
}

執行上面示例代碼，得到以下結果 -

The sorted array is:
23
23
23
34
45
65
67
89
90
101

使用C#語言來實現基數(Radix)排序的代碼如下 -

using System;
public class Radix_Sort {
public static void Main()
{
        int i;
        int[] a = {90,23,101,45,65,23,67,89,34,23};
        radix_sort(a);
        Console.WriteLine("\n The sorted array is: \n");
        for(i=0;i<10;i++)
            Console.WriteLine(a[i]);
    }

    static int largest(int[] a)
    {
        int larger=a[0], i;
        for(i=1;i<10;i++)
        {
            if(a[i]>larger)
            larger = a[i];
        }
        return larger;
    }
    static void radix_sort(int[] a)
    {
        int[,] bucket=new int[10,10];
        int[] bucket_count=new int[10];
        int i, j, k, remainder, NOP=0, divisor=1, larger, pass;
        larger = largest(a);
        while(larger>0)
        {
            NOP++;
            larger/=10;
        }
        for(pass=0;pass<NOP;pass++) // Initialize the buckets
        {
            for(i=0;i<10;i++)
            bucket_count[i]=0;
            for(i=0;i<10;i++)
            {
                // sort the numbers according to the digit at passth place
                remainder = (a[i]/divisor)%10;
                bucket[remainder,bucket_count[remainder]] = a[i];
                bucket_count[remainder] += 1;
            }
            // collect the numbers after PASS pass
            i=0;
            for(k=0;k<10;k++)
            {
                for(j=0;j<bucket_count[k];j++)
                {
                    a[i] = bucket[k,j];
                    i++;
                }
            }
            divisor *= 10;
        }
    }
}

執行上面示例代碼，得到以下結果 -

The sorted array is:
23
23
23
34
45
65
67
89
90
101