您现在的位置是: 首页 >  技术分享 > 

重新解读常见的排序算法
叶子 2017-11-08 16:52:00

冒泡排序:最简单的一种算法,如果第一次接触程序的同学,就会有一些疑惑,为什么那么写。我举例子说明一下:就比如你有两个瓶子,分别是A瓶,B瓶,瓶子里都装满了水,你想把这AB两瓶水做一个交换,在生活中,你一定会找来第三个空瓶子C,把刚才A瓶的水,倒进那个空瓶子C,此时你就可以完成A瓶和B瓶的交换,这就是现实版的冒泡排序。

<?php
$order_array=array(5,4,3,6,7,1,2,10,8,9 );
function bubble_order($arr){
    $count_num=count($arr);
    for($k=1;$k<$count_num;$k++){
        for($i=0;$i<$count_num-$k;$i++){
            if($arr[$i]>$arr[$i+1]){
                $tem=$arr[$i];
                $arr[$i]=$arr[$i+1];
                $arr[$i+1]=$tem;
            }
        }
    }
    return $arr;
}
$new_order_arr=bubble_order($order_array);
echo '<pre>';
print_r($new_order_arr);

插入排序:对于少量元素的排序,它是一个有效的算法。插入排序的工作方式像许多人排序一手扑克牌。开始时,我们的左手为空并且桌子上的牌面向下。然后,我们每次从桌子上拿走一张牌并将它插入左手中正确的位置。为了找到一张牌的正确位置,我们从右到左将它与已在手中的每张牌进行比较。拿在左手上的牌总是排序好的,原来这些牌是桌子上牌中顶部的牌。

<?php
function insertSort($arr=array()){
    $num = count($arr);
    for($j=1;$j<$num;$j++) {
        $key = $arr[$j];
        $i = $j - 1;
        while ($i>=0 && $arr[$i]>$key) {
            $arr[$i+1] = $arr[$i];
            $i = $i - 1;
        }
        $arr[$i + 1] = $key;
    }
    return $arr;
}
$array = array(5,2,4,6,1,3);
$sort = insertSort($array);
var_dump($sort);

快速排序:采用的是分治法,大家上学的时候都出过早操吧,个子矮的在前面站着,个子高的站在后面,快排的原理就是找一位同学作为基准,比这位同学矮的站在左边,比这位同学高的站在右边,然后再用同样的方法递归排序划分那两拨,最后排好了再合并一下就可以了。

<?php
function quick_sort($arr){
    $length = count($arr);
    if($length <= 1) {
        return $arr;
    }
    $base_num = $arr[0];
    $left_array = array();
    $right_array = array();
    for($i=1; $i<$length; $i++) {
        if($base_num > $arr[$i]) {
            $left_array[] = $arr[$i];
        } else {
            $right_array[] = $arr[$i];
        }
    }
    $left_array = quick_sort($left_array);
    $right_array = quick_sort($right_array);
    //合并
    return array_merge($left_array, array($base_num), $right_array);;
}
$arr=array(2,1,0,3,9,10,59,41,78,56,45,47,12,15,45,11);
$rs=quick_sort($arr);
echo '<pre>';
print_R($rs);die;

上面说法纯属个人观点,如果大家还是不太理解,请参考相关资料查看。有任何错误的地方,请及时纠正,以免误导学习排序算法的同学。

yezismile wechat
欢迎关注博主公众号
分享:

Copyright © 2018
www.yezismile.com All rights reserved. 京ICP备15029736号-1