Apakah strategi pengoptimuman dan kaedah pelaksanaan algoritma isihan pantas dalam PHP?

Apakah strategi pengoptimuman dan kaedah pelaksanaan algoritma isihan pantas dalam PHP?

Isih cepat ialah algoritma pengisihan biasa. Idea asasnya ialah memilih elemen sebagai nilai penanda aras dan membahagikan tatasusunan kepada dua bahagian, satu bahagian lebih kecil daripada nilai penanda aras, dan bahagian lain lebih besar daripada nilai penanda aras. Kemudian cepat susun dua bahagian secara berasingan sehingga keseluruhan tatasusunan diisih. Apabila melaksanakan isihan pantas, prestasi algoritma boleh dipertingkatkan melalui strategi pengoptimuman.

Beberapa strategi pengoptimuman dan kaedah pelaksanaan akan diperkenalkan di bawah, dan contoh kod PHP khusus akan disediakan.

1. Pilih nilai penanda aras secara rawak
   Secara ringkas, pemilihan nilai penanda aras mempunyai kesan yang besar terhadap prestasi algoritma. Jika elemen pertama atau terakhir dipilih sebagai nilai rujukan setiap kali, maka apabila tatasusunan itu sendiri dipesan atau lebih kurang dipesan, kerumitan masa algoritma akan mencapai O(n^2). Untuk mengelakkan situasi ini, kita boleh memilih unsur secara rawak sebagai nilai asas, dengan itu mengurangkan kebarangkalian senario kes terburuk.

Kod sampel:

function partition($arr, $low, $high) {
    $pivot_index = rand($low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

2. Kaedah mencari tengah tiga nombor
   Apabila memilih nilai penanda aras, mengelak daripada memilih nilai minimum atau maksimum tatasusunan boleh meningkatkan prestasi algoritma. Kaedah biasa untuk mengambil nilai asas ialah menggunakan "kaedah tiga nombor", iaitu, pilih tiga elemen dari permulaan, tengah dan akhir tatasusunan, dan kemudian ambil nilai tengah sebagai nilai asas.

Contoh kod:

function getPivotIndex($arr, $low, $high) {
    $mid = intval(($low + $high) / 2);
    
    if ($arr[$low] < $arr[$mid]) {
        if ($arr[$mid] < $arr[$high]) {
            return $mid;
        } else if ($arr[$high] < $arr[$low]) {
            return $low;
        } else {
            return $high;
        }
    } else {
        if ($arr[$low] < $arr[$high]) {
            return $low;
        } else if ($arr[$mid] < $arr[$high]) {
            return $high;
        } else {
            return $mid;
        }
    }
}

function partition($arr, $low, $high) {
    $pivot_index = getPivotIndex($arr, $low, $high);
    // 交换基准值到数组最后一个位置
    $arr[$pivot_index] = $arr[$high];
    $arr[$high] = $arr[$pivot_index];
    
    $pivot = $arr[$high];
    $i = $low - 1;
    
    for ($j = $low; $j < $high; $j++) {
        if ($arr[$j] < $pivot) {
            $i++;
            // 交换元素位置
            $temp = $arr[$i];
            $arr[$i] = $arr[$j];
            $arr[$j] = $temp;
        }
    }
    
    // 将基准值交换回正确的位置
    $temp = $arr[$i + 1];
    $arr[$i + 1] = $arr[$high];
    $arr[$high] = $temp;
    
    return $i + 1;
}

function quickSort($arr, $low, $high) {
    if ($low < $high) {
        $pivot_index = partition($arr, $low, $high);
        quickSort($arr, $low, $pivot_index - 1);
        quickSort($arr, $pivot_index + 1, $high);
    }
}

$arr = [5, 9, 3, 1, 6, 4, 8, 2, 7];
quickSort($arr, 0, count($arr) - 1);
echo implode(", ", $arr);  // 输出：1, 2, 3, 4, 5, 6, 7, 8, 9

Dengan menggunakan strategi pengoptimuman seperti memilih nilai penanda aras secara rawak dan mengambil pertengahan tiga nombor, prestasi algoritma isihan pantas boleh dipertingkatkan dan kebarangkalian senario kes terburuk dapat dikurangkan. Strategi pengoptimuman ini amat penting untuk meningkatkan kecekapan algoritma jika digunakan untuk menyusun set data berskala besar.

Atas ialah kandungan terperinci Apakah strategi pengoptimuman dan kaedah pelaksanaan algoritma isihan pantas dalam PHP?. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!