越努力,越幸运

php排序算法

 1 year ago

Notice:先为大家介绍三种排序算法,后面会不定期的新增算法。

一. 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法(比如序列[5, 5, 3]第一次就将第一个[5]与[3]交换,导致第一个5挪动到第二个5后面)。--来自百度百科


简单的说: 每一次从数组中选择一个值A,然后从剩下待排序中选取值B,如果B<A,那么交换位置。继续比较第二个的位置,重复比较到数据排序完毕。

function SelectSort($array){
    $count = count($array);

    for($i = 0; $i < $count; $i++) {
        $k = $i;
        for($j = $i + 1; $j < $count; $j++) {
            if($array[$j] < $array[$k]) {
                $k = $j;
            }
        }
        if($k != $i) {
            list($array[$i], $array[$k]) = array($array[$k], $array[$i]);
        }
    }
    return $array;
}
var_dump(SelectSort([5,1,65,17,25,2,28,25,246,367]));

二. 冒泡排序

它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。--来自百度百科


简单的说: 冒泡是三种排序算法中比较慢的,原理是比较相邻的元素,如果第一个比第二个大,则进行交换。就是大的放到后面,直到排序完成。

function BubbleSort($array){
    $count = count($array);
    for($i = 0; $i <= $count; $i++) {
        for($j = 0; $j < $count - 1; $j++) {
            if($array[$j] > $array[$j+1]) {
                list($array[$j], $array[$j+1]) = array($array[$j+1], $array[$j]);
            }
        }
    }
    return $array;
}
var_dump(BubbleSort([5,1,65,17,25,2,28,25,246,367]));

三. 快速排序

快速排序(Quick Sort)是一种有效的排序算法。虽然算法在最坏的情况下运行时间为O(n^2),但由于平均运行时间为O(nlogn),并且在内存使用、程序实现复杂性上表现优秀,尤其是对快速排序算法进行随机化的可能,使得快速排序在一般情况下是最实用的排序方法之一。快速排序被认为是当前最优秀的内部排序方法。--来自搜狗百科


简单的说: 通过递归,将小的放一边,大的放一边最后合并变成有序序列。

通过图片来详细看整个过程:
Notice: "[数字]"是$array[0]的值,"[]"是返回空数组,黄色框中是返回的结果

图片名称

function QuickSort($array) {
    $count = count($array);
    if($count <= 1) {
        return $array;
    }

    $left = $right = [];
    foreach($array as $k => $v) {
        if($k == 0) {
            continue;
        }
        if($array[$k] < $array[0]) {
            $left[] = $v;
        } else {
            $right[] = $v;
        }
    }

    $left = QuickSort($left);
    $right = QuickSort($right);

    return array_merge($left, [$array[0]], $right);
}
var_dump(QuickSort([5,1,65,17,25,2,28,25,246,367]));

谢谢观看,希望能帮到大家!另外转载请备注来源!