排序算法和查找算法

示例：分別用冒泡排序，快速排序，選擇排序，插入排序將數組中的值從小到大的順序排序

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

1、冒泡排序算法

//思路:兩兩比較待排序數據元素的大小，發現兩個數據元素的次序相反即進行交換，直到沒有反序的數據元素為止
function bubbleSort($array){
        $lg = count($array);
        if($lg <=1){
            return $array;
        }
        //該層循環控制 需要冒泡的輪數
        for($i=0;$i<$lg;$i++){
            //該層循環用來控制每輪 冒出一個數 需要比較的次數
            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、選擇排序算法

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

3、插入排序算法

//思路:在要排序的一組數中，假設前面的數已經是排好順序的，現在要把第n個數插到前面的有序數中，使得這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) {
    //先判斷是否需要繼續進行
    $length = count($array);
    if($length <= 1) {
        return $array;
    }
    //選擇第一個元素作為基準
    $base_num = $array[0];
    //遍歷除了標尺外的所有元素，按照大小關系放入兩個數組內
    //初始化兩個數組
    $left_array = array();  //小于基準的
    $right_array = array();  //大于基準的
    for($i=1; $i<$length; $i++) {
        if($base_num > $array[$i]) {
            //放入左邊數組
            $left_array[] = $array[$i];
        } else {
            //放入右邊
            $right_array[] = $array[$i];
        }
    }
    //再分別對左邊和右邊的數組進行相同的排序處理方式遞歸調用這個函數
    $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;
}