排序算法和查找算法

示例：分别用冒泡排序，快速排序，选择排序，插入排序将数组中的值从小到大的顺序排序

$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;
}