Java/C语言中如何对已排序数组进行非字符串转换的字典排序

你需要的是基于字典序而非数值大小对整数数组排序，而且不能将元素转换为字符串。核心是实现一个自定义比较逻辑，通过数学运算提取数字的每一位来模拟字符串的逐位比较。下面分别给出Java和C语言的实现方案。

核心思路 #

要比较两个整数的字典序，我们可以通过以下步骤实现（无需转换为字符串）：

• 计算两个数字的位数，获取它们的最高位权重（比如数字15的权重是10，100的权重是100）
• 从最高位开始逐位比较：
  1. 提取两个数的当前最高位进行比较，若不同则直接返回比较结果
  2. 若当前位相同，则移除最高位（通过取余操作），继续比较下一位
• 若其中一个数是另一个数的前缀（比如1和10），则位数较少的数排在前面（符合"1" < "10"的字典序规则）

Java 实现 #

Java 中可以利用Arrays.sort()方法，传入自定义的Comparator来实现排序。由于int数组无法直接使用泛型比较器，我们可以先将其转换为Integer数组，排序后再转回int数组：

import java.util.Arrays;
import java.util.Comparator;

public class LexicographicalSort {
    public static void main(String[] args) {
        int[] arr = {1, 2, 3, 15, 22, 30, 100, 110, 150, 160, 250, 300};
        
        // 转换为Integer数组以使用自定义比较器
        Integer[] integerArr = Arrays.stream(arr).boxed().toArray(Integer[]::new);
        
        Arrays.sort(integerArr, new Comparator<Integer>() {
            @Override
            public int compare(Integer x, Integer y) {
                if (x == y) return 0;
                
                int lenX = getDigitCount(x);
                int lenY = getDigitCount(y);
                
                int weightX = 1;
                // 用循环计算权重，避免浮点数精度问题
                while (weightX * 10 <= x) {
                    weightX *= 10;
                }
                int weightY = 1;
                while (weightY * 10 <= y) {
                    weightY *= 10;
                }
                
                int tempX = x;
                int tempY = y;
                
                while (tempX > 0 && tempY > 0) {
                    int digitX = tempX / weightX;
                    int digitY = tempY / weightY;
                    
                    if (digitX != digitY) {
                        return digitX - digitY;
                    }
                    
                    // 移除最高位
                    tempX %= weightX;
                    weightX /= 10;
                    tempY %= weightY;
                    weightY /= 10;
                }
                
                // 若一个是另一个的前缀，位数少的在前
                return lenX - lenY;
            }
            
            // 计算数字的位数
            private int getDigitCount(int num) {
                if (num == 0) return 1;
                int count = 0;
                while (num > 0) {
                    count++;
                    num /= 10;
                }
                return count;
            }
        });
        
        // 转回int数组
        int[] sortedArr = Arrays.stream(integerArr).mapToInt(Integer::intValue).toArray();
        
        // 输出结果
        System.out.println(Arrays.toString(sortedArr));
        // 输出: [1, 100, 110, 15, 150, 160, 2, 22, 250, 3, 30, 300]
    }
}

C 语言实现 #

C 语言中可以使用标准库的qsort()函数，自定义比较函数来实现字典序排序：

#include <stdio.h>
#include <stdlib.h>

// 计算数字的位数
int getDigitCount(int num) {
    if (num == 0) return 1;
    int count = 0;
    while (num > 0) {
        count++;
        num /= 10;
    }
    return count;
}

// 自定义比较函数，用于qsort
int compareLexicographical(const void *a, const void *b) {
    int x = *(const int *)a;
    int y = *(const int *)b;
    
    if (x == y) return 0;
    
    int lenX = getDigitCount(x);
    int lenY = getDigitCount(y);
    
    int weightX = 1;
    // 用循环计算权重，避免浮点数精度问题
    while (weightX * 10 <= x) {
        weightX *= 10;
    }
    int weightY = 1;
    while (weightY * 10 <= y) {
        weightY *= 10;
    }
    
    int tempX = x;
    int tempY = y;
    
    while (tempX > 0 && tempY > 0) {
        int digitX = tempX / weightX;
        int digitY = tempY / weightY;
        
        if (digitX != digitY) {
            return digitX - digitY;
        }
        
        // 移除最高位
        tempX %= weightX;
        weightX /= 10;
        tempY %= weightY;
        weightY /= 10;
    }
    
    // 位数少的在前
    return lenX - lenY;
}

int main() {
    int arr[] = {1, 2, 3, 15, 22, 30, 100, 110, 150, 160, 250, 300};
    int size = sizeof(arr) / sizeof(arr[0]);
    
    qsort(arr, size, sizeof(int), compareLexicographical);
    
    // 输出结果
    printf("{");
    for (int i = 0; i < size; i++) {
        if (i > 0) printf(", ");
        printf("%d", arr[i]);
    }
    printf("}\n");
    // 输出: {1, 100, 110, 15, 150, 160, 2, 22, 250, 3, 30, 300}
    
    return 0;
}

注意事项 #

• 上述代码假设数组中的元素都是非负整数，如果需要处理负数，需要额外处理符号位的比较逻辑（比如负数的字典序通常排在正数前面，或者根据需求调整）
• 计算权重时使用了循环而非pow()函数，避免了浮点数运算可能带来的精度问题

内容的提问来源于stack exchange，提问作者Saxena Shekhar