015-最大数（特殊排序）

组成最大数问题（特殊排序）

给定一组非负整数，将它们排列成最大的数。

解决方案

function largestNumber(nums) {
  // 将数字转换为字符串并自定义排序
  const sorted = nums.map(String).sort((a, b) => {
    return (b + a) - (a + b);
  });
  
  // 处理全0的情况
  if (sorted[0] === '0') return '0';
  
  return sorted.join('');
}

// 使用示例
console.log(largestNumber([3, 30, 34, 5, 9])); // 输出: "9534330"

算法解析：

1. 将数字转为字符串，便于拼接比较
2. 自定义排序：比较两种拼接方式 b+a 和 a+b，取更大的排列
3. 处理特殊情况（如全0数组）
4. 时间复杂度：O(n log n)（取决于排序算法）

深入理解最大数排序的比较逻辑

为了让你彻底理解这个比较逻辑，我用更直观的方式来解释。

核心思想：拼接比较

我们不是比较单个数字的大小，而是比较两个数字不同拼接方式的结果，选择能产生更大数值的排列方式。

比较规则

对于任意两个数字字符串 a 和 b：

1. 尝试两种拼接方式：a+b 和 b+a
2. 比较这两种拼接结果的大小
3. 把能形成更大数字的那个排列放在前面

为什么是 (b+a) - (a+b) 而不是反过来？

1. 从排序规则理解

JavaScript的 sort() 函数是这样工作的：

• 比较函数返回 负数：a 排在 b 前面
• 返回 正数：b 排在 a 前面

我们需要：

• 当 b+a > a+b 时，b 应该排在 a 前面 → 需要返回正数
• 当 b+a < a+b 时，a 应该排在 b 前面 → 需要返回负数

这正是 (b+a) - (a+b) 的计算结果：

• 如果 b+a 更大 → 结果为正 → b 排前面
• 如果 a+b 更大 → 结果为负 → a 排前面

2. 具体例子分析

例子1：比较 “3” 和 “30”

• b+a = “303”
• a+b = “330”
• 比较：303 - 330 = -27（负数）
• 结果：”3” 排在 “30” 前面 → 最终组合是 “330”（更大的组合）

例子2：比较 “9” 和 “34”

• b+a = “349”
• a+b = “934”
• 比较：349 - 934 = -585（负数）
• 结果：”9” 排在 “34” 前面 → 最终组合是 “934”（更大的组合）

3. 如果反过来写会怎样？

假设写成 (a+b) - (b+a)：

同样例子1：比较 “3” 和 “30”

• a+b = “330”
• b+a = “303”
• 比较：330 - 303 = 27（正数）
• 结果：”30” 排在 “3” 前面 → 最终组合是 “303”（更小的组合）

这明显不是我们想要的最大数！

视觉化理解

想象你有两个数字块，可以左右交换位置。每次比较时，你都尝试两种排列方式，然后选择能使整体数字更大的那种排列。

比较 "5" 和 "9":
排列1: 5 9 → 59
排列2: 9 5 → 95
95 > 59 → 所以把9放在前面

(b+a)-(a+b) 这个计算就是在自动帮我们做这个判断：

• 如果 ba > ab → 把b放前面
• 如果 ba < ab → 把a放前面

为什么这样能保证全局最优？

这种两两比较的方式满足传递性，也就是说：

• 如果 A+B > B+A
• 且 B+C > C+B
• 那么 A+C > C+A

因此，通过这种局部两两比较，最终能得到全局最优的排列。

总结

记住这个口诀：
“把能使拼接结果更大的那个数字放在前面“

用代码实现就是：

// 当b在前能使拼接结果更大时，返回正数让b排在前面
// 当a在前能使拼接结果更大时，返回负数让a排在前面
.sort((a, b) => (b + a) - (a + b))

这样最终排列出来的数字字符串就是可能的最大数组合。