PHP 排序算法– 冒泡排序、快速排序、选择排序、插入排序

PHP 排序算法– 冒泡排序、快速排序、选择排序、插入排序

1. 冒泡排序 — 循环数组count($arr) 次,将数组的最后一个数据和前一个数据比较,从大到小(前一个大于后面)替换,从小到大(前面小于后面)替换

function bubbling_sort($arr)
{
     $count = count($arr);
     if($count <= 1)
     {
          return $arr;
     }
     for($i=0; $i<$count; $i++)
     {     
          for($j=$count-1; $j>$i; $j--)
          {
               if($arr[$j-1] > $arr[$j])
               {
                    $tmp = $arr[$j-1];
                    $arr[$j-1] = $arr[$j];
                    $arr[$j] = $tmp;
               }
          }
     }
     return $arr;
}

2. 快速排序 — 获取数组第一位数据保存,根据这个数将数组拆分两组,然后递归排序,合并数组。循环比第一位数小的是从小到大排序,比第一位数大按照从大到小排序

function quick_sort($arr)
{
     $count = count($arr);
     if($count <= 1)
     {
          return $arr;
     }

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

     return array_merge($left_arr, array($val), $right_arr);
}

3. 选择排序 — 每趟循环去一个数,与后面数比较,如果大或小进行替换

function select_sort($arr)
{
     $count = count($arr);
     if($count <= 1)
     {
          return $arr;
     }

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

4. 插入排序 — 循环取数组第$i位数字,for 循环中取得小于这个$i大小,while 循环比较

function insert_sort($arr)
{
     $count = count($arr);
     if($count <= 1)
     {
          return $arr;
     }

     for($i=1; $i<$count; $i++)
     {
          $val = $arr[$i];
          $j = $i -1;
          while($j >=0 && $arr[$j] > $val)
          {
               $arr[$j+1] = $arr[$j]
               $arr[$j] = $tmp;
               $j--;
          }
     }
     return $arr;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注