【题目来源】
学而思编程：数位排序
【题目描述】
小猴对一个数的数位之和很感兴趣，今天他要按照数位之和给序列a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an排序。当两个数各个数位之和不同时，将数位和较小的排在前面，当数位之和相等时，将数值小的排在前面，保证所有整数互不相同。
例如，1001 10011001排在99 9999前面，因为1001 10011001的数位之和是2 22，而99 9999的数位之和18 1818。
又如，2 22排在101 101101前面，因为它们的数位之和相同，而2 22小于101 101101。
请你帮助小猴完成这个任务。
【输入】
第一行，包含一个正整数n nn；
第二行，包含n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an。
【输出】
一行，空格隔开的n nn个整数，表示排序之后的序列。
【输入样例】
5 2 4 1 5 3【输出样例】
1 2 3 4 5【核心思想】
问题分析：给定n nn个互不相同的正整数，要求按数位和升序排序，数位和相同时按数值大小升序排序。这是一个自定义排序问题，关键在于设计比较函数，先比较数位和，再比较原数值。
算法选择：
- 数位和计算：通过取模和除法逐位求和
- 自定义比较函数：
cmp(x, y)先比较cal(x)与cal(y)，相等时比较x与y - 标准排序：使用
sort配合自定义比较函数
关键步骤：
- 初始化：读取n nn和数组a [ 1.. n ] a[1..n]a[1..n]
- 数位和函数
cal(x)：sum = 0- 当
x > 0时循环：sum += x % 10：累加末位数字x /= 10：去掉末位
- 返回
sum
- 自定义比较函数
cmp(x, y)：- 若
cal(x) != cal(y)：返回cal(x) < cal(y)（数位和小的排前面） - 否则：返回
x < y（数位和相等时，数值小的排前面）
- 若
- 排序并输出：
sort(a + 1, a + n + 1, cmp)：按自定义规则排序- 输出排序后的数组
时间/空间复杂度：
- 时间复杂度：O ( n log n × d ) O(n \log n \times d)O(nlogn×d)，d dd为数字位数（数位和计算），排序O ( n log n ) O(n \log n)O(nlogn)，每次比较O ( d ) O(d)O(d)
- 空间复杂度：O ( n ) O(n)O(n)，存储数组
自定义排序的核心思想：
- 多级排序键：第一关键字为数位和，第二关键字为原数值，比较函数按优先级依次判断
- 稳定排序替代：若使用稳定排序，可先按数值排序，再按数位和排序；但自定义比较函数更直接高效
- 数位和计算：利用十进制特性，通过
%10和/10逐位分离，适用于任意正整数 - 互异性保证：题目保证所有整数互不相同，避免了相等元素时的排序歧义
- 适用于"多关键字排序"类问题，自定义比较函数是 C++ 中实现复杂排序规则的标准方法
【解题思路】
【算法标签】
#其他排序
【代码详解】
#include<bits/stdc++.h>usingnamespacestd;intn,a[100005];intcal(intx)// 计算数位和{intsum=0;while(x>0){sum+=x%10;x/=10;}returnsum;}boolcmp(intx,inty){if(cal(x)!=cal(y)){// 数位和不同时returncal(x)<cal(y);// 小的排前面}returnx<y;// 否则数值小的排前面}intmain(){cin>>n;for(inti=1;i<=n;i++)cin>>a[i];// 输入n个数sort(a+1,a+n+1,cmp);// 按照自定义方式排序for(inti=1;i<=n;i++)cout<<a[i]<<" ";return0;}【运行结果】
5 2 4 1 5 3 1 2 3 4 5
