实现常见的排序算法

admin

在工作中我们经常使用MySQL的order by方法对数据进行排序，但是还是有很多开发场景无法通过MySQL排序获取数据，需要我们自己动手开发，今天我们就针对四个常见的排序算法进行讲解一下。
1. 冒泡排序
3 q& C" X3 N, s这个应该是大家最为熟悉的排序了，实现也比较简单。我们通过两两相比，每循环一轮就获得这一轮中最大或最小的值。

复制代码
<?php

//冒泡排序，降序
function maopaoSort(array $data)
{
    $len = count($data);
    for ($i=0;$i<$len;$i++){
        for ($j=0;$j<$len-$i-1;$j++){
            if($data[$j]<$data[$j+1]){
                $tem = $data[$j];
                $data[$j] = $data[$j+1];
                $data[$j+1] = $tem;
            }
        }
    }
    return $data;
}

print_r(maopaoSort([0,435,123,54323,54621,543,321,56,231,54,455,977]));

注意：第二层的循环中 $j 最大值是 数组的长度 - 1 - 以循环的次数($i)
2. 选择排序
0 U8 H% t- S# {! X选择一个值作为对比对象，再用其他值与对比对象进行比较，然后根据对比结果调换位置，循环一遍数据后就可以得到想要的结果了。

复制代码
<?php

//选择排序，降序
function selectSort(array $data)
{
    $len = count($data);
    for ($i=0;$i<$len;$i++){
        $selectVal = $data[$i];
        $selectKey = $i;
        for ($j=$i+1;$j<$len;$j++){
            //如果想要升序，只需要把【<】改为【>】即可
            if($selectVal>$data[$j]){
                $selectVal = $data[$j];
                $selectKey = $j;
            }
        }
        $tem = $data[$i];
        $data[$i] = $selectVal;
        $data[$selectKey] = $tem;
    }
    return $data;
}

print_r(selectSort([0,435,123,54323,54621,543,321,56,231,54,455,977]));

3. 快速排序
3 j! \* Z  b- L+ n选择一个比较值，将数组的值跟选择的值进行比较，将数组拆分成左右两组数据。

复制代码
<?php

//快速排序，降序
function fastSort(array $data)
{
    $len = count($data);
    //如果数组中只有一个元素，直接返回
    if($len<=1) return $data;
    //选择一个元素作为比较对象
    $base = $data[0];
    $leftData = array();
    $rightData = array();
    for ($i=1;$i<$len;$i++){
        //降序时左边的存储比较大的值，如果想要升序，左边的数组存储比较小的值
        if($base<$data[$i]){
            $leftData[] = $data[$i];
        }else{
            $rightData[] = $data[$i];
        }
    }
    //使用递归再次处理左右两边的数组
    $leftData = fastSort($leftData);
    $rightData = fastSort($rightData);
    //注意顺序，一定是$leftData为第一个参数,$rightData为第三个参数
    return array_merge($leftData,[$base],$rightData);
}

4. 插入排序
其工作原理：首先我们假设前面的数据都是已经排好的数据，现在我们把第N个数据插入到有序里。

复制代码
<?php

//插入排序，降序
function insertSort(array $data)
{
    $len = count($data);
    for ($i=1;$i<$len;$i++){
        $tmp = $data[$i];
        for ($j=$i-1; $j>0; $j--){
            //如果想要升序，只需要把【<】改为【>】即可
            if($data[$j]<$tmp){
                $data[$j+1] = $data[$j];
                $data[$j] = $tmp;
            }
        }
    }
    return $data;
}

除了上述的这四种排序外还有希尔排序、堆排序以及归并排序。这几种排序相对较为复杂，有兴趣的可以自己去实现一下。