如何对多列进行快速排序

发布于 2024-09-27 03:51:56 字数 885 浏览 2 评论 0原文

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

我正在对一个对象数组进行排序，

$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 次排序确实让我很困惑。

有我可以查看的算法吗？

原文

I'm looking to quicksort some objects in php.

i'm sorting an array of OBJECTS

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

I want to first sort by x, then y, then z.

This is my quicksort function
Where it accepts an array of jobjects, and sorts by a particular sortkey (x, y, or z column)
The function returns a sorted array of objects, that have been sorted by the 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));
}

I can easily quicksort any individual column using a quicksort recursive algorithm, but grouping them together and then sorting those subgroups to the nth time is really messing with my head.

Is there an algorithm that I could be looking at?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

拥抱影子 2024-10-04 03:51:56

您需要采用与最初想法不同的方法。不要递归排序，只进行一次排序，以排序的方式一次考虑所有您的标准（即，如果 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排序。

You need a different approach than your initial thought. Instead of sorting recursively, do only one sort that takes all your criteria into mind at once, in a ranked fashion (i.e. if x is same, test for y, and so on).

Others have already pointed to sorting functions that take a such called comparison function as an argument. The comparison function is given two of your objects and returns which object is smaller/greater than the other.

In the code you posted, you have this comparison:

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

Instead of the test $v->$sortKey < $pivot->$sortKey, you need a call to your own comparison function, e.g.

    if (smaller($v, $pivot))

In the function smaller(), you define your rules.

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;
}

... and so on. As you can see, the sorting will ensure ordering according to x, and in the case that x is same (not smaller, not greater) continue to order according to y.

回复收藏 0 原文