首页 > 代码库 > 基数排序算法

基数排序算法

2024-07-04 09:29:30   217人阅读

     基数排序思想：分配桶，把待排序的数字按照从低到高的顺序排列。主要有两个过程，分配和收集。

     分配时，根据数字的位数，从小到大存放到桶中。

     收集时，按照顺序，再覆盖原数组。

     重复分配和收集的过程，直到到数字的最高位。

      好长时间不写C++代码了。。。

     代码如下：

   

?
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
#include <iostream>
#include <cstdlib>
 
using namespace std;
 
int getNumInPos(int num,int k)
{
    int temp=1;
    for(int i=1;i<k;i++)
    {
         temp*=10;
    }
 
    return  (num/temp)%10;
}
 
void radix_sort(int arr[],int n,int k)
{
 
    int *radix_arr[10];
    for(int i=0;i<n;i++)
    {
        radix_arr[i]=(int *)malloc(sizeof(int)*(n+1));//分配桶
        radix_arr[i][0]=0;
    }
     
    for(int j=1;j<=k;j++)
    {
         int t;
        //分配数据分配到桶中
        for(int i=0;i<n;i++)
          {
            int digit=getNumInPos(arr[i],j);
            int index=++radix_arr[digit][0];
            radix_arr[digit][index]=arr[i];
          }
          //从桶中收集数据
          for(int i=0,t=0;i<n;i++)
          {
              for( int m=1;m<=radix_arr[i][0];m++)
              {
                   arr[t++]=radix_arr[i][m];
              }
              radix_arr[i][0]=0;
          }
 
    }
 
     
 
}
 
void print_arr(int arr[],int n)
{
    for(int i=0;i<n;i++)
       printf("%d,",arr[i]);
    printf("\n");
}
 
int main()
{
    int arr[10]={123,243,521,213,67,12,7,90,101,321};
    printf("基数排序前:");
    print_arr(arr,10);
    radix_sort(arr,10,3);
    printf("基数排序后:");
    print_arr(arr,10);
 
    return 0;
 
}

　　运行结果：

      

   

    


联系
我们