美文网首页
算法(冒泡、选择、插入、快速)

算法(冒泡、选择、插入、快速)

作者: liamu | 来源:发表于2017-03-15 17:48 被阅读13次

$arr = array(1,43,54,62,21,66,32,78,36,76,39);

冒泡排序

function getBubble($arr){
    $array_length = count($arr);//先判断数组的长度
    if($array_length <= 0){
        return $arr;
    }
    for($i=0;$i<$array_length;$i++){
        for($j=0;$j<$array_length-$i-1;$j++){
            if($arr[$j]>$arr[$j+1]){
                $tmp = $arr[$j+1];
                $arr[$j+1] = $arr[$j];
                $arr[$i] = $tmp;
            }
        }
    }
    return $arr;
}

选择排序

function selectSort($arr){
    $array_length = count($arr);
    if($array_length <= 0){
        return $arr;
    }
    for($i=0;$i<$array_length;$i++){
        $p = $i;
        for($j=0;$j<$array_length;$j++){
            if($arr[$p]>$arr[$j]){
                $p = $j;
            }
        }
        if($p != $i){
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    return $arr;
}

插入排序法

输入一个元素,检查数组列表中的每个元素,将其插入到一个已经排好序的数列中的适当位置,使数列依然有序,当最后一个元素放入合适位置时,该数组排序完毕。

  • 代码规律分析:
  • 第一次大循环:$[1]与$[0]比;
  • 第二次大循环:$[2]与$[1]比,$[1]与$[0]比;
  • 第三次大循环:$[3]与$[2]比,$[2]与$[1]比,$[1]与$[0]比
function insertSort($arr){
    $array_length = count($arr);
    if($array_length <=1){return $arr;}
    for($i=0;$i<$array_length;$i++){
        for($j=$i;$j>0;$j--){
            if($arr[$j]> $arr[$j+1]){
                $tmp = $arr[$j+1];
                $arr[$j+1] = $arr[$j];
                $arr[$j] = $tmp;
            }
        }
    }
    return $arr;
}
function getInsert($arr){
    $arr_length = count($arr);
    if ($arr_length <= 1) {
        return $arr;
    }
    // =======================================
    // 先默认第一个下标为0的数是排好的数
    for ($i=1; $i < $arr_length; $i++) { 
        //确定插入比较的数
        $insertVal = $arr[$i];
        //确定与前面比较的数比较
        $insertIndex = $i - 1;
        while ($insertIndex >=0 && $insertVal < $arr[$insertIndex]) {
            //把数后移
            $arr[$insertIndex + 1] = $arr[$insertIndex];
            $insertIndex--;
        }
        $arr[$insertIndex+1] = $insertVal;
    }

    // =======================================
    //先默认第一个下标为0的数是排好的数
    // for ($i=1; $i < $arr_length; $i++) { 

    //  $tmp = $arr[$i];//获取当前需要比较的元素值

    //  //内层循环控制  比较  并  插入
    //  for ($j=$i-1; $j >= 0; $j--) { 
    //      if ($tmp < $arr[$j]) {
    //          $arr[$j+1] = $arr[$j];
    //          $arr[$j] = $tmp;
    //      }else{
    //          break;
    //      }
    //  }
    // }
    return $arr;
}

快速排序法

function quickSort($arr){
    $arr_length = count($arr);
    if ($arr_length <= 1) {
        return $arr;
    }
    $base_val = $arr[0];
    $array_left = [];
    $array_right = [];
    for ($i=1; $i < $arr_length; $i++) { 
        if ($base_val > $arr[$i]) {
            $array_left[] = $arr[$i];
        }else{
            $array_right[] = $arr[$i];
        }
    }
    $array_left = quickSort($array_left);
    $array_right = quickSort($array_right);
    return array_merge($array_left,array($base_val),$array_right);
}

相关文章

网友评论

      本文标题:算法(冒泡、选择、插入、快速)

      本文链接:https://www.haomeiwen.com/subject/djtrnttx.html