求一个数组排序的算法

Question

数据数组如下$data = array(
array(
'id' => 123,
'value' => 'a'
),
array(
'id' => 456,
'value' => 'b'
),
array(
'id' => 789,
'value' => 'c'
),
array(
'id' => 111,
'value' => 'd'
),
array(
'id' => 222,
'value' => 'e'
)
);
需要根据下面的数组排序$index = array(222, 111, 789, 123, 456);
目前只想到两次foreach 
此程序对性能有一定要求 所以在此求更好的算法

Answer 1

$data = array(
    array(
        'id' => 123,
        'value' => 'a'
    ),
    array(
        'id' => 456,
        'value' => 'b'
    ),
    array(
        'id' => 789,
        'value' => 'c'
    ),
    array(
        'id' => 111,
        'value' => 'd'
    ),
    array(
        'id' => 222,
        'value' => 'e'
    )
);$index = array(222, 111, 789, 123, 456);foreach($data as $v)
  $r[] = array_search($v['id'], $index);array_multisort($r, $data);print_r($data);Array
(
    [0] => Array
        (
            [id] => 222
            [value] => e
        )    [1] => Array
        (
            [id] => 111
            [value] => d
        )    [2] => Array
        (
            [id] => 789
            [value] => c
        )    [3] => Array
        (
            [id] => 123
            [value] => a
        )    [4] => Array
        (
            [id] => 456
            [value] => b
        ))

Answer 2

array_search相当于foreach，所以1楼的办法也是O（n^2)的复杂度.下面的办法复杂度是O（nlgn）（假设php中array作为hashmap查找操作的复杂度是O(lgn)）。
 $data = array(
    array(
        'id' => 123,
        'value' => 'a'
    ),
    array(
        'id' => 456,
        'value' => 'b'
    ),
    array(
        'id' => 789,
        'value' => 'c'
    ),
    array(
        'id' => 111,
        'value' => 'd'
    ),
    array(
        'id' => 222,
        'value' => 'e'
    )
);
$index = array(222, 111, 789, 123, 456);$datatoindex = array();
foreach ($data as $key => $value) {
$datatoindex[$value['id']] = $key;
}foreach ($index as $i) {
  $r[] = $data[$datatoindex[$i]];
}
print_r($r);

Answer 3

$datatoindex[$value['id']] = $key;
???
这需要 id 唯一仅从算法出发是不行的

Answer 4

只有id唯一，这个问题才有意义。id不唯一的话，下面的例子结果应该是什么？是abe还是eba，或者是aba？$data = array(
    array(
        'id' => 222,
        'value' => 'a'
    ),
    array(
        'id' => 456,
        'value' => 'b'
    ),
    array(
        'id' => 222,
        'value' => 'e'
    )
);
$index = array(222, 456, 222);