[一天一个排序算法] - 冒泡算法最优 & 选择排序
in 其他 with 0 条评论

[一天一个排序算法] - 冒泡算法最优 & 选择排序

in 其他 with 0 comment

[一天一个排序算法] - 冒泡算法最优 & 选择排序

每天一点点 , 进步还是非常大的,虽然我是学了又忘记,但是还是得加油啊,就当吧博客当作笔记了,今天来学习一些排序算法中最基本的算法,冒泡排序

首先,冒泡排序, 冒泡冒泡,就是一个个的冒出小泡呗。

Image text

首先,亮出最基本的 冒泡排序出来

 function dubble_sort( &$arr ) : void {
     $len = count($arr);
 
     for ($i=0; $i <$len ; $i++) { 
         for ($j=0; $j <$len-1 ; $j++) { 
             if( $arr[$j+1] < $arr[$j] ) {
                 list($arr[$j] , $arr[$j+1]) = [ $arr[$j+1] , $arr[$j] ];
             }
         }
     }
 
     $arr = implode('-',$arr) . '<br/>';
 }

双层循环,给每个元素进行遍历,在子循环中交换元素

这里采用了 list 交换元素, 至于为什么,自己理解哦,我们这里主要来学习,最优算法的


  1. 首先优化一

     function dubble_sort_s( &$arr ) : void {
         $len = count($arr);
      
         for ($i=0; $i <$len ; $i++) {
             $swapped = false;
             for ($j=0; $j <$len-1 ; $j++) { 
                 if( $arr[$j+1] < $arr[$j] ) {
                     list($arr[$j] , $arr[$j+1]) = [ $arr[$j+1] , $arr[$j] ];
                     $swapped = true;
                 }
             }
             if( !$swapped ) break;
         }
     
         $arr = implode('-',$arr);
     }
    

我们给每个子循环体添加了一个 参数 $swapped , 仔细想一想,当子循环体第一次循环的时候

例: 2 4 8 1 9 

    2 4 1 8 9 true  (发生了交换)
    
    2 1 4 8 9 true  (发生了交换)
    
    1 2 4 8 9 true  (发生了交换)
    
    1 2 4 8 9 false 

这里只执行了 父循环体三次, 就完成了排序,试想一下,这不是消耗了资源吗

所以,我没可以给他添加变量,检查是否发生了交换,如果没有则退出循环


  1. 优化二

    function dubble_sort_x( &$arr ) : void { $len = count($arr);

     for ($i=0; $i < $len ; $i++) {
     
         $swapped = false;
         for ($j=0; $j <$len-$i-1 ; $j++) {   # $j 循环体改变了
             if( $arr[$j+1] < $arr[$j] ) {
                 list($arr[$j] , $arr[$j+1]) = [ $arr[$j+1] , $arr[$j] ];
                 $swapped = true;
             }
         }
         if( !$swapped ) break;
     }
    
     $arr = implode('-',$arr);
    

    }

我们修改了子循环体的循环次数,为什么呢,如下

例如: 2 4 1 8 9 2

     2 1 4 8 2 9  # 1
      
     2 1 4 2 8 9  # 2 
     
     1 2 2 4 8 9  # 3

仔细瞧瞧, 你会发现 ,每次循环绝对会把最后一个参数给比较掉,前面的参数较来说不确定

所以在循环中,我们如果不添加如上,每次循环都会对尾部的元素多进行循环一次,这是无谓的消耗


  1. 优化三

     function dubble_sort_z( &$arr ) : void {
         $len = count($arr);
     
         $swapped = false;
         $bound = count($arr-1);
         for ($i=0; $i <$len ; $i++) {
             for ($j=0; $j <$bound ; $j++) { 
                 if( $arr[$j+1] < $arr[$j] ) {
                     list($arr[$j] , $arr[$j+1]) = [ $arr[$j+1] , $arr[$j] ];
                     $swapped = true;
                     $newBound = $j;
                 }
             }
             if( !$swapped ) break;
         }
     
         $arr = implode('-',$arr);
     }
    

这个和优化二的差不多,尝试理解一下,$newBound 代表当前已经排序的最终位置,后面的数项可以不需要进行排序了,直接精确定位,下次子循环的时候将不在进行后续的循环


选择排序

选择排序,即是将最小的数前置,将所有的数字与之对比,然后进行交换

function selectionSort( &$arr ) {
    $len = count( $arr ) ;

    for ( $i=0; $i<$len ; $i++ ) {
        $min = $arr[$i];

        # 遍历,找出比第一个小的值出来
        for ( $j=$i+1; $j<$len; $j++ ) {
            if( $arr[$j] < $min ) {
                $min = $arr[$j];
                $index = $j;
            }
        }

        # 已经找出了最小的,再进行交换
        list( $arr[$i] , $arr[$index]) = [$min , $arr[$i]];
    }

    $arr = implode('-',$arr);

}


例: 2 7 6 4 3 5 
    
    2 3 6 4 7 5
    
    2 3 4 6 7 5 
    
    2 3 4 5 7 6 
    
    2 3 4 5 6 7
Responses