PHP实现常见排序算法的示例代码

1. 冒泡排序

1.1 算法描述

冒泡排序是一种简单的排序算法。它重复地遍历要排序的序列，一次比较两个元素，如果它们的顺序错误就交换位置，直到没有任何一对元素需要交换为止。

算法描述：

比较相邻的两个元素，如果前一个元素大于后一个元素，则交换位置。

对每一对相邻元素进行比较和交换，直到最后一对元素。

针对所有的元素重复以上步骤，除了最后一个。

重复步骤1~3，直到排序完成。

1.2 示例代码

function bubbleSort($arr) {
    $len = count($arr);
    for ($i = 0; $i < $len - 1; $i++) { 
        for ($j = 0; $j < $len - 1 - $i; $j++) { 
            if ($arr[$j] > $arr[$j + 1]) { 
                $temp = $arr[$j]; 
                $arr[$j] = $arr[$j + 1]; 
                $arr[$j + 1] = $temp; 
            } 
        } 
    } 
    return $arr;
}
$arr = [5, 3, 8, 4, 2];
$result = bubbleSort($arr);
print_r($result);

1.3 算法分析

冒泡排序是一种时间复杂度为O(n^2)的排序算法。在最坏的情况下，数组完全逆序时，需要进行n(n-1)/2次比较和交换。冒泡排序是一种稳定排序算法，即相同元素的相对位置在排序前后不会发生变化。

2. 插入排序

2.1 算法描述

插入排序的基本思想是将一个记录插入到已经排好序的有序表中，插入排序将待排序的数组分为两部分，一部分为已经排好序的有序表，另一部分为待插入的元素。在已排序的表中，从后往前扫描，找到位置后插入。

2.2 示例代码

function insertionSort($arr) {
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        $key = $arr[$i];
        $j = $i - 1;
        while ($j >= 0 && $arr[$j] > $key) {
            $arr[$j + 1] = $arr[$j];
            $j--;
        }
        $arr[$j + 1] = $key;
    }
    return $arr;
}
$arr = [5, 3, 8, 4, 2];
$result = insertionSort($arr);
print_r($result);

2.3 算法分析

插入排序的时间复杂度为O(n^2)。插入排序是一种稳定排序算法，相同元素的相对位置在排序前后不会发生变化。插入排序的最好情况是已经有序，时间复杂度为O(n)，最坏情况是逆序，时间复杂度为O(n^2)。

总结：

冒泡排序和插入排序是两种常见的排序算法，它们的原理和实现方法不同，适用于不同的场景。冒泡排序通过相邻元素的比较和交换来进行排序，时间复杂度为O(n^2)；插入排序通过将元素插入到已经排好序的有序表中，时间复杂度也为O(n^2)。两种算法都是稳定排序算法，相同元素的相对位置不会发生变化。

在实际应用中，根据具体问题的规模和性能需求选择合适的排序算法非常重要。如果待排序的数组已经接近有序，插入排序的效率更高。如果待排序的数组规模较大，可以考虑使用其他时间复杂度更低的排序算法，如快速排序、归并排序等。