求数组中元素组合的最大字符串（转）

原文链接：https://www.fanhaobai.com/2017/04/array-form-max-string.html

题目

给定一个所有元素为非负的数组，将数组中的所有数字连接起来，求最大的那个数。

示例：
输入：

4,94,9,14,1

输出：

9944141

输入：

121,89,98,15,4,3451

输出：

98894345115121

解题思路

• 比较规则：分析 a 和 b 的排列，因为这 2 个数存在 2 种排列情况，既 a_b 和 b_a，若 a_b 组合值大于 b_a 组合，那么认为 a “大于” b，则 a 需要排列在 b 前面，反之则需要交换 a 和 b 的位置。同我们熟悉的排序算法唯一不同的是，这里不是直接通过比较 2 个元素值大小，而是需要通过排列后的 2 个新值进行大小比较。
• 排序算法：由于只是比较规则的不同，所以常用的排序算法（冒泡、快速、堆）一样适用。

这里使用冒泡排序来进行说明，每一趟找出待排序元素的最小值，算法执行流程如下：

编码实现

定义比较规则，ab 和 ba 组合后的数字进行值大小的比较：

1
2
3
4
5
6

function ($a, $b) {
    if ($a == $b) {
        return 0;
    }
    return $a . $b > $b . $a ? -1 : 1;
}

接收输入并输出结果：

1
2
3
4
5
6
7
8
9
10
11
12

function array_form_max_str(array $Arr) {
    foreach ($Arr as $value) {
        if ($value < 0) {
            return '';
        }
    }
    usort($Arr, "cmp");
    
    return implode('', $Arr);
}
//输入:4,94,9,14,1
echo array_form_max_str(explode(',', $input)), PHP_EOL;

原文:大专栏  求数组中元素组合的最大字符串（转）