算法-排序

冒泡排序

对数组按照从小到大进行排序，从前往后对相邻的两个数依次进行比较和调整，让较大的往后移动，每轮将最大的数移动到最后。

function blbble_sort($arr) {
    $count = count($arr);
    if($count == 0) {
        return false;
    }
    
    for($i = 0; $i < $count; $i++) {
        // 循环控制每轮，将该轮最大的数字移动到最后
        for($j = 0; $j < $count - $i; $j++) {
            if($arr[$j] > $arr[$j + 1]) {
                $temp = $arr[$j];
                $arr[$j] = $arr[$j + 1];
                $arr[$j + 1] = $temp;
            }
        }
    }
    return $arr;
}

选择排序

在数组中，选出最小的一个数与第一个位置的数交换，然后再在剩下的数中找出最小的数与第二个位置的数进行交换，如此循环到倒数第二个数与最后一个数比较为止。

public function selectSort($arr)
{
    $len = count($arr);
    // 双层循环，外层控制轮数，内层控制比较次数
    for ($i = 0; $i < $len-1; $i++) {
        // 先假设最小值的位置
        $p = $i;

        for ($j = $i + 1; $j < $len; $j++) {
            // $arr[$p]是当前已知的最小值
            // 比较，发现更小的，记录下最小值的位置；并且在下次比较的时候采用已知的最小值进行比较
            if ($arr[$p] > $arr[$j]) {
                $p = $j;
            }
        }

        // 最小值的位置为$p，如果发现最小值的位置和当前假设的位置$i不同，则位置互换即可
        if ($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }

    return $arr;
}

插入排序

在需要排序的数组中，假设前面的数已经是排序好的，现在要把第n个数插入到前面的有序数组中，使得这n个数也是排序好的。如此反复循环，直到全部排好顺序。

public function insertSort($arr)
{
    $len = count($arr);
    for ($i = 1; $i < $len; $i++) {
        // 要插入的元素
        $tmp = $arr[$i];

        // 内层是在外层之前的数组
        for ($j = $i - 1; $j >= 0; $j--) {
            // 发现插入的元素要小，交换位置，将后边的元素与前面的元素互换
            if ($tmp < $arr[$j]) {
                $arr[$j + 1] = $arr[$j];
                $arr[$j] = $tmp;
            } else {
                // 如果碰到不需要移动的元素，由于是已经排序好是数组，则前面的就不需要再次比较了,跳出内层循环
                break;
            }
        }
    }

    return $arr;
}

快速排序

选择一个基准元素，通过一趟扫描，将数组分成两部分，一部分比基准元素小，一部分大于等于基准元素，此时基准元素在其排好序后的中间位置，然后再用同样的方法递归地排序划分的两部分。

function quick_sort(array $list) {
    $len = count($list);
    if($len <= 1) {
        return $list;
    }
    // 选择第一个元素作为基准元素
    $pivotValue = $list[0];
    $left = array();
    $right = array();
    // 遍历除了基准元素以外的所有元素，按照大小关系放入两个数组中
    for ($i = 1; $i < $lenght; $i++) {
        if ($list[$i] < $pivotValue) {
            $left[] = $list[$i];
        } else {
            $right[] = $list[$i];
        }
    }
    // 再分别对左边和右边的数组进行相同的排序处理
    $left = quick_sort($left);
    $right = quick_sort($right);
    return array_merge($left, array($pivotValue), $right);
}