从多个预排序数组创建排序数组

Question

我想从可变数量的预排序数组中创建一个排序数组。

考虑到{A1, ..., An}是预排序数组，我希望创建At，它是{A1, ..., An}的组合，并以相同的方式排序。

例子：

Given :
A1 = [2, 4, 9, 16]
A2 = [-3, 4, 98, 116]
...
An = [1, 7, 17, 76, 512]

I would like :
At = [-3, 1, 2, 4, 4, 9, 16, 17, 76, 98, 116, 512] 

计算这个数组最有效的方法是什么？

谢谢

Answer 1

我已经实现了一个函数来做我想做的事情。

你觉得这次演出怎么样？你有什么改进的建议吗？

分类功能：

function sortPreSortedArrays($arrays, $comparisonFunction, $order = 'asc')
{
    $sortedArray = array();

    /* Sort */

    while(sizeof($arrays) !== 0)
    {
        /* Find the greatest value */

        $max = true;
        $keyMax = -1;

        foreach($arrays as $key => $array)
        {
            if($max === true || $comparisonFunction(end($array), $max))
            {
                $max = end($array);
                $keyMax = $key;
            }
        }

        /* Take the greatest value */

        array_push($sortedArray, array_pop($arrays[$keyMax]));
        if(sizeof($arrays[$keyMax]) === 0) unset($arrays[$keyMax]);
    }

    /* Return */

    if($order === 'asc')
        return array_reverse($sortedArray);
    else
        return $sortedArray;

比较功能：

function compareLogArrayDate($log1, $log2)
{
    $t1 = $log1['date'];
    $t2 = $log2['date'];

    return ($t1 > $t2) ? true : false;
}

编辑:为了提高性能，我尝试使用最有效的数组函数(array_pop O(1)而不是array_shift O(n) )。不过，我仍然在使用unset。：

Answer 2

这很简单。我们将A1..AN预排序列表和相同数量的索引I1..IN设置为零(对于基于零的列表)。现在我们需要从这里形成合并列表。为此，我们需要从所有这些列表中找到最小(或最大取决于初始排序顺序)元素。很明显，这是一个A1I1 A2I2 ..。ANIN元素所以我们只需要通过所有这些元素来选择最小的元素。假设它是A2中的元素。我们将其放入新的大列表中，并增加I2。现在我们有相同的情况，在开始，应该重复所有这些步骤，或停止，如果所有的清单用尽。

示例：

A1 = [1, 2, 6]
A2 = [2, 4, 5]

A = []
I1 = 0
I2 = 0
-------------
A = [1]
I1 = 1
I2 = 0
-------------
A = [1, 2]
I1 = 2
I2 = 0
-------------
A = [1, 2, 2]
I1 = 2
I2 = 1
...

Answer 3

$A1 = [2, 4, 9, 16];
$A2 = [-3, 4, 98, 116];
$An = [1, 7, 17, 76, 512];


// create arrays of ith elements
$return = call_user_func_array('array_map', [null, $A1, $A2, $An]);
// sort arrays
array_walk($return, 'sort');
// create new arrays
$return = call_user_func_array('array_merge', $return);
// remove null values lefted after first operation
$return = array_filter($return, 'is_scalar');
var_dump($return);