Bagaimana untuk melaksanakan algoritma urutan terbalik menggunakan PHP

Cara melaksanakan algoritma urutan terbalik dalam PHP

Dalam sains komputer, urutan terbalik adalah dalam urutan Untuk mana-mana dua elemen ai dan aj, jika i < j dan ai > . Menyelesaikan masalah susunan terbalik adalah kepentingan praktikal yang besar dan mempunyai aplikasi dalam bidang seperti pengoptimuman masalah pengisihan dan analisis data.

Dalam artikel ini, kami akan memperkenalkan cara menggunakan bahasa pengaturcaraan PHP untuk melaksanakan algoritma pasangan terbalik untuk lebih memahami dan menguasai masalah biasa ini.

Pertama, kita perlu memikirkan cara mengira pasangan tertib terbalik. Pendekatan mudah ialah menggunakan dua gelung bersarang, membandingkan semua pasangan elemen setiap kali. Jika syarat ai > aj dipenuhi, maka tambahkan pembilang pasangan tertib terbalik. Walau bagaimanapun, kerumitan masa kaedah ini adalah O(n^2) dan tidak sesuai untuk set data yang besar.

Satu lagi kaedah yang lebih cekap ialah menggunakan algoritma isihan gabungan. Idea asas algoritma ini adalah untuk menguraikan urutan ke dalam urutan yang lebih kecil dan kemudian menggabungkannya ke dalam urutan disusun yang lebih besar. Semasa proses penggabungan, kita boleh mengira bilangan pasangan dalam susunan terbalik dengan mudah.

Berikut ialah contoh kod kami untuk melaksanakan algoritma pasangan tertib terbalik menggunakan bahasa pengaturcaraan PHP:

function mergeSortCount(&$arr) {
    $temp = array();
    $count = 0;
    $length = count($arr);
    $temp = array_fill(0, $length, 0); // 创建一个临时数组用于存储合并过程中的结果

    $count = mergeSort($arr, $temp, 0, $length - 1); // 调用真正的归并排序函数

    return $count;
}

function mergeSort(&$arr, &$temp, $left, $right) {
    $count = 0;
    if ($left < $right) {
        $mid = floor(($left + $right) / 2); // 找到中间位置
        $count += mergeSort($arr, $temp, $left, $mid); // 递归地对左子数组进行排序
        $count += mergeSort($arr, $temp, $mid + 1, $right); // 递归地对右子数组进行排序
        $count += merge($arr, $temp, $left, $mid + 1, $right); // 合并左右子数组，并计算逆序对数量
    }
    return $count;
}

function merge(&$arr, &$temp, $left, $mid, $right) {
    $count = 0;
    $i = $left; // 左子数组起始位置
    $j = $mid; // 右子数组起始位置
    $k = $left; // 合并后的数组起始位置

    while ($i <= $mid - 1 && $j <= $right) {
        if ($arr[$i] <= $arr[$j]) {
            $temp[$k++] = $arr[$i++];
        } else {
            $temp[$k++] = $arr[$j++];
            $count += $mid - $i;
        }
    }

    while ($i <= $mid - 1) {
        $temp[$k++] = $arr[$i++];
    }

    while ($j <= $right) {
        $temp[$k++] = $arr[$j++];
    }

    for ($i = $left; $i <= $right; $i++) {
        $arr[$i] = $temp[$i];
    }

    return $count;
}

// 测试示例
$arr = array(3, 1, 2, 4, 5);
$count = mergeSortCount($arr);
echo "逆序对的数量：" . $count;

Kod di atas mula-mula mentakrifkan fungsi mergeSortCount, yang menerima tatasusunan sebagai parameter dan mengembalikan bilangan pasangan tertib terbalik . Dalam fungsi ini, kami mencipta tatasusunan sementara temp, memulakan pembilang count dan merekodkan panjang tatasusunan panjang. mergeSortCount函数，该函数接受一个数组作为参数，并返回逆序对的数量。在这个函数中，我们创建了一个临时数组temp，并初始化一个计数器count，以及记录数组长度length。

接下来，我们调用mergeSort函数进行实际的归并排序。mergeSort函数接受一个左闭区间$left和一个右闭区间$right作为参数，在每次递归调用中，它将分割数组并递归地对子数组进行排序，然后调用merge函数来合并子数组并计算逆序对的数量。

在merge函数中，我们使用三个指针$i、$j和$k，对左、右子数组和合并后的数组进行遍历。如果左子数组的当前元素小于或等于右子数组的当前元素，则将左子数组的当前元素放入临时数组中，并将$i和$k指针向后移动一位。如果右子数组的当前元素小于左子数组的当前元素，则将右子数组的当前元素放入临时数组中，并将$j和$k指针向后移动一位。在这个过程中，如果出现右子数组的当前元素小于左子数组的当前元素，则计数器$count加上左子数组当前位置到中间位置的元素个数（因为左子数组已经有序）。

最后，我们将临时数组$temp中的元素复制回原始数组$arr，然后返回计数器$count。

在最后的测试示例中，我们定义了一个包含5个整数的数组，并调用mergeSortCount

Seterusnya, kami memanggil fungsi mergeSort untuk melaksanakan isihan gabungan sebenar. Fungsi mergeSort menerima selang tertutup kiri $left dan selang tertutup kanan $right sebagai parameter Dalam setiap panggilan rekursif, ia akan memisahkan tatasusunan dan mengisih subarray secara rekursif, kemudian panggil fungsi merge untuk menggabungkan subarray dan mengira bilangan pasangan terbalik.

Dalam fungsi merge, kami menggunakan tiga penunjuk $i, $j dan $k, untuk The subarray kiri dan kanan dan tatasusunan yang digabungkan dilalui. Jika elemen semasa subarray kiri kurang daripada atau sama dengan elemen semasa subarray kanan, letakkan elemen semasa subarray kiri ke dalam tatasusunan sementara dan tambahkan $i dan $ k code>Penunjuk bergerak ke belakang satu kedudukan. Jika elemen semasa subarray kanan lebih kecil daripada elemen semasa subarray kiri, letakkan elemen semasa subarray kanan ke dalam tatasusunan sementara dan tambahkan <code>$j dan $k kod> Penunjuk bergerak ke belakang satu kedudukan. Dalam proses ini, jika elemen semasa subarray kanan lebih kecil daripada elemen semasa subarray kiri, pembilang <code>$count ditambah kepada bilangan elemen dari kedudukan semasa subarray kiri ke kedudukan tengah (kerana subarray kiri Tatasusunan sudah diisih). 🎜🎜Akhir sekali, kami menyalin elemen dalam tatasusunan sementara $temp kembali ke tatasusunan asal $arr, dan kemudian mengembalikan pembilang $count . 🎜🎜Dalam contoh ujian terakhir, kami menentukan tatasusunan yang mengandungi 5 integer dan memanggil fungsi mergeSortCount untuk mengira bilangan pasangan tertib terbalik. Dalam contoh ini, bilangan pasangan terbalik ialah 2. 🎜🎜Melalui contoh kod di atas, kita dapat melihat bahawa tidak sukar untuk melaksanakan algoritma pasangan terbalik menggunakan bahasa pengaturcaraan PHP. Idea teras algoritma isihan gabungan adalah untuk menguraikan jujukan kepada urutan yang lebih kecil, melaksanakan pengisihan melalui operasi penggabungan, dan mengira bilangan pasangan tertib terbalik pada masa yang sama. Ini adalah algoritma pengisihan yang cekap dan biasa digunakan yang boleh digunakan untuk pelbagai masalah praktikal. 🎜

Atas ialah kandungan terperinci Bagaimana untuk melaksanakan algoritma urutan terbalik menggunakan PHP. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!