5

我正在寻找快速排序 php 中的一些对象。

我正在对一组 OBJECTS 进行排序

$object->x;
$object->y;
$object->z;

我想先按 x 排序，然后是 y，然后是 z。

这是我的快速排序函数，它接受一个作业数组，并按特定的排序键（x、y 或 z 列）排序。该函数返回一个已排序的对象数组，这些对象已按排序键排序。

private function quicksort($objects, $sortKey) {
    if(count($objects) < 2) return $objects;

    $left = $right = array();

    reset($objects);
    $pivot_key = key($objects);
    $pivot = array_shift($objects);

    foreach($objects as $k => $v) {
        if($v->$sortKey < $pivot->$sortKey)
            $left[$k] = $v;
        else
            $right[$k] = $v;
    }

    return array_merge($this->quicksort($left,$sortKey), array($pivot_key => $pivot), $this->quicksort($right,$sortKey));
}

我可以使用快速排序递归算法轻松快速排序任何单个列，但是将它们组合在一起然后将这些子组排序到第 n 次真的让我很头疼。

有没有我可以看的算法？

4

3 回答 3

10

你需要一种不同于你最初想法的方法。而不是递归排序，只做一个排序，一次考虑所有标准，以排序的方式（即如果 x 相同，测试 y，等等）。

其他人已经指出了将这种称为比较函数作为参数的排序函数。比较函数给出了两个对象，并返回哪个对象比另一个更小/更大。

在您发布的代码中，您有以下比较：

    if($v->$sortKey < $pivot->$sortKey)

您需要调用自己的比较函数，而不是测试 $v->$sortKey < $pivot->$sortKey，例如

    if (smaller($v, $pivot))

在函数smaller()中，您定义您的规则。

private function smaller($obj1, $obj2) {
    if ($obj1->x < $obj2->x)
        return true;
    if ($obj1->x > $obj2->x)
        return false;
    if ($obj1->y < $obj2->y)
        return true;
    if ($obj1->y > $obj2->y)
        return false;
}

... 等等。如您所见，排序将确保根据 x 排序，并且在 x 相同（不是更小，不是更大）的情况下继续根据 y 排序。

于 2010-10-11T16:53:23.353 回答
2

您是否正在实施自己的排序？你检查过http://us3.php.net/usort吗？

usort() 可以接受比较函数，因此您可以实现几乎任何您想要的排序规则。

于 2010-10-11T16:50:35.267 回答
1

排序算法不依赖于比较的机制，只依赖于它返回一致的排序。您需要的是一个排序例程，它允许您指定自己的比较函数。

PHP 提供了三个：usort()、uasort() 和 uksort()。

于 2010-10-11T16:52:05.797 回答