一些简单的排序法(已烂大街)

冒泡排序,快速排序,选择排序,二分法查找,快速查找

/**

  • 冒泡排序
  • 相邻2数比较,小的在前,大的在后
  • 数组有几个元素,就要比较几轮 $i
  • 每轮需要比较的次数为,数组元素个数-已比较的次数 $j
  • @param array $array 要操作的数组
  • @return array $array 返回的数组
    */

function bubbleSort($array)
{

    $cnt = count($array);
    for($i = 0; $i < $cnt ; $i++){
            for($j = 0 ; $j < ($cnt-$i-1) ; $j++){
                    if($array[$j] > $array[$j+1]){
                            $temp = $array[$j];
                            $array[$j] = $array[$j+1];
                            $array[$j+1] = $temp;
                    }
            }
    }
    return $array;

}

/**

  • 快速排序
  • 递归实现
  • 获取数组第一个数,循环使后面的数与其比较,
  • 比其小的放在一个数组中,比其大的放在一个数组中
  • 将2个数组递归调用,直到最终数组元素小于等于1时,没有可以比较的元素
  • 通过array_merge函数,将比较的数组按大小顺序合并然后一层一层的return出去,最终实现从小到大排序
  • @param array $array 要操作的数组
  • @return array $array 返回的数组
    */

function quickSort($array)
{

    if(count($array) <= 1 ) return $array;
    $key = $array[0];
    $left_arr = array();
    $right_arr = array();
    for ($i=1;$i<count($array);$i++){
            if($array[$i] <= $key){
                    $left_arr[] = $array[$i];
            }else{
                    $right_arr[] = $array[$i];
            }
    }

    $left_arr = quickSort($left_arr);
    $right_arr = quickSort($right_arr);
    return array_merge($left_arr,array($key),$right_arr);

}

/**

  • 选择排序
  • 2层循环
  • 第一层逐个获取数组的值 $array[$i]
  • 第二次遍历整个数组与$array[$i]比较($j=$i+1已经比较的,不再比较,减少比较次数)
  • 如果比$array[$i]小,就交换位置
  • 这样一轮下来就可以得到数组中最小值
  • 以此内推整个外层循环下来就数组从小到大排序了
  • @param array $array 要比较的数组
  • @return array $array 从小到大排序后的数组
    */

function selectSort($array){

    $cnt = count($array);
    for($i=0;$i<$cnt;$i++){
            for($j=($i+1);$j<$cnt;$j++){
                    if($array[$i]>$array[$j]){
                            $tmp = $array[$i];
                            $array[$i] = $array[$j];
                            $array[$j] = $tmp;
                    }
            }
    }
    return $array;

}

/**

  • 二分法查找一个值在数组中的位置
  • @param array $array 操作的数组
  • @param void $val 要查找的值
  • @return int $mid 返回要查找的值在数组中的索引,如果不存在返回-1
    */

function binarySearch($array,$val)
{

    $cnt = count($array);
    $low = 0;
    $high = $cnt - 1;
    while ($low <= $high){
            $mid = intval(($low + $high)/2);
            if($array[$mid] == $val){
                    return $mid;
            }

            if($array[$mid] < $val){
                    $low = $mid + 1;
            }

            if($array[$mid] > $val){
                    $high = $mid - 1;
            }
    }

    return -1;

}

/**

  • 顺序查找(最简单,效率低下)
  • 通过循环数组查找要的值
  • @param array $array 要操作的数组
  • @param void $val 要查找的值
  • @return int 如果存在,返回该值在数组中的索引,否则返回-1
    */

function seqSch($array,$val)
{

    for($i=0;$i<count($array);$i++){
            if($array[$i] == $val)
                    break;
    }

    if($i < count($array)){
            return $i;
    }else{
            return -1;
    }

}

标签: 算法

评论已关闭