What are the optimization strategies and implementation methods of the quick sort algorithm in PHP?

What are the optimization strategies and implementation methods of the quick sort algorithm in PHP?

Quick sort is a common sorting algorithm. Its basic idea is to select an element as the benchmark value and divide the array into two parts, one part is smaller than the benchmark value, and the other part is greater than the benchmark value. Then quickly sort the two parts separately until the entire array is sorted. When implementing quick sort, the performance of the algorithm can be improved through optimization strategies.

The following will introduce several optimization strategies and implementation methods, and provide specific PHP code examples.

1. Randomly select the benchmark value
   In quick sort, the selection of the benchmark value has a great impact on the performance of the algorithm. If the first or last element is selected as the reference value each time, then when the array itself is ordered or approximately ordered, the time complexity of the algorithm will reach O(n^2). To avoid this situation, we can randomly select an element as the base value, thereby reducing the probability of the worst case scenario.

Sample code:

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. Three-number method
   When selecting the benchmark value, avoiding selecting the minimum or maximum value of the array can improve the performance of the algorithm. A common method of taking the base value is to use the "three-number method", that is, select three elements from the beginning, middle, and end of the array, and then take the middle value as the base value.

Sample code:

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

By adopting optimization strategies such as randomly selecting the benchmark value and taking the middle of three numbers, the performance of the quick sort algorithm can be improved and the worst-case scenario can be reduced. Probability. These optimization strategies are particularly important to improve algorithm efficiency if applied to sorting large-scale data sets.

The above is the detailed content of What are the optimization strategies and implementation methods of the quick sort algorithm in PHP?. For more information, please follow other related articles on the PHP Chinese website!