Как быстро сортировать по нескольким столбцам

Question

Я хочу быстро отсортировать некоторые объекты в php.

Я сортирую массив ОБЪЕКТОВ

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

Я хочу сначала отсортировать по x, затем y, затем z.

Это моя функция быстрой сортировки, где она принимает массив заданий и сортирует по определенному ключу сортировки (столбец 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.

Answer 2

Вы реализуете свой собственный вид?Вы уже отметили, http://us3.php.net/usort?

usort () может принять функцию сравнения, так что вы можете реализовать практически любые правила упорядочения, которые вы хотите.

Answer 3

Алгоритмы сортировки не зависят от механизма сравнения, только в том, что он возвращает последовательный порядок.Вам нужна подпрограмма сортировки, которая позволяет вам указать собственную функцию сравнения.

Php предоставляет три функции: usort (), uasort () и uksort ().