基数排序(radix sort)

适用级别:提高组
难度系数:6

算法描述

将所有待比较数值统一为同样的数位长度,数位较短的数前面补零。然后,从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列

1、基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。
2、基数排序法是属于稳定性的排序,基数排序法的是效率高的稳定性排序法。
3、基数排序(Radix Sort)是桶排序的扩展。

基数排序图文说明:

1、原始数组

4203651324223910779142385930

2、第一次以每个元素的个位放入对应的桶中

930
910
420
142
42
132
23385
365
779
0123456789

3、将桶中的元素取出,放入原数组

4209109301324214223365385779

4、第二次以每个元素的十位放入对应的桶中,没有十位的放入0号桶

91023
420
132
930
142
42
365779385
0123456789

5、将桶中的元素取出,放入原数组

9104202393013242142365779385

6、第三次以每个元素的百位放入对应的桶中,没有百位的放入0号桶

42
23
142
132
385
365
420779930
910
0123456789

将桶中的元素取出,放入结果数组

2342132142365385420779910930

代码实现:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
/**************************************************************** 
 * Description: C++ implementation of Radix Sort 
 * Author: Alex Li
 * Date: 2023-06-09 15:59:05
 * LastEditTime: 2023-07-15 09:08:04
****************************************************************/

#include <iostream>
using namespace std;

//取得数组最大值 
int getMax(int arr[],int n){
    int mx=arr[0];
    for (int i = 1; i <n; i++){
       if(arr[i]>mx)mx=arr[i];
    }
    return mx;
}

//计数排序,根据某一位exp
//counting sort of arr according to the digit representated by exp.
void countSort(int arr[],int n, int exp){
    
    int output[n];//准备输出的数组output array
    int i,count[10]={0};

//用count[]存储计数
//store count of occurrences in count[]
    for (i=0;i<n;i++)count[(arr[i]/exp)%10]++;
//让count[]数组存储实际在输出组output[]中的位置
//change count[i] so that count[i] now contains actual position of this digit in output[]
    for ( i =1; i <10; i++)count[i]+=count[i-1];
//生成输出数组output[]
//build the output array
    for (i=n-1;i >=0; i--){
        output[count[(arr[i]/exp)%10]-1]=arr[i];
        count[(arr[i]/exp)%10]--;
    }
//复制output[]数组到arr[]数组,arr[]数组就是按当前某位排序的数组
//copy the output array to arr[], so that arr[] now contains sorted numbers according to current digit.
    for ( i = 0; i <n; i++)arr[i]=output[i];
    
}

//the main function to that sorts arr[] of size n using Radix Sort
void radixSort(int arr[],int n){

//find the maximum number to know number of digits
    int m=getMax(arr,n);
//每一位按计数排序    
//do counting sort for every digit. note that instead of passing digit number 
//exp是10的次方,从10^0次方开始,调用计数排序按每一位排序
//exp is passed. exp is 10^i, where i is current digit number
    for (int exp =1; m/exp>0; exp*=10){
        countSort(arr,n,exp);
    }
}
//打印数组
//print an array
void print(int arr[],int n){
    for (int i=0;i<n ;i++)cout<<arr[i]<<' ';
}

//主函数
//driver code 
int main(){
    int arr[]={180,35,75,90,802,24,2,86};
    int n=sizeof(arr)/sizeof(arr[0]);

//function call
    radixSort(arr,n);
    print(arr,n);
    return 0;
}
Scroll to Top