阅读程序2解析

此程序为基数排序,详细算法讲解见相关章节。

 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
/**************************************************************** 
 * Description: 2022_CSP_S_2  
 * Author: Alex Li
 * Date: 2023-08-18 05:15:45
 * LastEditTime: 2023-08-18 10:19:12
****************************************************************/
#include <iostream>
using namespace std;
  
  const int MAXN = 105;
  
  int n, m, k, val[MAXN];
  int temp[MAXN], cnt[MAXN];
  
 void init() {
     cin >> n >> k;// n是元素个数,k是进制
     for (int i = 0; i < n; i++) cin >> val[i];
     int maximum = val[0];//设maximum是数组的最大值
     for (int i = 1; i < n; i++) //求出数组的最大值
         if (val[i] > maximum) maximum = val[i];
     m = 1; //m是位数
     while (maximum >= k) {//统计最高位数
         maximum /= k;
         m++;
     }
 }
 
 void solve() {
     int base = 1;
     for (int i = 0; i < m; i++) {//从低位到高位依次排序
         for (int j = 0; j < k; j++) cnt[j] = 0;//初始化cnt数组
         for (int j = 0; j < n; j++) cnt[val[j] / base % k]++;//桶计数,当前位数字
         for (int j = 1; j < k; j++) cnt[j] += cnt[j - 1];//前缀和
         for (int j = n - 1; j >= 0; j--) {//从后向前,按第m位排序,放到temp数组里
             temp[cnt[val[j] / base % k] - 1] = val[j];
             cnt[val[j] / base % k]--;
         }
         for (int j = 0; j < n; j++) val[j] = temp[j];//把temp数组结果回填到val数组
         base *= k;//位数提高一位
     }
 }
 
 int main() {
     init();
     solve();
     //输出数组
     for (int i = 0; i < n; i++) cout << val[i] <<' ' ;
     cout << endl;
     return 0;
 }
Scroll to Top