冒泡排序

将数组中的相邻元素的比较和交换来把小的数交换到最前面

//冒泡排序
function maopao($num)
{
    for ($i = 0; $i < count($num); $i++) {
        for ($j = 0; $j < count($num) - $i - 1; $j++) {
            if ($num[$j] > $num[$j + 1]) {
                list($num[$j],$num[$j+1]) = [$num[$j+1],$num[$j]];
                //$tmp = $num[$j + 1];
                //$num[$j + 1] = $num[$j];
                //$num[$j] = $tmp;
            }
        }
    }
    return $num;
}

选择排序

先找出最小的一个数。放到最前面.

选择排序的思想其实和冒泡排序有点类似,都是在一次排序后把最小的元素放到最前面。但是过程不同,冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子,对5,3,8,6,4这个无序序列进行简单选择排序,首先要选择5以外的最小数来和5交换,也就是选择3和5交换,一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换,最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化,因为其目的相同,只是选择排序只有在确定了最小数的前提下才进行交换,大大减少了交换的次数。选择排序的时间复杂度为O(n^2)

function check_array($arr)
{
    $count = count($arr);
    for ($i = 0; $i < $count; $i++) {
        $min = $i;
        for ($j = $i + 1; $j < $count; $j++) {
            if ($arr[$min] > $arr[$j]) {
                $min = $j;
            }
        }
        if ($min != $i) {
            list($arr[$min], $arr[$i]) = [$arr[$i],$arr[$min]];
            //$tem = $arr[$min];
            //$arr[$min] = $arr[$i];
            //$arr[$i] = $tem;
        }
    }
    return $arr;
}

插入排序

插入排序类似玩儿扑克牌时候的理牌,将拿到的牌插入到正确的位置中去

function insertSort($arr)
{
    $count = count($arr);
    for ($i = 1; $i < $count; $i++) {
        $key = $i-1;
        $val = $arr[$i];
        while ($val >= 0 && $arr[$key] > $val) {
            $arr[$key + 1] = $arr[$key];
            $key--;
        }
        $arr[$key + 1] = $val;
    }

    return $arr;
}

快速排序

快速排序是比较和交换小数和大数,这样一来不仅把小数冒泡到上面同时也把大数沉到下面。选择一个数,将小于这个数的数放入左边数组、大于这个数的放入右边数组。

//简易排序排序、不是正确的快速排序!!
function qsort($arr)
{
    $count = count($arr);
    //这一步不能少!!!!
    if($count <= 1)
    {
        return $arr;
    }
    $midlle = $arr[0];
    $left = $right = [];
    for ($i = 1; $i < $count; $i++) {
        ($arr[$i] < $midlle) ? $left[] = $arr[$i] : $right[] = $arr[$i];
    }
    $left = qsort($left);
    $right = qsort($right);

    return array_merge($left, [$midlle], $right);
}

快速排序:

通过数组引用改变数组内元素值、返回原数组

function swap(array &$arr,$a,$b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
function Partition(array &$arr,$low,$high){
    $pivot = $arr[$low];   //选取子数组第一个元素作为枢轴
    while($low < $high){  //从数组的两端交替向中间扫描
        while($low < $high && $arr[$high] >= $pivot){
            $high --;
        }
        swap($arr,$low,$high);    //终于遇到一个比$pivot小的数,将其放到数组低端
        while($low < $high && $arr[$low] <= $pivot){
            $low ++;
        }
        swap($arr,$low,$high);    //终于遇到一个比$pivot大的数,将其放到数组高端
    }
    return $low;   //返回high也行,毕竟最后low和high都是停留在pivot下标处
}

function QSort(array &$arr,$low,$high){
    if($low < $high){
        $pivot = Partition($arr,$low,$high);  //将$arr[$low...$high]一分为二,算出枢轴值
        QSort($arr,$low,$pivot - 1);   //对低子表进行递归排序
        QSort($arr,$pivot + 1,$high);  //对高子表进行递归排序
    }
}

//快速排序入口
function QuickSort(array &$arr){
    $low = 0;
    $high = count($arr) - 1;
    QSort($arr,$low,$high);
}

参考资料

https://blog.csdn.net/baidu_30000217/article/details/53311840

https://github.com/francistao/LearningNotes/blob/master/Part3/Algorithm/Sort/%E9%9D%A2%E8%AF%95%E4%B8%AD%E7%9A%84%2010%20%E5%A4%A7%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E6%80%BB%E7%BB%93.md

标签: PHP

添加新评论