Bagaimana untuk melaksanakan algoritma bukan rekursif jenis cepat dalam PHP

Pengenalan

Isih cepat ialah algoritma pengisihan yang cekap yang mencapai pengisihan dengan membahagikan tatasusunan kepada dua sub-tatasusunan secara berterusan. Dalam algoritma quicksort, nilai pangsi dipilih dan semua elemen yang lebih kecil daripada nilai pangsi diletakkan di sebelah kirinya, manakala semua elemen yang lebih besar daripada nilai pangsi diletakkan di sebelah kanannya. Proses ini kemudiannya digunakan secara rekursif pada subarray kiri dan kanan sehingga keseluruhan tatasusunan diisih.

Isih cepat ialah fungsi rekursif kerana ia memerlukan memecahkan masalah asal kepada dua submasalah yang lebih kecil, dan kemudian menyelesaikan masalah asal dengan menyelesaikan submasalah ini secara rekursif. Walaupun pendekatan ini boleh berfungsi dengan berkesan dalam beberapa situasi, pendekatan ini mempunyai beberapa batasan. Khususnya, apabila memproses tatasusunan besar, algoritma rekursif mungkin menghabiskan ruang tindanan komputer, menyebabkan pengecualian limpahan tindanan. Selain itu, overhed tambahan bagi panggilan fungsi rekursif juga boleh menyebabkan kemerosotan prestasi algoritma.

Oleh itu, dalam beberapa kes, mungkin lebih sesuai untuk menggunakan pelaksanaan bukan rekursif. Dalam artikel ini, kami akan memperkenalkan algoritma bukan rekursif untuk isihan pantas menggunakan PHP.

Pelaksanaan Algoritma

Kami mula-mula mentakrifkan partition fungsi tambahan, yang digunakan untuk membahagikan tatasusunan kepada dua sub-tatasusunan: satu mengandungi semua elemen yang lebih kecil daripada nilai garis dasar, dan satu mengandungi semua elemen lebih besar daripada nilai asas.

function partition(&$arr, $left, $right) {
    $pivot = $arr[$right]; // 选择最后一个元素作为基准值
    $i = $left - 1;
    for ($j = $left; $j < $right; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            list($arr[$i], $arr[$j]) = array($arr[$j], $arr[$i]); // 交换i和j处的元素
        }
    }
    list($arr[$i + 1], $arr[$right]) = array($arr[$right], $arr[$i + 1]); // 将基准值放到正确的位置
    return $i + 1;
}

Fungsi ini memilih elemen terakhir daripada tatasusunan sebagai nilai pangsi dan meletakkan semua elemen lebih kecil daripada nilai pangsi ke sebelah kiri tatasusunan dengan menukar elemen tatasusunan. Dalam proses ini, kami menggunakan pembolehubah $i untuk merekodkan subskrip subarray yang sedang diproses dan $j digunakan untuk melintasi keseluruhan tatasusunan. Apabila kita menemui elemen yang lebih kecil daripada nilai pangsi, kita mengalihkan $i satu kedudukan ke kanan dan meletakkan elemen itu pada kedudukan $i. Akhir sekali, kami meletakkan nilai asas pada kedudukan akhir $i + 1.

Dengan fungsi partition, kami kini boleh melaksanakan versi bukan rekursif algoritma quicksort. Dalam versi ini, kami menggunakan timbunan untuk menyimpan subarray untuk diproses. Apabila kami memproses subarray, kami mula-mula merekodkan sempadan kiri dan kanan subarray pada timbunan, dan kemudian terus membahagikannya kepada dua subarray yang lebih kecil sehingga semua subarray diisih.

function quick_sort(&$arr) {
    $stack = new SplStack(); // 使用SplStack实现栈
    $stack->push(count($arr) - 1); // 将整个数组的下标压入栈
    $stack->push(0);
    while (!$stack->isEmpty()) {
        $left = $stack->pop();
        $right = $stack->pop();
        $pivotIndex = partition($arr, $left, $right);
        if ($left < $pivotIndex - 1) {
            $stack->push($pivotIndex - 1);
            $stack->push($left);
        }
        if ($pivotIndex + 1 < $right) {
            $stack->push($right);
            $stack->push($pivotIndex + 1);
        }
    }
}

Dalam versi kod ini, kami menggunakan kelas SplStack untuk melaksanakan tindanan. Kami mula-mula menolak sempadan kiri dan kanan keseluruhan tatasusunan ke atas timbunan, kemudian secara berterusan mengeluarkan sempadan kiri dan kanan daripada timbunan dan menghantarnya ke fungsi partition untuk membahagikan subarray. Jika dibiarkan

Kerumitan masa algoritma ini ialah O(nlogn). Walaupun ia tidak sepantas versi rekursif quicksort dalam semua kes, ia boleh mengurangkan kerumitan ruang algoritma dengan ketara dan mengelakkan overhed panggilan fungsi rekursif. Jika anda perlu mengisih tatasusunan besar dengan cepat dalam PHP, algoritma ini mungkin sesuai dengan keperluan anda lebih baik daripada versi rekursif isihan pantas.

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma bukan rekursif jenis cepat dalam PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!