我需要实现一些特殊的排序算法。我有两个阵列:
$items = array(
array("id" => "…", "type" => "alpha"),
array("id" => "…", "type" => "beta"),
array("id" => "…", "type" => "company"),
array("id" => "…", "type" => "marketing"),
array("id" => "…", "type" => "beta"),
array("id" => "…", "type" => "company"),
array("id" => "…", "type" => "alpha"),
array("id" => "…", "type" => "alpha"),
array("id" => "…", "type" => "company"),
array("id" => "…", "type" => "marketing"),
[…]
);
$order = array("company", "marketing", "alpha", "beta" );
正如你可以想象的那样,我需要根据$order
中指定的顺序对$items
进行排序。
运行$items
并使用"type"作为键将所有内容索引到字典中。然后运行$order
,查找与该"类型"对应的项目列表,并将它们附加到排序列表中。在O(n+k)
中运行,k为|order|
。
您可以使用usort
使用自定义比较函数进行排序
usort($items, "cmp");
function cmp($a, $b)
{
$order = array("company" => 0, "marketing" => 1, "alpha" => 2, "beta" => 3);
$order_a = $order[$a["type"]];
$order_b = $order[$b["type"]];
if ($order_a == $order_b) {
return 0;
}
return ($order_a < $order_b) ? -1 : 1;
}
与Ozgur非常相似!!然而,我会内置功能来处理订单中未考虑的意外值。它们位于排序数组的末尾。
usort($items,"compare");
echo "<pre>";
print_r($items);
echo "</pre>";
function compare($a, $b) {
$order = array("company" => 1, "marketing" => 2, "alpha" => 3, "beta" => 4);
$ax = $order[$a['type']]; $bx = $order[$b['type']];
if ($ax < 1) return 1;
if ($ax == $bx) return 0;
return ($ax > $bx) ? 1 : -1;
}
您可以简单地实现用户排序函数:
function mySort($a, $b) {
global $order;
return array_search($a['type'], $order) - array_search($b['type'], $order);
}
然后做一个usort()
:
usort($items, 'mySort');
可能不是很有效,但它有效。
更新
为了避免多次调用array_search()
,您可以提前翻转$order
数组一次。这将用一个简单的查找取代array_search()
:
$reversed_order = array_flip($order);
function mySort($a, $b) {
global $reversed_order;
return $reversed_order[$a['type']] - $reversed_order[$b['type']];
}
应该更有效率。(演示)
使用usort,这是一种高效的PHP算法,可以根据您提供的条件运行。
http://php.net/manual/en/function.usort.php
这是一个正在运行的代码,您可以根据自己的数据对其进行基准测试:http://codepad.org/MRpZQkKk
如果你想改变排序标准,这将给你更多的控制权,从复杂性来看,它非常快,应该是O(n-logn)(内部快速排序),并且空间复杂性也较低。
以下是更多信息:PHP';usort申请了吗?
<?php
$items = array(
array("id" => "…", "type" => "alpha"),
array("id" => "…", "type" => "beta"),
array("id" => "…", "type" => "company"),
array("id" => "…", "type" => "marketing"),
array("id" => "…", "type" => "beta"),
array("id" => "…", "type" => "company"),
array("id" => "…", "type" => "alpha"),
array("id" => "…", "type" => "alpha"),
array("id" => "…", "type" => "company"),
array("id" => "…", "type" => "marketing"),
);
$order = array("company", "marketing", "alpha", "beta" );
$orderIndexes = array(); /* cache indexes of the order keys */
for($i = 0 ; $i < count($order) ; $i++ )
{
$orderIndexes[$order[$i]] = $i ;
}
/* we have something like :
$orderIndexes = array('company' => 0 , 'marketing' => 1 , ....);
*/
function myCriteria($item1,$item2) /* this is the function used to decide order */
{ global $orderIndexes;
$index1 = $orderIndexes[$item1['type']];
$index2 = $orderIndexes[$item2['type']];
return $index1 - $index2 ; // negative means $item1 precedes $item2
}
usort($items,"myCriteria");
print_r($items);
?>