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

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

本文由 邓尘锋 创作，采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: May 4, 2019 at 11:38 am

← ↓ ↑
Comments are closed.