解析：阅读程序-2

代码功能概述

这段代码实现了基数排序算法，用于对一个非负整数数组进行排序。

代码详细解析

1. 初始化（init函数）

  • 读取输入： 输入数组的元素个数 n 和进制 k，以及数组的 n 个元素。
  • 求最大值： 找到数组中的最大值，用于确定排序所需的位数。
  • 计算位数： 根据最大值和进制，计算出数组元素的最大位数 m。

2. 排序（solve函数）

  • 基数排序核心： 从最低位开始，逐位对数组进行排序。
  • 桶计数：
    • 对于当前位，使用一个计数数组 cnt 来统计每个数字出现的次数。
    • 将每个元素根据当前位的数字放入对应的桶中。
  • 排序：
    • 根据计数数组，将元素从后向前依次放入临时数组 temp 中。
    • 将临时数组 temp 的内容复制回原数组 val。
  • 进位： 将基数 base 乘以进制 k，准备排序下一位。

算法原理

基数排序是一种稳定的排序算法，它的核心思想是：

  • 将整数按位数切割成不同的数字，然后按每个位数分别进行排序。
  • 从最低位开始，每次排序都使用计数排序的思想。
  • 经过多轮排序后，整个数组就变得有序了。

时间复杂度

基数排序的时间复杂度通常是 O(d * (n + k))，其中：

  • d：数组元素的最大位数
  • n：数组元素个数
  • k：进制

当 k 远小于 n 时，基数排序的效率很高。

空间复杂度

基数排序的空间复杂度是 O(n + k)。

 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;
 }
Previous Topic
Back to Lesson
Next Topic