四种排序算法

一、冒泡排序

<?php 
header(" content-type:text/html;charset=utf-8");
    //冒泡排序
    set_time_limit(0);
    $arr = array(10,7,1,-1,-100,78,12345,90);
    //$arr = array(1,56,90,120,890,900);
    //$arr = range(1,1000);
    //做一个优化处理，如果数组已经是一个从小到大的顺序，我们就需要反复比较了

    function bubble(&$arr){

        $flag = 0;
        //先确定数组的大小
        $arr_size = count($arr);
        //确定大循环次数
        for($i = 0; $i < $arr_size - 1; $i++){
            //echo '<br>循环的次数' . ($i+1)'
            for($j = 0; $j < $arr_size - 1 - $i; $j++){
                //echo '<br>第’. ($i+1) . '大循环中的 小循环次数' . ($j+1)'
                //让前面的数和后面的数进行比较，如果前面的数比后面的数大，则交换数据
                if ($arr[$j] > $arr[$j + 1]){
                    //交换，定义一个中间变量
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $temp;
                    $flag = 1;
                }
            }
            if ($flag == 0){
                //如果$flag == 0,说明数组没有进行一次交换，则改该数组已经是一个从小到
                //大的顺序，因此结束排序
                break;
            }else{
                //如果$flag == 1,说明数组进行了一次交换，则该数组还不是一个从小到大
                //的排序，因此重新设置为0
                $flag = 0;
            }
        }
    }
    date_default_timezone_set('prc');
    echo '<br>' . date('H:i:s');
    bubble($arr);
    echo '<br>' . date('H:i:s');
    echo '<pre>';
    print_r($arr);

?>

二、选择排序

<?php 
header(" content-type:text/html;charset=utf-8");
    // 选择排序
    /*
        第一次从R[0]~R[N-1]中选取最小值，与R[0]交换，第二次从R[1]~R[N-1]
        选取最小值，与R[1],交换，第三次从R[2]~R[N-1]中选取最小值与R[2]交换
        以此类推
    */
    $arr = array(10,7,1,-1,-100,78,12345,90);
    function selectSort(&$arr){
        //获取数组大小
        $arr_size = count($arr);
        //大循环的次数
        for($i = 0; $i < $arr_size - 1; $i++){
            //假定$arr[$i] 就是最小值
            $min_val = $arr[$i];
            //把最小值下标记录
            $min_val_index = $i;

            //开始循环比较，找到真正的最小值，然后交换
            for($j = $i + 1; $j < $arr_size; $j++){
                //判断
                if($min_val > $arr[$j]){
                    //重新设置最小值和下标
                    $min_val = $arr[$j];
                    $min_val_index = $j;
                }
            }
            if($min_val_index != $i){
                //最好再交换
                $arr[$min_val_index] = $arr[$i];
                $arr[$i] = $min_val;
            }
        }
    }

    selectSort($arr);
    echo '<pre>';
    print_r($arr);
?>  

三、插入排序

<?php
header(" content-type:text/html;charset=utf-8");
    //插入排序
    $arr = array(10,7,1,-1,-100,78,12345,90);

    function insertSort(&$arr){
        //确定大循环的次数
        $arr_size = count($arr);

        //从$i =  1 这个数，加入到我们的有序数组
        for($i = 1; $i < $arr_size; $i++){

            //先把 $arr[$i],保存到$insertVal变量
            $insertVal = $arr[$i];
            //$index 是你的有序数组的最后的最后那一个元素的下标
            $index = $i - 1;
            while($index >= 0 && $arr[$index] > $insertVal){

                //将这个$index 对应的元素后移
                $arr[$index + 1] = $arr[$index];
                $index--;
            }

            //将我们的$insertVal 值，让到$index + 1 的位置即可
            $arr[$index + 1] = $insertVal;
        }
    }

    insertSort($arr);
    echo '<pre>';
    print_r($arr);
?>

四、快速排序

<?php
header(" content-type:text/html;charset=utf-8");
    //快速排序
    $arr = array(10,7,1,-1,-100,78,12345,90);

    function quickSort($left, $right, &$array){
             $l = $left;
             $r = $right;
             $pivot = $array[($left + $right) / 2];
             $temp = 0;

             while($l < $r){

                while($array[$l] < $pivot) $l++;
                while($array[$r] > $pivot) $r--;

                if($l >= $r) break;

                $temp = $array[$l];
                $array[$l] = $array[$r];
                $array[$r] = $temp;

                if($array[$l] == $pivot) --$r;
                if($array[$r] == $pivot) ++$l;
             }

             if($l == $r){

                 $l++;
                 $r--;
             }

             if($left < $r) quickSort($left, $r, $array);
             if($right < $r) quickSort($l, $right, $array);
    }

    quickSort(0, count($arr)-1, $arr);
    echo '<pre>';
    print_r($arr);
?>

四周排序速度对比 ： 快速 > 插入 > 选择 > 冒泡
以上代码来自韩顺平老师-------感谢他引领我入门

本作品采用《CC 协议》，转载必须注明作者和本文链接