排序算法和查找算法

示例：分別用冒泡排序，快速排序，選擇排序，插入排序?qū)?shù)組中的值從小到大的順序排序

$array = (9,5,1,3,6,4,8,7,2);

1、冒泡排序算法

//思路:兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反即進(jìn)行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止
function bubbleSort($array){
        $lg = count($array);
        if($lg <=1){
            return $array;
        }
        //該層循環(huán)控制 需要冒泡的輪數(shù)
        for($i=0;$i<$lg;$i++){
            //該層循環(huán)用來控制每輪 冒出一個數(shù) 需要比較的次數(shù)
            for($j=1;$j<$lg-$i;$j++){
                if($array[$j-1]>$array[$j]){
                    $_tmp = $array[$j-1];
                    $array[$j-1] = $array[$j];
                    $array[$j] = $_tmp;
                }
            }
        }
        return $array;
    }

2、選擇排序算法

//思路:在要排序的一組數(shù)中，選出最小的一個數(shù)與第一個位置的數(shù)交換。然后在剩下的數(shù)當(dāng)中再找最小的與第二個位置的數(shù)交換，如此循環(huán)到倒數(shù)第二個數(shù)和最后一個數(shù)比較為止
function selectSort($array){
        $lg = count($array);
        if($lg <=1){
            return $array;
        }
        //雙重循環(huán)完成，外層控制輪數(shù)，內(nèi)層控制比較次數(shù)
        for($i=0;$i<$lg;$i++){
            $min = $i;//先假設(shè)最小的值的位置
            for($j=$i+1;$j<$lg;$j++){
                //$array[$min] 是當(dāng)前已知的最小值
                if($array[$j] < $array[$min]){
                    $min = $j;//比較，發(fā)現(xiàn)更小的,記錄下最小值的位置；并且在下次比較時采用已知的最小值進(jìn)行比較
                }
            }
            //已經(jīng)確定了當(dāng)前的最小值的位置，保存到$p中。如果發(fā)現(xiàn)最小值的位置與當(dāng)前假設(shè)的位置$i不同，則位置互換即可
            if($i !=$min){
                $_tmp = $array[$i];
                $array[$i] = $array[$min];
                $array[$min] = $_tmp;
            }
        }
        return $array;
    }

3、插入排序算法

//思路:在要排序的一組數(shù)中，假設(shè)前面的數(shù)已經(jīng)是排好順序的，現(xiàn)在要把第n個數(shù)插到前面的有序數(shù)中，使得這n個數(shù)也是排好順序的。如此反復(fù)循環(huán)，直到全部排好順序。
function insertSort($array){
        $lg = count($array);
        if($lg <=1 ){
            return $array;
        }
        for($i=1;$i<$lg;$i++){
            $x=$array[$i];
            $j=$i-1;
            while(($j>=0) && ($array[$j]>$x)){
                $array[$j+1] = $array[$j];
                $j--;
            }
            if($array[$j+1] !=$x){
                $array[$j+1] = $x;
            }
        }
        return $array;
    }

4、快速排序算法

function quickSort($array) {
    //先判斷是否需要繼續(xù)進(jìn)行
    $length = count($array);
    if($length <= 1) {
        return $array;
    }
    //選擇第一個元素作為基準(zhǔn)
    $base_num = $array[0];
    //遍歷除了標(biāo)尺外的所有元素，按照大小關(guān)系放入兩個數(shù)組內(nèi)
    //初始化兩個數(shù)組
    $left_array = array();  //小于基準(zhǔn)的
    $right_array = array();  //大于基準(zhǔn)的
    for($i=1; $i<$length; $i++) {
        if($base_num > $array[$i]) {
            //放入左邊數(shù)組
            $left_array[] = $array[$i];
        } else {
            //放入右邊
            $right_array[] = $array[$i];
        }
    }
    //再分別對左邊和右邊的數(shù)組進(jìn)行相同的排序處理方式遞歸調(diào)用這個函數(shù)
    $left_array = quickSort($left_array);
    $right_array = quickSort($right_array);
    //合并
    return array_merge($left_array, array($base_num), $right_array);
}

5、二分查找算法

function binarySearch($arr,$key){
       $low = 0;
       $high = 9;
       while($low<=$high){
            $mid = intval(($low+$high)/2);
            if($key == $arr[$mid]){
                return $mid+1;
            }elseif($key<$arr[$mid]){
                $high = $mid-1;
            }elseif($key>$arr[$mid]){
                $low = $mid+1;
            }
        }
        return -1;
  }

6、順序查找算法

function SqSearch($arr,$value){
    $length = count($arr);
    for($i=0;$i<$length;$i++){
      if($value == $arr[$i]){
          return $i+1;
       }
      }
    return -1;
}