选择排序&冒泡排序

选择排序和冒泡排序时间复杂度都属于 O(n^2)级别的排序算法，由于它实现起来比较简单，在不考虑性能的简单情景下，可以优先考虑。

1.选择排序原理图

选择排序的原理就是每循环一次就挑出最小的那个（假设从小到大排），然后记住最小位置的那个索引，把它安排到最前面去，已经排过的位置就往后排，以此类推达到选择排序的目的：

2.选择排序代码

<?php
/**
 * 从小到大选择排序
 * @param array $arr
 * @return array
 */
function selectionSort(array $arr):array
{
    for ($i=0;$i < count($arr) - 1;$i++){
        $minIndex = $i;
        $min = $arr[$i];
        for ($j = $i;$j < count($arr);$j++){
            if($arr[$j] < $min){
                $minIndex = $j;
                $min = $arr[$j];
            }
        }
        if($minIndex != $i){
            $tpm = $arr[$minIndex];
            $arr[$minIndex] = $arr[$i];
            $arr[$i] = $tpm;
        }
    }

    return $arr;
}

$arr = [1,16,5,8,4,6,2,9,6,4,10,11,5,7,3,6,12];

print_r(selectionSort($arr));
/**
 * [1,2,3,4,4,5,5,6,6,6,7,8,9,10,11,12,16]
 */

演示输出如下图所示：

Tips:时间复杂度是 O(n^2) 级别的。

3.冒泡排序原理图

冒泡排序的原理就是每次循环过程中，直接比较当前位置和下一个位置的值比较，若当前位置值比下一个位置值大则交换位置（假设从小到大排序，向右冒泡），这样经过 n-1 次（n是元素个数）操作之后，就可以像冒泡一样达到排序的效果。

4.冒泡排序代码

<?php
/**
 * 冒泡排序从小到大
 * @param array $arr
 * @return array
 */
function bubblingSort(array $arr): array
{
    for($i=0;$i < count($arr) - 1;$i++){
        for ($j = 0;$j < count($arr) - 2 - $i;$j++){
            if($arr[$j] > $arr[$j+1]){
                $tmp = $arr[$j];
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $tmp;
            }
        }
    }
    return $arr;
}

$arr = [1,16,5,8,4,6,2,9,6,4,10,11,5,7,3,6,12];

print_r(bubblingSort($arr));
/**
 * [1,2,3,4,4,5,5,6,6,6,7,8,9,10,11,12,16]
 */

演示输出如下图：

Tips:时间复杂度是 O(n^2) 级别的。

代码仓库 ：https://gitee.com/love-for-poetry/data-structure

扫码关注爱因诗贤