PHP实现排序算法(9种)

排序算法（sorting algorithm）用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用，因为有序数据通常能够被更高效地查找、分析和处理。

以下是 PHP 实现的九种经典排序算法，每种算法都包含详细注释和特点说明。

<?php

/**
 * 排序算法
 */
class AlgoSort
{
    
    /**
     * 1、选择排序
     * 特点：每次从未排序部分选择最小元素放到已排序部分末尾
     * 时间复杂度：O(n²) 无论最好最坏情况
     * 空间复杂度：O(1)
     * 稳定性：不稳定（相同元素可能改变相对位置）
     */
    public function selectionSort(array $arr): array {
        $n = count($arr);
        for ($i = 0; $i < $n - 1; $i++) {
            $minIndex = $i; // 假设当前元素是最小的
            
            // 在未排序部分查找真正的最小元素
            for ($j = $i + 1; $j < $n; $j++) {
                if ($arr[$j] < $arr[$minIndex]) {
                    $minIndex = $j;
                }
            }
            
            // 将最小元素与当前元素交换
            if ($minIndex != $i) {
                [$arr[$i], $arr[$minIndex]] = [$arr[$minIndex], $arr[$i]];
            }
        }
        return $arr;
    }

    /**
     * 2、冒泡排序
     * 特点：相邻元素两两比较，较大的元素逐步"冒泡"到数组末尾
     * 时间复杂度：O(n²) 最好情况O(n)（已排序时）
     * 空间复杂度：O(1)
     * 稳定性：稳定（相等元素不交换）
     */
    public function bubbleSort(array $arr): array {
        $n = count($arr);
        for ($i = 0; $i < $n - 1; $i++) {
            $swapped = false; // 优化：如果某一轮没有交换，说明已排序
            
            for ($j = 0; $j < $n - $i - 1; $j++) {
                if ($arr[$j] > $arr[$j + 1]) {
                    [$arr[$j], $arr[$j + 1]] = [$arr[$j + 1], $arr[$j]];
                    $swapped = true;
                }
            }
            
            if (!$swapped) break; // 提前退出
        }
        return $arr;
    }

    /**
     * 3、插入排序
     * 特点：将每个元素插入到已排序部分的适当位置
     * 时间复杂度：O(n²) 最好情况O(n)（已排序时）
     * 空间复杂度：O(1)
     * 稳定性：稳定
     */
    public function insertionSort(array $arr): array {
        $n = count($arr);
        for ($i = 1; $i < $n; $i++) {
            $key = $arr[$i]; // 当前要插入的元素
            $j = $i - 1;
            
            // 将比$key大的元素后移
            while ($j >= 0 && $arr[$j] > $key) {
                $arr[$j + 1] = $arr[$j];
                $j--;
            }
            
            $arr[$j + 1] = $key; // 插入到正确位置
        }
        return $arr;
    }

    /**
     * 4、快速排序
     * 特点：分治法，选择一个基准元素将数组分为两部分
     * 时间复杂度：平均O(n log n)，最坏O(n²)（当数组已排序时）
     * 空间复杂度：O(log n)（递归栈）
     * 稳定性：不稳定
     */
    public function quickSort(array $arr): array {
        if (count($arr) <= 1) {
            return $arr;
        }
        
        $pivot = $arr[0]; // 选择第一个元素作为基准
        $left = $right = [];
        
        // 分区操作
        for ($i = 1; $i < count($arr); $i++) {
            if ($arr[$i] < $pivot) {
                $left[] = $arr[$i];
            } else {
                $right[] = $arr[$i];
            }
        }
        
        // 递归排序并合并
        return array_merge($this->quickSort($left), [$pivot], $this->quickSort($right));
    }

    // 原地分区优化版
    public function quickSortInPlace(array &$arr, int $low = 0, int $high = null): void {
        if ($high === null) $high = count($arr) - 1;
        if ($low < $high) {
            $pi = $this->partition($arr, $low, $high);
            $this->quickSortInPlace($arr, $low, $pi - 1);
            $this->quickSortInPlace($arr, $pi + 1, $high);
        }
    }

    public function partition(array &$arr, int $low, int $high): int {
        $pivot = $arr[$high]; // 选择最后一个元素作为基准
        $i = $low - 1;
        
        for ($j = $low; $j < $high; $j++) {
            if ($arr[$j] < $pivot) {
                $i++;
                [$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
            }
        }
        
        [$arr[$i + 1], $arr[$high]] = [$arr[$high], $arr[$i + 1]];
        return $i + 1;
    }

    /**
     * 5、归并排序
     * 特点：分治法，将数组分成两半分别排序后合并
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(n)
     * 稳定性：稳定
     */
    public function mergeSort(array $arr): array {
        if (count($arr) <= 1) return $arr;
        
        $mid = (int)(count($arr) / 2);
        $left = array_slice($arr, 0, $mid);
        $right = array_slice($arr, $mid);
        
        return $this->merge($this->mergeSort($left), $this->mergeSort($right));
    }

    public function merge(array $left, array $right): array {
        $result = [];
        $i = $j = 0;
        
        while ($i < count($left) && $j < count($right)) {
            if ($left[$i] <= $right[$j]) {
                $result[] = $left[$i++];
            } else {
                $result[] = $right[$j++];
            }
        }
        
        // 合并剩余元素
        while ($i < count($left)) $result[] = $left[$i++];
        while ($j < count($right)) $result[] = $right[$j++];
        
        return $result;
    }

    /**
     * 6、堆排序
     * 特点：利用堆数据结构设计的排序算法
     * 时间复杂度：O(n log n)
     * 空间复杂度：O(1)
     * 稳定性：不稳定
     */
    public function heapSort(array &$arr): void {
        $n = count($arr);
        
        // 构建最大堆
        for ($i = (int)($n / 2) - 1; $i >= 0; $i--) {
            $this->heapify($arr, $n, $i);
        }
        
        // 逐个提取元素
        for ($i = $n - 1; $i > 0; $i--) {
            [$arr[0], $arr[$i]] = [$arr[$i], $arr[0]]; // 将当前最大元素移到末尾
            $this->heapify($arr, $i, 0); // 重新堆化剩余元素
        }
    }

    public function heapify(array &$arr, int $n, int $i): void {
        $largest = $i;
        $left = 2 * $i + 1;
        $right = 2 * $i + 2;
        
        // 找出左子节点或右子节点中较大的
        if ($left < $n && $arr[$left] > $arr[$largest]) $largest = $left;
        if ($right < $n && $arr[$right] > $arr[$largest]) $largest = $right;
        
        // 如果需要交换，继续堆化
        if ($largest != $i) {
            [$arr[$i], $arr[$largest]] = [$arr[$largest], $arr[$i]];
            $this->heapify($arr, $n, $largest);
        }
    }

    /**
     * 7、桶排序
     * 特点：将元素分布到有限数量的桶中，每个桶再单独排序
     * 时间复杂度：平均O(n + k)，最坏O(n²)
     * 空间复杂度：O(n + k)
     * 稳定性：稳定（取决于内部排序算法）
     */
    public function bucketSort(array $arr, int $bucketSize = 5): array {
        if (count($arr) === 0) return $arr;
        
        $min = min($arr);
        $max = max($arr);
        $bucketCount = floor(($max - $min) / $bucketSize) + 1;
        $buckets = array_fill(0, $bucketCount, []);
        
        // 将元素分配到桶中
        foreach ($arr as $num) {
            $index = floor(($num - $min) / $bucketSize);
            $buckets[$index][] = $num;
        }
        
        $sorted = [];
        foreach ($buckets as $bucket) {
            if (!empty($bucket)) {
                sort($bucket); // 可以使用其他排序算法
                $sorted = array_merge($sorted, $bucket);
            }
        }
        
        return $sorted;
    }

    /**
     * 8、计数排序
     * 特点：非比较排序，适用于整数小范围数据
     * 时间复杂度：O(n + k)（k是数据范围）
     * 空间复杂度：O(k)
     * 稳定性：稳定
     */
    public function countingSort(array $arr): array {
        if (count($arr) <= 1) return $arr;
        
        $max = max($arr);
        $count = array_fill(0, $max + 1, 0);
        
        // 统计每个元素出现次数
        foreach ($arr as $num) {
            $count[$num]++;
        }
        
        // 计算累计次数
        for ($i = 1; $i <= $max; $i++) {
            $count[$i] += $count[$i - 1];
        }
        
        $output = array_fill(0, count($arr), 0);
        
        // 反向填充保持稳定性
        for ($i = count($arr) - 1; $i >= 0; $i--) {
            $output[$count[$arr[$i]] - 1] = $arr[$i];
            $count[$arr[$i]]--;
        }
        
        return $output;
    }

    /**
     * 9、基数排序
     * 特点：按位数进行排序，从最低位到最高位依次排序
     * 时间复杂度：O(n * k)（k是最大数字的位数）
     * 空间复杂度：O(n + k)
     * 稳定性：稳定
     */
    public function radixSort(array $arr): array {
        if (count($arr) <= 1) return $arr;
        
        $max = max($arr);
        $maxDigits = strlen((string)$max);
        
        for ($digit = 0; $digit < $maxDigits; $digit++) {
            $buckets = array_fill(0, 10, []);
            
            foreach ($arr as $num) {
                $digitVal = floor($num / pow(10, $digit)) % 10;
                $buckets[$digitVal][] = $num;
            }
            
            $arr = [];
            for ($i = 0; $i < 10; $i++) {
                $arr = array_merge($arr, $buckets[$i]);
            }
        }
        
        return $arr;
    }
}

总结对比表

实际应用中，快速排序和归并排序是最常用的通用排序算法，而特定场景下（如整数排序）可以考虑计数排序或基数排序等非比较排序算法。