php常见的五种排序算法

愉快的周未过到了，新的一周工作让我们从饭米粒开始吧。
算法是很多phper容易忽略和薄弱的环节，本文用php实现常见的五种排序算法，希望能够加深对排序算法的理解。

1.插入排序

以数组第二个数字为基准 假定该数组之前的数字都是排好序的，相互比较大小，比该数字小的放该基准数字的前面，依次往后移动,直到数组尾部，整个数组排序完毕.插入排序是稳定算法。

   function charu($arr) {
    $count = count($arr);    for ($i = 1; $i < $count; $i++) {        #以数组第一个数字为基准
        $temp = $arr[$i];        #控制循环并进行交换
        for ($j = $i - 1; $j >= 0; $j--) {            if ($temp < $arr[$j]) {                $arr[$j + 1] = $arr[$j];                $arr[$j] = $temp;
            } else {                break;
            }
        }
    }    return $arr;
}

2.选择排序

默认以第一个数字为基准数字，每次以基准数字从待排数字中找出最小（大）的数字，顺序放在已经排好数据列的最后，选择排序是不稳定的。

function xuanze($arr) {
    $count = count($arr);    for ($i = 0; $i < $count - 1; $i++) {        $min = $i;        for ($j = $i + 1; $j < $count; $j++) {            if ($arr[$min] > $arr[$j]) {                $min = $j;
            }
        }        if ($i != $min) {            $temp = 0;            $temp = $arr[$min];            $arr[$min] = $arr[$i];            $arr[$i] = $temp;
        }
    }    return $arr;
}

3.冒泡排序

相邻的两个数字进行比较 找出最小的放在前面 大数放后面 依次比较。冒泡算法是稳定算法。

function maopao($arr) {
    $count = count($arr);    for ($i = 0; $i < $count - 1; $i++) {        for ($j = $i + 1; $j < $count; $j++) {            if ($arr[$i] > $arr[$j]) {                $temp = 0;                $temp = $arr[$j];                $arr[$j] = $arr[$i];                $arr[$i] = $temp;
            }
        }
    }    return $arr;
}

4.快速排序

以数组的第一个数字为基准点 以这个基准数字为参考点 比该数字大的放右边 比该数字小的放左边 然后在根据切分出来的数组进行递归 到只剩一元素时停止递归.快速排序是不稳定算法。

function kuaisu($arr) {
    $count = count($arr);    if ($count <= 1) {        return $arr;
    }    $temp = $arr[0];    $left = $right = [];    for ($i = 1; $i < $count; $i++) {        if ($temp > $arr[$i]) {            $left[] = $arr[$i];
        } else {            $right[] = $arr[$i];
        }
    }    $left = kuaisu($left);    $right = kuaisu($right);    return array_merge($left, array($temp), $right);
}

5.木桶排序

首先产生两个数字，最大值和最小值，然后根据两个数字的值决定要创建多少个桶装数据，每个 桶装数据按key编好号码，按数组内的数字指定桶的出现次数。然后输出所有指定桶。木桶算法是不稳定算法。

function mutong($arr) {
    $min = min($arr);    $max = max($arr);    $count = count($arr);    $buffer = array_fill($min, $max - $min + 1, 0);    for ($i = 0; $i < $count - 1; $i++) {        $buffer[$arr[$i]] ++;
    }    //根据统计桶内的次数输出桶内的数字
    for ($i = $min; $i < $max + 1; $i++) {        for ($j = 0; $j < $buffer[$i]; $j++) {            $result[] = $i;
        }
    }    return $result;
}

tips:关于稳定排序和不稳定排序: 

比如在一个数组中,有[1,3,5,10,5]，第一个5我们称作r5,第二个5我们称作j5.在经过排序后，r5还是在j5之前的，我们称作稳定算法，反之称作不稳定算法。

最后贴出算法时间复杂度和空间复杂图的图片:

---------------伟大的分割线----------------

PHP饭米粒(phpfamily) 由一群靠谱的人建立，愿为PHPer带来一些值得细细品味的精神食粮！

本文由 范强 向php饭米粒(phpfamily) 投稿，转载请注明本来源信息和以下的二维码（长按可识别二维码关注）：