基数排序是一种非比较算法，它使用计数排序作为子例程按词典（字典）顺序对数据进行排序。它非常适合按数字对整数和按字符对字符串进行排序，它按数字值将元素分配到存储桶中，从最低有效数字到最高有效数字重复排序以获得最终顺序。

基数排序算法

在计算 sort时，我们发现我们可以根据数组中元素的频率对数组进行排序。但唯一的困难是，如果元素的范围非常大，那么使用计数排序效率不高。

因此，我们提出了基数排序，我们应用从最低有效数字到最高有效数字逐位计数排序。

基数排序是一种稳定的排序方法，它使用计数排序作为子例程。建议仅对正数使用基数排序，但是通过对标准基数排序算法进行一些修改，我们也可以对包含负数元素的数组进行排序。

基数排序以升序对数组进行排序所涉及的步骤是——

  • 找到数组的最大元素，令其为max
  • 找出其中的位数max， 随它去k。
  • 对于每一个，我 i 范围从1到k，应用计数排序算法每个元素的最低有效数字。如果任意元素小于我 i 数字考虑00在它的位置（因为29也可以表示为029）。

使用此方法，您还可以对适合32/64 位数据类型（int、float、double 等）的数字进行排序，这在计数排序算法中实际上是不可能实现的。

注意 -如果您还没有经历过计数排序，请注意一次，因为它是基数排序的先决条件，如果您想按降序对数组进行排序，请调整计数排序函数以使其排序数组按相反顺序排列。

基数排序算法示例

假设我们有一个数组a = [682,244,73,6,535,123]- 

这里最大元素是682，有3 位数字，因此我们将对最低有效数字应用计数排序，即最后一位数 -

现在我们对数字的第二位应用计数排序，之后数字将根据最低有效数字 - 

现在是时候根据以下内容对数字进行排序了从右起的数字，即最高有效数字。- 

完成后，现在数组已按升序排序。

基数排序的伪代码

在伪代码中，我们将拥有函数RadixSort，它是实现基数排序功能的主要函数。

首先确定数组的最大元素，然后调用countingSort函数k时间在哪里k是上一步找到的最大元素的位数。

 

 
 
RadixSort(a[], n):
    // Finding the maximum element
    max=a[0]
    For (i=1 to n-1):
        If (a[i]>max):
            max=a[i]
            
    // Calling countingSort for 
    // k times using For loop.
    For (div=1 to max/div>0):
        countingSort(a, n, div)
        div=div*10

 
 
 

 

基数排序的实现
 

为了实现基数排序算法，我们将使用两个函数 -
 

  • radixSort -它需要一个数组（例如 a）及其大小（例如 n) 作为参数。首先，最大元素（max）存在于a确定后，然后使用变量div调用countingSort ，直到max / div > 0，其中，div乘以10每次迭代后。
  • countSort -它需要一个数组（a）， 尺寸 （n）， 和div作为参数。计数排序将根据获得的结果对数组进行排序 (a[i] / div) %10。其中( a [ i ] / div ) % 10在每次迭代中对应于的数字a[i]，其中，1 ≤ k ≤ X。


这里x表示，出现的位数max。
 

基数排序的C/C++实现
 

 

 
 
// C++ code for Radix Sort
#include<bits/stdc++.h>
using namespace std;

// Counting Sort function
void countingSort(int *a,int n,int div){
    // Making a count array of size 10, for counting 
    // the frequency of digits of array elements.
    int count[10];
    ;
    // Initializing all of its
    // entries with 0. 
    for(int i=0;i<10;i++)
        count[i]=0;
        
    // Increasing count of kth 
    // digit of a[i].
    for(int i=0;i<n;i++)
        count[(a[i]/div)%10]++;
        
    // Updating count[i] such that count[i] now contains
    // actual position of this digit in temp[].
    for(int i=1;i<10;i++)
        count[i]+=count[i-1];
        
    // Making a temporary array for 
    // storing the output.
    int temp[n];
    
    // Building the temporary array.
    for(int i=n-1;i>-1;i--){
        temp[count[(a[i]/div)%10]-1]=a[i];
        count[(a[i]/div)%10]--;
    }
    
    // Updating the elements in array.
    for(int i=0;i<n;i++)
        a[i]=temp[i];
}

// Radix Sort function
void radixSort(int a[], int n){
    // Finding the maximum element
    // of the array.
    int max=0;
    for(int i=0;i<n;i++)
        if(a[i]>max)
            max=a[i];
    
    // For each digit in max, calling 
    // the countingSort for ith digit. 
    for(int div=1;max/div>0;div*=10){
        countingSort(a,n,div);
    }
}

// Main function
int main(){
    // Initializing the array.
    int a[]={4,2,12,6,1,9,21};
    int n=7;
    // Applying the Radix sort function.
    radixSort(a,n);
    
    // Printing the array.  
    for(int i=0;i<n;i++)
        cout<<a[i]<<" ";
    
    return 0;
}

 
 
 

 

基数排序的Java实现
 

 

 
 
// Java code for Radix Sort
public class Main{
    // Counting Sort function
    static void countingSort(int a[],int n,int div){
        // Making a count array of size 10, for counting 
        // the frequency of digits of array elements.
        int count[]=new int[10];
        
        // Initializing all of its
        // entries with 0. 
        for(int i=0;i<10;i++)
            count[i]=0;
            
        // Increasing count of kth 
        // digit of a[i].
        for(int i=0;i<n;i++)
            count[(a[i]/div)%10]++;
            
        // Updating count[i] such that count[i] now contains
        // actual position of this digit in temp[].
        for(int i=1;i<10;i++)
            count[i]+=count[i-1];
            
        // Making a temporary array for 
        // storing the output.
        int temp[]=new int[n];
        
        // Building the temporary array.
        for(int i=n-1;i>-1;i--){
            temp[count[(a[i]/div)%10]-1]=a[i];
            count[(a[i]/div)%10]--;
        }
        
        // Updating the elements in array.
        for(int i=0;i<n;i++)
            a[i]=temp[i];
    }
    
    // Radix Sort function
    static void radixSort(int a[], int n){
        // Finding the maximum element
        // of the array.
        int max=0;
        for(int i=0;i<n;i++)
            if(a[i]>max)
                max=a[i];
        
        // For each digit in max, calling 
        // the countingSort for ith digit. 
        for(int div=1;max/div>0;div*=10){
            countingSort(a,n,div);
        }
    }
    
    // Main function
    public static void main(String args[]){
        // Initializing the array.
        int a[]={4,2,12,6,1,9,21};
        // Applying the Radix sort function.
        radixSort(a,a.length);
        
        // Printing the array. 
        for(int i=0;i<a.length;i++)
            System.out.print(a[i]+" ");
        
    }
}

 
 
 

 

基数排序的Python实现
 

 

 
 
# Python program for Radix Sort 

# Counting Sort Function
def countingSort(a, n, div):
    
    # Making a count array of size 10, for counting 
    # the frequency of digits of array elements.
    count = [0] * (10)
 
    # Increasing count of kth 
    # digit of a[i].
    for i in range(0, n):
        count[(a[i]//div)%10]+=1
 
    # Updating count[i] such that count[i] now contains
    # actual position of this digit in temp[].
    for i in range(1, 10):
        count[i]+=count[i-1]
 
    # Making a temporary array for 
    # storing the output
    temp = [0] * (n)
    
    # Building the temporary array.
    for i in range(n-1, -1, -1):
        
        temp[count[(a[i]//div)%10]-1]=a[i]
        count[(a[i]//div)%10]-=1
        
 
    # Updating the elements in array a.
    for i in range(0, len(a)):
        a[i] = temp[i]
 
# Radix Sort function
def radixSort(a, n):
 
    # Finding the maximum element
    # of the array.
    Max=a[0]
    for i in range(1,n):
        if(a[i]>Max):
            Max=a[i]
 
    # For each digit in max, calling 
    # the countingSort for ith digit. 
    div=1
    while Max/div>1:
        countingSort(a, n, div)
        div*=10
 
 
# Driver code

# Initializing the array.
a = [4, 2, 12, 6, 1, 9, 21]
# Applying the Radix sort function.
radixSort(a, len(a))
 
# Printing the array.
for i in range(len(a)):
    print(a[i],end=" ")

 
 
 

 

基数排序的 C# 实现
 

 

 
 
// C# code for Radix Sort
using System;

class Radix{
    // Cointing Sort function
    public static void countingSort(int[] a,int n,int div){
        // Making a count array of size 10, for counting 
        // the frequency of digits of array elements.
        int[] count=new int[10];
        
        // Initializing all of its
        // entries with 0. 
        for(int i=0;i<10;i++)
            count[i]=0;
            
        // Increasing count of kth 
        // digit of a[i].
        for(int i=0;i<n;i++)
            count[(a[i]/div)%10]++;
            
        // Updating count[i] such that count[i] now contains
        // actual position of this digit in temp[].
        for(int i=1;i<10;i++)
            count[i]+=count[i-1];
            
        // Making a temporary array for 
        // storing the output.
        int[] temp=new int[n];
        
        // Building the temporary array.
        for(int i=n-1;i>-1;i--){
            temp[count[(a[i]/div)%10]-1]=a[i];
            count[(a[i]/div)%10]--;
        }
        
        // Updating the elements in array.
        for(int i=0;i<n;i++)
            a[i]=temp[i];
    }
    
    // Radix Sort function
    public static void radixSort(int[] a, int n){
        // Finding the maximum element
        // of the array.
        int max=0;
        for(int i=0;i<n;i++)
            if(a[i]>max)
                max=a[i];
        
        // For each digit in max, calling 
        // the countingSort for ith digit. 
        for(int div=1;max/div>0;div*=10){
            countingSort(a,n,div);
        }
    }
    
    // Main function
    public static void Main(){
        // Initializing the array.
        int[] a={4,2,12,6,1,9,21};
        // Applying the Radix sort function.
        radixSort(a,a.Length);
        
        // Printing the array.  
        for(int i=0;i<a.Length;i++)
            Console.Write(a[i]+" ");
        
    }
}    

 
 
 

 

输出 - 1 2 4 6 9 12 211 2 4 6 9 1 2 2 1
 

基数排序的复杂度分析
 

基数排序时间复杂度
 

  •  
    最好的情况 -在最好的情况下，当数组已经排序时，我们不需要应用该算法，而是可以在数组的单次遍历中检查数组是否已排序。因此时间复杂度为O(n)在最好的情况下。
     
  •  
    最坏的情况 -在最坏的情况下，数组按相反顺序排序，我们需要应用计数排序（O(n)过程）对于k次。其中k是存在于中的最大元素中存在的位数a。
     


因此，总体时间复杂度为 O (n * k)
 

  • 平均情况 -在平均情况下，数组的元素是任意排列的，我们再次需要对数组应用计数排序k次。因此，在平均情况下，时间复杂度也是O (n * k)。


基数排序空间复杂度
 

由于我们在计数排序过程中使用了一个大小为 n 的 temp 数组和一个大小为 10 的 count 数组，因此空间复杂度为 O(n+b)。
 

其中，b 是原始数组中元素的基数，因为在上述情况下我们处理的是十进制数（基数为 10），所以 b = 10。
 

基数排序的应用
 

  • 在并行机器上运行基数排序非常有益，使得排序过程超快。
  • 它还用于构造 suffix_array （按排序顺序包含字符串的所有可能后缀的数组。）


例如，如果str="radix"则后缀数组将为 -
 

  • suf[0]="adix"
  • suf[1]="dix"
  • suf[2]="ix"
  • suf[3]="radix"
  • suf[4] =“x”


结论
 

  • 基数排序是一种非比较排序算法，在其实现中使用计数排序算法。
  • 除了整数之外，其他数据类型（例如字符串）也可以使用基数排序按字典顺序排序。
  • 基数排序的时间复杂度为O (n * k)，其中k是数组最大元素中存在的位数。
 
  

        # 排序算法
      
        # 数据结构
      
        # 算法
      
  
 
 Logo 
乐奇 Rokid 开放社区
 
 
 
  
更多推荐
  
cover
 
“什么值得买”兴趣消费服务接入乐奇AI眼镜，开启“看见即搜索”新体验
 
 
avatar 乐奇 Rokid 开放社区
 
cover
 
从佩戴到交互全面升级：乐奇Rokid发布Rokid Glasses 2，让AI眼镜更自然地融入日常
 
 
avatar 乐奇 Rokid 开放社区
 
cover
 
EDITH：让松灵PiPER机器人读懂人的眼神与手势
 
 
avatar 乐奇 Rokid 开放社区