: jank    :   : 5109    : 2016-09-21 18:45  数据结构和算法

一、排序算法

1.冒泡排序

    原理：冒泡排序的思路大致为，用两层for循环。

    里层的循环：原理是第一个数和第二个数进行对比，如果大于第二个数，则互换位置，然后第二个数再和第三个数对比，以此类推。

    外层的循环：原理是里层这个循环所走的遍数，总遍数为数组的长度。

例：

<?php
    $arr = array(3,1,4,5,6,9,2,20,14,33,28,22);
    $n = count($arr);
    for($i=1; $i<$n; $i++){
        for($j=0; $j<$n-1; $j++){
            $min = $arr[$j];
            if($arr[$j] > $arr[$j+1]){
                $arr[$j] = $arr[$j+1];
                $arr[$j+1] = $min;
        }
    }
    echo '第' . $i . '次循环:  ';
    print_r( $arr);
    echo '<br/>';
    }

输出结果如下所示：

2.快速排序

原理：先对一个数组进行分半处理并保存在一个空数组中，然后再对分半后的数组进行递归调用这个函数。当这个函数所传的参数数组个数小于等于1则递归结束，并返回结果。

例：

<?php
    $arr = array(5,3,23,34,12,1,2,6,11);    
    function quick_sort($arr){
        $n = count($arr);
        if($n <= 1) return $arr;//判断是否结束
        $arr_left = array();
        $arr_right = array();
        for($i=1; $i<$n; $i++){
            if($arr[0] > $arr[$i]){//把数组分半
                $arr_left[] = $arr[$i];
            }else{
                $arr_right[] = $arr[$i];
            }
        }
        $arr_left = quick_sort($arr_left);//递归调用函数并保存结果
        $arr_right = quick_sort($arr_right);
        return array_merge($arr_left, array($arr[0]), $arr_right);
    }
    print_r(quick_sort($arr));

输出结果如下所示：

Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 5 [4] => 6 [5] => 11 [6] => 12 [7] => 23 [8] => 34 )

3.选择排序

   原理：选择排序利用两个for循环，里边的循环即利用数组的第一个数值同整个数组中的值进行挨个比较，每一次比较就判断数值的大小，并把较小值的键赋给$min,最后把取得的最小值赋给$arr[0]，,外边的循环则是里边的循环执行的次数（数组的长度），以此类推，得到$arr[1],$arr[2]...$arr[n]。

例：

<?php
   header('content-type: text/html; charset=utf8');
    $arr = array(4,21,65,14,3,2,6,8,19,11,23,32,12);
    function selectsort($arr){
        $n = count($arr);
        if($n <= 1) return $arr;
        for($i=0; $i<$n; $i++){
            $min = $i;    //设置$min=0,同时也是数组第一个键
            for($j=$i+1; $j<$n; $j++){
                if($arr[$j]<$arr[$min]){
                    $min = $j;
                }
            }
            if($min != $i){
                $tmp = $arr[$i];  
               $arr[$i] = $arr[$min];  
             $arr[$min] = $tmp;  
            }
            echo '第';
            echo $i+1 . '次： ';//运算符前不能拼接字符串
            print_r($arr);
            echo '<br/>';
        }
        return $arr;
    }
    print_r(selectsort($arr));

输出结果：

4.插入排序

原理：使用两层for循环，里面的循环在数组中先插入一个数$arr[0]，对比前面一个数,如果小于它则互换位置，里面的循环次数等于外循环的层数。以此类推得到最终的结果。

例：

<?php
    header('content-type: text/html; charset=utf8');
    $arr = array(4,12,1,2,5,28,42,39,11,9);
    function insertsort($arr){
        $n = count($arr);
        if($n <= 1) return $arr;
        for($i=1; $i<$n; $i++){
            $a = $arr[$i];
            for($j=$i-1; $j>=0; $j--){
                if($a < $arr[$j]){
                    $arr[$j+1] = $arr[$j];
                    $arr[$j] = $a;
                }else{
                    break;
                }
            }
            echo '第'.$i.'次: ';
            print_r($arr);
            echo '<br/>';
        }
        return $arr;
    }
    print_r(insertsort($arr));

输出结果：