c++代码实现基数排序中比较次数和移动次数的计算

基数排序的比较次数和移动次数都与具体实现方式有关，下面给出一种可能的实现方式，计算比较次数和移动次数的代码如下：

#include <iostream>
#include <vector>
using namespace std;

int get_max(vector<int>& arr) {
    int max_val = arr[0];
    for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > max_val) {
            max_val = arr[i];
        }
    }
    return max_val;
}

int get_digit(int num, int d) {
    for (int i = 1; i < d; ++i) {
        num /= 10;
    }
    return num % 10;
}

void counting_sort(vector<int>& arr, int exp, int& cmp_cnt, int& mov_cnt) {
    vector<int> count(10, 0);
    vector<int> temp(arr.size(), 0);
    for (int i = 0; i < arr.size(); ++i) {
        count[get_digit(arr[i], exp)]++;
    }
    for (int i = 1; i < count.size(); ++i) {
        count[i] += count[i - 1];
    }
    for (int i = arr.size() - 1; i >= 0; --i) {
        int digit = get_digit(arr[i], exp);
        temp[count[digit] - 1] = arr[i];
        count[digit]--;
        cmp_cnt++;
        mov_cnt++;
    }
    for (int i = 0; i < arr.size(); ++i) {
        arr[i] = temp[i];
        mov_cnt++;
    }
}

void radix_sort(vector<int>& arr, int& cmp_cnt, int& mov_cnt) {
    int max_val = get_max(arr);
    for (int exp = 1; max_val / exp > 0; exp *= 10) {
        counting_sort(arr, exp, cmp_cnt, mov_cnt);
    }
}

int main() {
    vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    int cmp_cnt = 0;
    int mov_cnt = 0;
    radix_sort(arr, cmp_cnt, mov_cnt);
    cout << "比较次数：" << cmp_cnt << endl;
    cout << "移动次数：" << mov_cnt << endl;
    // 输出排序结果
    for (int i = 0; i < arr.size(); ++i) {
        cout << arr[i] << " ";
    }
    cout << endl;
    return 0;
}

在这个实现方式中，我们用函数 get_max 获取数组中的最大值，用函数 get_digit 获取一个数字的某一位数值。在计数排序中，我们用数组 count 统计每个数字出现的次数，并用数组 temp 存储排序结果。比较次数和移动次数则分别在计数排序中统计。在主函数中，我们调用 radix_sort 对数组进行排序，并输出比较次数和移动次数，以及排序结果。

需要注意的是，这里的比较次数和移动次数仅仅是在排序过程中的统计，实际比较次数和移动次数可能会更多，因为还可能存在一些其它的操作，比如函数调用等