叶子Blog

重新解读常见的排序算法

冒泡排序：最简单的一种算法，如果第一次接触程序的同学，就会有一些疑惑，为什么那么写。我举例子说明一下：就比如你有两个瓶子，分别是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;

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