华为OD机试：按个位数稳定排序数组的实现
1. 题目解析与需求拆解
这道华为OD机试题的核心要求是：对整型数组按照元素的个位数（十进制最低位）进行升序排序，同时保持个位数相同的元素在原数组中的相对顺序不变。这实际上考察了两个关键点：
- 稳定排序算法的应用：需要确保相同个位数的元素保持原始相对顺序
- 自定义排序规则的实现：需要提取数字的个位数作为排序依据
举个例子，给定数组[12, 34, 56, 72, 28, 91]，其个位数分别是[2,4,6,2,8,1]，排序后应该得到[91, 12, 72, 34, 56, 28]。注意其中12和72的个位数都是2，它们在结果中保持了原始输入时的相对顺序。
2. 算法设计与实现思路
2.1 核心算法选择
这类自定义排序问题通常有两种实现路径：
- 修改比较函数：在标准排序算法中注入自定义比较逻辑
- 装饰-排序-去装饰模式：为每个元素计算排序键值，排序后再去除键值
考虑到题目要求保持相同键值元素的相对顺序，我们需要选择稳定排序算法。各语言内置的排序方法稳定性如下：
| 语言 | 排序方法 | 是否稳定 |
|---|---|---|
| Python | sorted() | 是 |
| JS | Array.sort() | 实现相关 |
| C++ | std::stable_sort | 是 |
| C | qsort() | 否 |
2.2 各语言实现方案
2.2.1 Python实现
Python的sorted()函数天然稳定，且支持自定义键函数：
def sort_by_last_digit(arr): return sorted(arr, key=lambda x: x % 10)关键点：
x % 10获取个位数，lambda函数作为key参数传递给sorted()
2.2.2 JavaScript实现
现代JS引擎的Array.sort()通常是稳定的，但需要注意比较函数的写法：
function sortByLastDigit(arr) { return arr.slice().sort((a, b) => (a % 10) - (b % 10)); }注意：这里使用slice()创建副本以避免修改原数组
2.2.3 C++实现
使用std::stable_sort保证稳定性：
#include <algorithm> #include <vector> std::vector<int> sortByLastDigit(std::vector<int>& arr) { std::stable_sort(arr.begin(), arr.end(), [](int a, int b) { return (a % 10) < (b % 10); }); return arr; }2.2.4 C语言实现
由于qsort()不稳定，需要手动实现稳定排序：
#include <stdlib.h> typedef struct { int value; int index; } Element; int compare(const void* a, const void* b) { Element* ea = (Element*)a; Element* eb = (Element*)b; int lastA = ea->value % 10; int lastB = eb->value % 10; if (lastA != lastB) return lastA - lastB; return ea->index - eb->index; } void sortByLastDigit(int* arr, int size) { Element* elements = malloc(size * sizeof(Element)); for (int i = 0; i < size; i++) { elements[i].value = arr[i]; elements[i].index = i; } qsort(elements, size, sizeof(Element), compare); for (int i = 0; i < size; i++) { arr[i] = elements[i].value; } free(elements); }3. 边界条件与测试用例
3.1 常见边界情况
- 负数处理：
-123的个位数应该是3（-123 % 10在多数语言中得-3，需要特殊处理） - 大数处理：当数字超过
INT_MAX时的处理 - 空数组输入：应该返回空数组而非报错
- 全相同个位数：应保持原数组顺序不变
3.2 测试用例设计
| 输入数组 | 预期输出 | 测试要点 |
|---|---|---|
| [12, 34, 56, 72, 28, 91] | [91, 12, 72, 34, 56, 28] | 基本功能验证 |
| [-123, 45, -67, 89] | [45, -123, -67, 89] | 负数处理 |
| [111, 222, 333, 444] | [111, 222, 333, 444] | 全相同个位数 |
| [] | [] | 空数组处理 |
| [5, 15, 25, 35, 45] | [5, 15, 25, 35, 45] | 已排序数组保持顺序 |
4. 性能分析与优化
4.1 时间复杂度分析
各语言实现的时间复杂度主要取决于使用的排序算法：
- Python/Timsort: O(n log n)
- JavaScript: 通常为O(n log n)
- C++ std::stable_sort: O(n log n)
- C语言实现: O(n log n)
4.2 空间复杂度优化
对于C语言的实现，可以通过以下方式优化空间使用：
- 原位排序：修改原始数组而非创建副本
- 索引数组：只存储原始索引而非整个Element结构
- 基数排序：针对个位数排序的特殊性，可以使用基数排序的变种
优化后的C实现示例：
void sortByLastDigitOptimized(int* arr, int size) { int* indices = malloc(size * sizeof(int)); for (int i = 0; i < size; i++) indices[i] = i; // 使用插入排序保持稳定性 for (int i = 1; i < size; i++) { int key = arr[i] % 10; int orig_idx = indices[i]; int j = i - 1; while (j >= 0 && (arr[j] % 10) > key) { arr[j + 1] = arr[j]; indices[j + 1] = indices[j]; j--; } arr[j + 1] = arr[i]; indices[j + 1] = orig_idx; } free(indices); }5. 实际编码中的常见问题
5.1 负数处理陷阱
许多初学者会忽略负数取模的问题。在C/C++中，-123 % 10得到的是-3而非7。正确的处理方式应该是：
def get_last_digit(x): return abs(x) % 10 # 处理负数情况5.2 稳定性误解
有些开发者会误认为所有语言的sort()都是稳定的。实际上：
JavaScript在ES2019之前不要求sort()的稳定性，不同引擎实现可能不同
5.3 原地修改问题
在JavaScript中，Array.sort()会修改原数组。良好的实践应该是：
const sorted = [...arr].sort(compareFn); // 使用扩展运算符创建副本5.4 大数处理
当数字非常大时（超过2^53），JavaScript会出现精度问题。解决方案：
function getLastDigitBigInt(x) { return Number(BigInt(x) % 10n); }6. 扩展思考与变种题目
6.1 变种题目示例
- 按十位数排序：修改为
(x // 10) % 10 - 多级排序：先按个位数，再按十位数
- 字符串数字排序：处理字符串形式的数字
6.2 实际应用场景
- 文件排序：按文件大小末位数字分类
- 哈希分片：根据ID末位进行数据分片
- 视觉布局：按某种特征值末位分组展示
6.3 算法选择进阶
对于超大规模数据（如1亿个数字），可以考虑：
- 基数排序：针对固定位数特别高效
- 并行排序：利用多线程/多进程加速
- 外排序：处理无法全部装入内存的数据
我在实际华为OD机试模拟中发现，这类题目往往有运行时间限制，因此选择最直接的实现方式（如Python的sorted）通常是最稳妥的选择，除非题目明确要求优化空间复杂度。对于C/C++实现，要特别注意内存管理和指针操作的正确性。