Bagaimana untuk mengisih tatasusunan dan data dalam PHP?

Question

Soalan ini bertujuan sebagai rujukan berkenaan isu pengisihan tatasusunan dalam PHP. Mudah untuk berfikir bahawa kes khusus anda adalah unik dan patut ditanya soalan baharu, tetapi kebanyakannya sebenarnya hanyalah variasi kecil pada salah satu penyelesaian di halaman ini.

Jika soalan anda telah ditutup sebagai pendua soalan ini, sila hanya minta untuk membuka semula soalan anda jika anda boleh menerangkan sebab ia berbeza dengan ketara daripada semua soalan di bawah.

Bagaimana untuk mengisih tatasusunan dalam PHP?

Bagaimana untuk mengisih tatasusunan kompleks dalam PHP?

Bagaimana untuk mengisih pelbagai objek dalam PHP?

---

1. Asas tatasusunan satu dimensi; Tatasusunan berbilang dimensi, termasuk. Susunan objek termasuk. Isih satu tatasusunan berdasarkan tatasusunan yang lain

2. Gunakan pengisihan SPL

3. Isih stabil

Untuk jawapan praktikal menggunakan fungsi PHP sedia ada, lihat 1., dan untuk jawapan terperinci secara akademik tentang algoritma pengisihan (yang fungsi PHP laksanakan dan yang anda mungkin perlukan dalam kes yang sangat, sangat kompleks), lihat 2.

Answer 1

Baiklah, decezetelah merangkumi kebanyakan kaedah asas, saya akan cuba lihat jenis pengisihan yang lain

Isih menggunakan SPL

SplHeap

class SimpleHeapSort extends SplHeap {
    public function compare($a, $b) {
        return strcmp($a, $b);
    }
}

// Let's populate our heap here (data of 2009)
$heap = new SimpleHeapSort();
$heap->insert("a");
$heap->insert("b");
$heap->insert("c");

echo implode(PHP_EOL, iterator_to_array($heap));

Output

c
b
a

SplMaxHeap

Kelas SplMaxHeap menyediakan fungsi utama timbunan, mengekalkan nilai maksimum di bahagian atas.

$heap = new SplMaxHeap();
$heap->insert(1);
$heap->insert(2);
$heap->insert(3);

SplMinHeap

$heap = new SplMinHeap ();
$heap->insert(3);
$heap->insert(1);
$heap->insert(2);

Jenis pengisihan lain

Isih gelembung

Dipetik daripadaArtikel Wikipedia tentang jenis gelembung:

function bubbleSort(array $array) {
    $array_size = count($array);
    for($i = 0; $i 

Pilih isihan

Dipetik daripada Artikel Wikipedia tentang jenis pilihan: 



function selectionSort(array $array) {
    $length = count($array);
    for($i = 0; $i 

Isihan sisipan

Dipetik daripada Artikel Wikipedia tentang jenis sisipan: 



function insertionSort(array $array) {
    $count = count($array);
    for($i = 1; $i = 0 && $array[$j] > $element ) {
            $array[$j + 1] = $array[$j];
            $array[$j] = $element;
            $j = $j - 1;
        }
    }
    return $array;
}

Semacam bukit

Dipetik daripadaArtikel Wikipedia tentang Shellsort:



function shellSort(array $array) {
    $gaps = array(
            1,
            2,
            3,
            4,
            6
    );
    $gap = array_pop($gaps);
    $length = count($array);
    while ( $gap > 0 ) {
        for($i = $gap; $i = $gap && $array[$j - $gap] > $tmp ) {
                $array[$j] = $array[$j - $gap];
                $j -= $gap;
            }
            $array[$j] = $tmp;
        }
        $gap = array_pop($gaps);
    }
    return $array;
}

Penyisihan sikat

Dipetik daripadaArtikel Wikipedia tentang jenis sikat:



function combSort(array $array) {
    $gap = count($array);
    $swap = true;
    while ( $gap > 1 || $swap ) {
        if ($gap > 1)
            $gap /= 1.25;
        $swap = false;
        $i = 0;
        while ( $i + $gap  $array[$i + $gap]) {
                // swapping the elements.
                list($array[$i], $array[$i + $gap]) = array(
                        $array[$i + $gap],
                        $array[$i]
                );
                $swap = true;
            }
            $i ++;
        }
    }
    return $array;
}

Gabung Isih

Dari Artikel Wikipedia tentang isihan gabungan: 



function mergeSort(array $array) {
    if (count($array)  0 && count($right) > 0 ) {
        if ($left[0]  0 )
        array_push($result, array_shift($left));

    while ( count($right) > 0 )
        array_push($result, array_shift($right));

    return $result;
}

Isih Cepat

Dipetik daripada Artikel Wikipedia tentang jenis cepat: 



function quickSort(array $array) {
    if (count($array) == 0) {
        return $array;
    }
    $pivot = $array[0];
    $left = $right = array();
    for($i = 1; $i 

Susun dan susun

Dipetik daripada Artikel Wikipedia tentang pengisihan: 



function permutationSort($items, $perms = array()) {
    if (empty($items)) {
        if (inOrder($perms)) {
            return $perms;
        }
    } else {
        for($i = count($items) - 1; $i >= 0; -- $i) {
            $newitems = $items;
            $newperms = $perms;
            list($foo) = array_splice($newitems, $i, 1);
            array_unshift($newperms, $foo);
            $res = permutationSort($newitems, $newperms);
            if ($res) {
                return $res;
            }
        }
    }
}

function inOrder($array) {
    for($i = 0; $i  $array[$i + 1]) {
                return False;
            }
        }
    }
    return True;
}

Isih Radix

Dipetik daripada Artikel Wikipedia tentang jenis radix: 



// Radix Sort for 0 to 256
function radixSort($array) {
    $n = count($array);
    $partition = array();

    for($slot = 0; $slot age & 0xFF][] = &$array[$i];
    }

    $i = 0;

    for($slot = 0; $slot 

Answer 2

Tatasusunan asas satu dimensi

$array = array(3, 5, 2, 8);

Fungsi pengisihan yang berkenaan:

• 排序
• 排序
• 分类
• 排序
• natsort
• natcasesort
• ksort
• krsort

Satu-satunya perbezaan antara mereka ialah sama ada untuk mengekalkan perkaitan nilai kunci ("a”函数），是否按从低到高排序或反向排序（“r” >”），是否对值或键进行排序（“k”）以及如何比较值（“nat" berbanding biasa). Lihat http://php.net/manual/en/array.sorting.php untuk mendapatkan gambaran keseluruhan dan pautan kepada butiran lanjut.

Tatasusunan berbilang dimensi, termasuk tatasusunan objek

$array = array(
    array('foo' => 'bar', 'baz' => 42),
    array('foo' => ...,   'baz' => ...),
    ...
);

Jika anda ingin menekan kekunci setiap pasangan "foo" entri $array进行排序，则需要一个自定义比较函数。上面的 sort dan fungsi yang berkaitan berfungsi pada nilai mudah yang mereka tahu cara membandingkan dan mengisih. PHP tidak hanya "tahu" cara mengendalikan nilai kompleks seperti array('foo' => 'bar', 'baz' => 42);

Untuk melakukan ini, anda perlu mencipta fungsi perbandingan. Fungsi ini menerima dua elemen dan jika elemen dianggap sama, ia mesti kembali 0；如果第一个值较低，则必须返回低于 0 的值；如果认为第一个值低于 0，则必须返回高于 0 的值 jika nilai pertama lebih tinggi. Ini sahaja yang diperlukan:

function cmp(array $a, array $b) {
    if ($a['foo']  $b['foo']) {
        return 1;
    } else {
        return 0;
    }
}

Lazimnya, anda perlu menggunakan fungsi tanpa nama sebagai panggilan balik. Jika anda ingin menggunakan kaedah atau kaedah statik, lihat Cara Lain untuk Menentukan Panggilan Balik dalam PHP.

Kemudian anda boleh menggunakan salah satu fungsi berikut:

• usort
• uasort
• uksort

Sekali lagi, ia hanya berbeza sama ada persatuan nilai kunci dipelihara dan sama ada ia diisih mengikut nilai atau kunci. Sila baca dokumentasi mereka untuk mendapatkan butiran.

Contoh penggunaan:

usort($array, 'cmp');

usort 将从数组中取出两项并用它们调用您的 cmp 函数。因此 cmp() 将以 $a 的形式调用 array('foo' => 'bar', 'baz' => 42)和 $b 作为另一个 array('foo' => ..., 'baz' => ...)。然后该函数返回到 usort 哪个值更大或者它们是否相等。 usort 重复此过程，为 $a 和 $b 传递不同的值，直到数组排序完毕。 cmp 函数将被调用多次，至少与 $array 中的值一样多，并且值的不同组合每次代码>$a和$b.

Untuk membiasakan diri dengan idea ini, cuba yang berikut:

function cmp($a, $b) {
    echo 'cmp called with $a:', PHP_EOL;
    var_dump($a);
    echo 'and $b:', PHP_EOL;
    var_dump($b);
}

Apa yang anda lakukan ialah menentukan cara tersuai untuk membandingkan dua item dan itu sahaja yang anda perlukan. Ini berfungsi untuk pelbagai nilai.

Dengan cara ini, ini berfungsi dengan mana-mana nilai, yang tidak semestinya tatasusunan yang kompleks. Anda juga boleh membandingkan tatasusunan nombor mudah jika anda ingin melakukan perbandingan tersuai.

sort Isih mengikut rujukan tidak akan mengembalikan apa-apa yang berguna!

Perhatikan bahawa tatasusunan diisih di tempat, anda tidak perlu memberikan nilai pulangan kepada apa-apa. $array = sort($array) 会将数组替换为 true，而不是排序后的数组。只需 sort($array); Itu sahaja.

Perbandingan nombor tersuai

Jika anda ingin mengisih mengikut kekunci nombor baz, apa yang perlu anda lakukan ialah:

function cmp(array $a, array $b) {
    return $a['baz'] - $b['baz'];
}

Berkat kuasa math, ini akan mengembalikan nilai 0, bergantung pada $a 是否小于、等于或大于 $b.

Perhatikan bahawa ini adalah benar untuk float 值不起作用，因为它们会被简化为 int 并失去精度。请改用显式 -1、0 和 1 nilai pulangan.

Objek

Jika anda mempunyai pelbagai objek, ia berfungsi dengan cara yang sama:

function cmp($a, $b) {
    return $a->baz - $b->baz;
}

Fungsi

Anda boleh melakukan apa sahaja yang anda perlukan dalam fungsi perbandingan, termasuk fungsi panggilan:

function cmp(array $a, array $b) {
    return someFunction($a['baz']) - someFunction($b['baz']);
}

String

Pintasan untuk versi perbandingan rentetan pertama:

function cmp(array $a, array $b) {
    return strcmp($a['foo'], $b['foo']);
}

strcmp 完全符合 cmp 的预期，它返回 -1、0 或 1.

Operator Kapal Angkasa

PHP 7 memperkenalkan pengendali kapal angkasa, yang menyatukan dan memudahkan sama/kurang daripada/lebih besar daripada perbandingan merentas jenis: p>

function cmp(array $a, array $b) {
    return $a['foo']  $b['foo'];
}

Isih mengikut berbilang medan

Jika anda mahu mengisih terutamanya mengikut foo, tetapi jika dua elemen' foo adalah sama, kemudian mengisih mengikut foo 排序，但如果两个元素的 foo 相等，则按 baz:

function cmp(array $a, array $b) {
    if (($cmp = strcmp($a['foo'], $b['foo'])) !== 0) {
        return $cmp;
    } else {
        return $a['baz'] - $b['baz'];
    }
}

Bagi mereka yang biasa, ini bersamaan dengan pertanyaan SQL menggunakan ORDER BY foo, baz.
Lihat juga versi trengkas yang sangat ringkas inidan cara mencipta fungsi perbandingan sedemikian secara dinamik untuk sebarang bilangan kunci.

Isih mengikut susunan statik manual

Jika anda ingin mengisih elemen ke dalam "pesanan manual" seperti "foo", "bar", "baz" :

function cmp(array $a, array $b) {
    static $order = array('foo', 'bar', 'baz');
    return array_search($a['foo'], $order) - array_search($b['foo'], $order);
}

---

Untuk semua perkara di atas, jika anda menggunakan PHP 5.3 atau lebih tinggi (dan anda benar-benar perlu), gunakan fungsi tanpa nama untuk memendekkan kod anda dan mengelakkan fungsi global yang lain:

usort($array, function (array $a, array $b) { return $a['baz'] - $b['baz']; });

Ini ialah cara mudah untuk mengisih tatasusunan berbilang dimensi yang kompleks. Sekali lagi, ajar PHP cara menentukan antara dua item yang "lebih besar" biarkan PHP melakukan pengisihan sebenar.

Selain itu, untuk semua perkara di atas, untuk menukar antara tertib menaik dan menurun, hanya tukar parameter $a 和 $b. Contohnya:

return $a['baz'] - $b['baz']; // ascending
return $b['baz'] - $a['baz']; // descending

Isih satu tatasusunan berdasarkan tatasusunan yang lain

Terdapat juga yang mewah array_multisort yang membolehkan anda mengisih tatasusunan berdasarkan: Satu lagi:

$array1 = array( 4,   6,   1);
$array2 = array('a', 'b', 'c');

Hasil yang diharapkan di sini ialah:

$array2 = array('c', 'a', 'b');  // the sorted order of $array1

Ke sana menggunakan array_multisort:

array_multisort($array1, $array2);

Bermula dengan PHP 5.5.0, anda boleh menggunakan array_column untuk mengekstrak lajur daripada tatasusunan berbilang dimensi dan mengisih tatasusunan pada lajur itu:

array_multisort(array_column($array, 'foo'), SORT_DESC, $array);

Anda juga boleh mengisih berbilang lajur dalam mana-mana arah:

array_multisort(array_column($array, 'foo'), SORT_DESC,
                array_column($array, 'bar'), SORT_ASC,
                $array);

Bermula dalam PHP 7.0.0, anda juga boleh mengekstrak sifat daripada pelbagai objek.

---