PHP实现四种基本排序算法

冒泡排序

思路分析：

• 给一个N个元素的数组，要求从小到大排序，从底部向上把较大的数值逐步向上，这样根据1次遍历后，最大的元素会被升向最顶部，然后根据这种方式，循环N-1次直至所有气泡大小有序。
• 核心思路：内层循环两两比较，较大的向后推

function bubbleSort(array $arr)
{
    $count = count($arr);
    for ($i=1; $i < $count; $i++) {
        for ($j=0; $j < $count-$i; $j++) {
            if($arr[$j] > $arr[$j+1]){
                // $tmp = $arr[$j];
                // $arr[$j] = $arr[$j+1];
                // $arr[$j+1] = $tmp;
                list($arr[$j], $arr[$j+1]) = [$arr[$j+1], $arr[$j]];
            }
        }
    }
    return $arr;
}

快速排序

思路分析：

• 找任意一个元素作为基准参数，小于基准参数的放在left中，大于基准参数的放在right中，得到left和right数组，然后递归调用此函数

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

插入排序

思路分析：

• 每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
• 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
• 插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素， 但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。
• 在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

function insertSort(array $arr)
{
    $count = count($arr);
    for ($i = 1; $i < $count; $i++){
        $temp = $arr[$i];
        $j    = $i - 1;

        while ($arr[$j] > $temp){
            $arr[$j+1] = $arr[$j];
            $arr[$j]   = $temp;
            $j--;
            if ($j < 0) break;
        }
    }
    return $arr;
}

选择排序

思路分析：

• 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
• 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

function selectSort(array $arr)
{
    $count = count($arr);
    for ($i = 0; $i < $count; $i++){
        $k = $i;
        for ($j = $i + 1; $j < $count; $j++){
            if($arr[$j] < $arr[$k]){
                $k = $j;
            }
        }
        if($k != $i){
            $temp    = $arr[$i];
            $arr[$i] = $arr[$k];
            $arr[$k] = $temp;
        }
    }
    return $arr;
}