PHP写的排序算法

2016-08-13 06:07:11 PHP 2248 0

排序算法

下面的是通过PHP实现经典算法，并计算了耗时
可以通过耗时对比这几种算法的复杂度

插入排序、冒泡排序、选择排序、并归排序、快速排序

代码如下

$arr = [];

for ($i = 0; $i < 5000; $i++) {
    $arr[] = rand(1, 10000);
}

1 插入排序

function insertionSort($arr)
{

    for ($i = 1; $i < count($arr); $i++) {
        $tmp = $arr[$i]; //设置监视哨
        $key = $i - 1; //设置开始查找的位置
        while ($key >= 0 && $tmp < $arr[$key]) { // 监视哨的值比查找的值小 并且 没有到此次查询的第一个
            $arr[$key + 1] = $arr[$key];  //数组的值进行后移
            $key--;  //要查找的位置后移
        }
        if (($key + 1) != $i) //放置监视哨
            $arr[$key + 1] = $tmp;
    }
    return $arr;

}

$insertion_start_time = microtime(true);

$insertion_sort = insertionSort($arr);

$insertion_end_time = microtime(true);

$insertion_need_time = $insertion_end_time - $insertion_start_time;

print_r("插入排序耗时:" . $insertion_need_time);

2 冒泡排序

function bubbleSort($arr)
{

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

            }
        }
    }
    return $arr;
}

$bubble_start_time = microtime(true);

$bubble_sort = bubbleSort($arr);

$bubble_end_time = microtime(true);

$bubble_need_time = $bubble_end_time - $bubble_start_time;

print_r("冒泡排序耗时:" . $bubble_need_time);

3 选择排序

function selectionSort($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;
                //赋值新的最小的
            }
        }
        /*swap$array[$i]and$array[$min]即将当前内循环的最小元素放在$i位置上*/
        if ($min != $i) {
            $temp = $arr[$min];
            $arr[$min] = $arr[$i];
            $arr[$i] = $temp;
        }
    }
    return $arr;

}

$selection_start_time = microtime(true);

$selection_sort = selectionSort($arr);

$selection_end_time = microtime(true);

$selection_need_time = $selection_end_time - $selection_start_time;

print_r("选择排序耗时:" . $selection_need_time);

4 并归排序

//merge函数将指定的两个有序数组(arr1arr2,)合并并且排序
//我们可以找到第三个数组,然后依次从两个数组的开始取数据哪个数据小就先取哪个的,然后删除掉刚刚取过///的数据
function al_merge($arrA, $arrB)
{
    $arrC = array();
    while (count($arrA) && count($arrB)) {
        //这里不断的判断哪个值小,就将小的值给到arrC,但是到最后肯定要剩下几个值,
        //不是剩下arrA里面的就是剩下arrB里面的而且这几个有序的值,肯定比arrC里面所有的值都大所以使用
        $arrC[] = $arrA['0'] < $arrB['0'] ? array_shift($arrA) : array_shift($arrB);
    }
    return array_merge($arrC, $arrA, $arrB);
}

//归并排序主程序
function al_merge_sort($arr)
{
    $len = count($arr);
    if ($len <= 1)
        return $arr;//递归结束条件,到达这步的时候,数组就只剩下一个元素了,也就是分离了数组
    $mid = intval($len / 2);//取数组中间
    $left_arr = array_slice($arr, 0, $mid);//拆分数组0-mid这部分给左边left_arr
    $right_arr = array_slice($arr, $mid);//拆分数组mid-末尾这部分给右边right_arr
    $left_arr = al_merge_sort($left_arr);//左边拆分完后开始递归合并往上走
    $right_arr = al_merge_sort($right_arr);//右边拆分完毕开始递归往上走
    $arr = al_merge($left_arr, $right_arr);//合并两个数组,继续递归
    return $arr;
}

$merge_start_time = microtime(true);

$merge_sort = al_merge_sort($arr);

$merge_end_time = microtime(true);

$merge_need_time = $merge_end_time - $merge_start_time;

print_r("并归排序耗时:" . $merge_need_time);

5 快速排序

function quickSort(&$arr)
{
    $_size = count($arr);
    if ($_size == 0) {
        return [];
    }
    // 每次都以第一个作为基准值
    $k = $arr[0];
    $x = array();
    $y = array();
    // 去掉基准数据，剩下的归并
    for ($i = 1; $i < $_size; $i++) {
        // 比它小的放左边
        // 比它大的放右边
        if ($arr[$i] <= $k) {
            $x[] = $arr[$i];
        } else {
            $y[] = $arr[$i];
        }
    }
    $x = quickSort($x);
    $y = quickSort($y);
    // 递归合并结果
    return array_merge($x, array($k), $y);
}

$quick_start_time = microtime(true);
$quick_sort = al_merge_sort($arr);
$quick_end_time = microtime(true);
$quick_need_time = $quick_end_time - $quick_start_time;
print_r("快速排序耗时:" . $quick_need_time);