如何快速排序多列

Question

我想在php中快速输入一些对象.

我正在排序一系列OBJECTS

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

我想首先按x排序,然后是y,然后是z.

这是我的快速排序函数,它接受一个jobjects数组,并按特定的sortkey(x,y或z列)排序.该函数返回一个排序的对象数组,这些对象已经按sortkey排序.

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次真是搞糟了.

有没有我可以看到的算法？

Answer 1

你需要一种不同于最初想法的方法.不是递归排序,而是只进行一次排序,以排名的方式同时考虑所有标准(即,如果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继续排序.