华为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 核心算法选择这类自定义排序问题通常有两种实现路径修改比较函数在标准排序算法中注入自定义比较逻辑装饰-排序-去装饰模式为每个元素计算排序键值排序后再去除键值考虑到题目要求保持相同键值元素的相对顺序我们需要选择稳定排序算法。各语言内置的排序方法稳定性如下语言排序方法是否稳定Pythonsorted()是JSArray.sort()实现相关Cstd::stable_sort是Cqsort()否2.2 各语言实现方案2.2.1 Python实现Python的sorted()函数天然稳定且支持自定义键函数def sort_by_last_digit(arr): return sorted(arr, keylambda 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::vectorint sortByLastDigit(std::vectorint 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^53JavaScript会出现精度问题。解决方案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实现要特别注意内存管理和指针操作的正确性。