php实现排序算法

PHP实现冒泡排序

冒泡排序通过重复遍历数组，比较相邻元素并交换位置实现排序。时间复杂度为O(n²)，适合小规模数据排序。

function bubbleSort($array) {
    $length = count($array);
    for ($i = 0; $i < $length - 1; $i++) {
        for ($j = 0; $j < $length - $i - 1; $j++) {
            if ($array[$j] > $array[$j + 1]) {
                $temp = $array[$j];
                $array[$j] = $array[$j + 1];
                $array[$j + 1] = $temp;
            }
        }
    }
    return $array;
}

PHP实现快速排序

快速排序采用分治策略，选取基准值将数组分为两部分递归排序。平均时间复杂度为O(n log n)。

function quickSort($array) {
    if (count($array) <= 1) {
        return $array;
    }
    $pivot = $array[0];
    $left = $right = [];
    for ($i = 1; $i < count($array); $i++) {
        if ($array[$i] < $pivot) {
            $left[] = $array[$i];
        } else {
            $right[] = $array[$i];
        }
    }
    return array_merge(quickSort($left), [$pivot], quickSort($right));
}

PHP实现选择排序

选择排序每次遍历找到最小元素放到已排序序列末尾。时间复杂度始终为O(n²)。

function selectionSort($array) {
    $length = count($array);
    for ($i = 0; $i < $length - 1; $i++) {
        $minIndex = $i;
        for ($j = $i + 1; $j < $length; $j++) {
            if ($array[$j] < $array[$minIndex]) {
                $minIndex = $j;
            }
        }
        if ($minIndex != $i) {
            $temp = $array[$i];
            $array[$i] = $array[$minIndex];
            $array[$minIndex] = $temp;
        }
    }
    return $array;
}

PHP实现插入排序

插入排序将未排序元素逐个插入到已排序部分的正确位置。最坏时间复杂度O(n²)，适合近乎有序的数据。

function insertionSort($array) {
    $length = count($array);
    for ($i = 1; $i < $length; $i++) {
        $key = $array[$i];
        $j = $i - 1;
        while ($j >= 0 && $array[$j] > $key) {
            $array[$j + 1] = $array[$j];
            $j--;
        }
        $array[$j + 1] = $key;
    }
    return $array;
}

PHP实现归并排序

归并排序采用分治法，将数组分成两半分别排序后合并。时间复杂度稳定为O(n log n)，但需要额外空间。

function mergeSort($array) {
    if (count($array) <= 1) {
        return $array;
    }
    $mid = (int)(count($array) / 2);
    $left = array_slice($array, 0, $mid);
    $right = array_slice($array, $mid);
    return merge(mergeSort($left), mergeSort($right));
}

function merge($left, $right) {
    $result = [];
    while (count($left) > 0 && count($right) > 0) {
        if ($left[0] <= $right[0]) {
            $result[] = array_shift($left);
        } else {
            $result[] = array_shift($right);
        }
    }
    return array_merge($result, $left, $right);
}

PHP内置排序函数

PHP提供多种内置排序函数，针对不同场景优化：

• sort(): 对数组升序排序
• rsort(): 对数组降序排序
• asort(): 保持索引关联的升序排序
• ksort(): 按键名对数组升序排序
• usort(): 使用用户自定义比较函数排序

$numbers = [3, 1, 4, 1, 5, 9, 2, 6];
sort($numbers);  // 升序排序
rsort($numbers); // 降序排序