PHP四种排序算法实现及效率分析【冒泡排序,插入

1. 冒泡排序

1.1 算法原理

冒泡排序是一种简单的排序算法。它重复地遍历要排序的数组，依次比较相邻的两个元素，如果它们的顺序错误，则交换位置。这样，每一趟都会将最大（或最小）的元素"浮"到数组的末端，直到整个数组都排好序为止。

以下是冒泡排序的算法步骤：

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+1];
                arr[$j+1] = arr[$j];
                arr[$j] = $temp;
            }
        }
    }
    return arr;
}

1.2 时间复杂度分析

冒泡排序的时间复杂度为O(n^2)。它的主要耗时在于嵌套的两个循环，外层循环需要n-1次，内层循环需要n-i-1次。因此，总共需要进行的比较次数为(n-1) + (n-2) + ... + 1，这是一个等差数列，根据等差数列的求和公式可得总比较次数为(n-1)n/2，即O(n^2)。

2. 插入排序

2.1 算法原理

插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

以下是插入排序的算法步骤：

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

2.2 时间复杂度分析

插入排序的时间复杂度也是O(n^2)。它的外层循环需要n-1次，内层循环的平均次数约为n/2。因此，总共需要进行的比较次数为(n-1)n/2，即O(n^2)。虽然插入排序的时间复杂度与冒泡排序相同，但在实际使用中，插入排序的性能通常要优于冒泡排序。

3.

... （文章继续）