How to implement quick sort non-recursive algorithm in PHP

Introduction

Quick sort is an efficient sorting algorithm that implements sorting by continuously dividing an array into two sub-arrays. In the quick sort algorithm, a pivot value is selected and all elements smaller than the pivot value are placed on its left side, while all elements greater than the pivot value are placed on its right side. This process is then applied recursively to the left and right subarrays until the entire array is sorted.

Quick sort is a recursive function because it needs to decompose the original problem into two smaller sub-problems, and then solve the original problem by solving these sub-problems recursively. While this approach can work effectively in some situations, it has some limitations. Specifically, when processing large arrays, recursive algorithms may exhaust the computer's stack space, causing a stack overflow exception. In addition, the additional overhead of recursive function calls may also cause performance degradation of the algorithm.

Therefore, in some cases, it may be more appropriate to use non-recursive implementation methods. In this article, we will introduce a non-recursive algorithm for quick sort using PHP.

Algorithm implementation

We first define an auxiliary function partition, which is used to divide an array into two sub-arrays: one containing all elements smaller than the baseline value, and one containing all elements greater than the baseline value.

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;
}

This function selects the last element from the array as the pivot value and puts all elements smaller than the pivot value to the left side of the array by swapping the array elements. In this process, we use the variable $i to record the subscript of the currently processed subarray, and $j is used to traverse the entire array. When we find an element that is smaller than the pivot value, we move $i one position to the right and place the element at $i's position. Finally, we place the base value at the final position $i 1 .

With the partition function, we can now implement a non-recursive version of the quicksort algorithm. In this version, we use a stack to store the subarrays to be processed. When we process a subarray, we first record the left and right boundaries of the subarray on the stack, and then continue to divide it into two smaller subarrays until all subarrays are sorted.

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);
        }
    }
}

In this version of the code, we use the SplStack class to implement the stack. We first push the left and right boundaries of the entire array onto the stack, then continuously remove the left and right boundaries from the stack and pass them to the partition function to divide the subarray. If left < pivotIndex - 1, it means that the left subarray is not yet sorted and is pushed onto the stack to wait for processing. Similarly, if pivotIndex 1 < right, it means that the right subarray is not yet sorted and is pushed onto the stack for processing.

The time complexity of this algorithm is O(nlogn). Although it is not as fast as the recursive version of quicksort in all cases, it can significantly reduce the space complexity of the algorithm and avoid the overhead of recursive function calls. If you need to quickly sort a large array in PHP, this algorithm may suit your needs better than the recursive version of quicksort.

The above is the detailed content of How to implement quick sort non-recursive algorithm in PHP. For more information, please follow other related articles on the PHP Chinese website!