PHP实现几种基本排序算法--冒泡排序法，快速排序法，选择排序法，插入排序法

﹏ヽ暗。殇╰゛Y 2022-06-06 10:07 284阅读 0赞

前提：分别用冒泡排序法，快速排序法，选择排序法，插入排序法将下面数组中的值按照从小到大的顺序进行排序。   
$arr(1,43,54,62,21,66,32,78,36,76,39);

## 1. 冒泡排序 ##

思路分析：在要排序的一组数中，对当前还未排好的序列，从前往后对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。即，每当两相邻的数比较后发现它们的排序与排序要求相反时，就将它们互换。  
  
代码实现：  
$arr=array(1,43,54,62,21,66,32,78,36,76,39);    
function bubbleSort($arr)  
\{    
  $len=count($arr);  
  //该层循环控制 需要冒泡的轮数  
  for($i=1;$i<$len;$i++)  
  \{ //该层循环用来控制每轮 冒出一个数 需要比较的次数  
    for($k=0;$k<$len-$i;$k++)  
    \{  
       if($arr\[$k\]>$arr\[$k+1\])  
        \{  
            $tmp=$arr\[$k+1\];  
            $arr\[$k+1\]=$arr\[$k\];  
            $arr\[$k\]=$tmp;  
        \}  
    \}  
  \}  
  return $arr;  
\}

## 2. 选择排序  ##

思路分析：在要排序的一组数中，选出最小的一个数与第一个位置的数交换。然后在剩下的数当中再找最小的与第二个位置的数交换，如此循环到倒数第二个数和最后一个数比较为止。  
  
代码实现：  
function selectSort($arr) \{  
//双重循环完成，外层控制轮数，内层控制比较次数  
 $len=count($arr);  
    for($i=0; $i<$len-1; $i++) \{  
        //先假设最小的值的位置  
        $p = $i;  
          
        for($j=$i+1; $j<$len; $j++) \{  
            //$arr\[$p\] 是当前已知的最小值  
            if($arr\[$p\] > $arr\[$j\]) \{  
            //比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。  
                $p = $j;  
            \}  
        \}  
        //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，则位置互换即可。  
        if($p != $i) \{  
            $tmp = $arr\[$p\];  
            $arr\[$p\] = $arr\[$i\];  
            $arr\[$i\] = $tmp;  
        \}  
    \}  
    //返回最终结果  
    return $arr;  
\}

## 3.插入排序 ##

思路分析：在要排序的一组数中，假设前面的数已经是排好顺序的，现在要把第n个数插到前面的有序数中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。  
  
代码实现：  
function insertSort($arr) \{  
    $len=count($arr);   
    for($i=1, $i<$len; $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;  
\}

## 4.快速排序   ##

思路分析：选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。  
  
代码实现：  
function quickSort($arr) \{  
    //先判断是否需要继续进行  
    $length = count($arr);  
    if($length <= 1) \{  
        return $arr;  
    \}  
    //选择第一个元素作为基准  
    $base\_num = $arr\[0\];  
    //遍历除了标尺外的所有元素，按照大小关系放入两个数组内  
    //初始化两个数组  
    $left\_array = array();  //小于基准的  
    $right\_array = array();  //大于基准的  
    for($i=1; $i<$length; $i++) \{  
        if($base\_num > $arr\[$i\]) \{  
            //放入左边数组  
            $left\_array\[\] = $arr\[$i\];  
        \} else \{  
            //放入右边  
            $right\_array\[\] = $arr\[$i\];  
        \}  
    \}  
    //再分别对左边和右边的数组进行相同的排序处理方式递归调用这个函数  
    $left\_array = quick\_sort($left\_array);  
    $right\_array = quick\_sort($right\_array);  
    //合并  
    return array\_merge($left\_array, array($base\_num), $right\_array);  
\}

转自：http://mp.weixin.qq.com/s?\_\_biz=MzA5Mjg2NTQxOA==&mid=2650420273&idx=1&sn=f2db8b34f560d9d8253af5fb712d172e&scene=4\#wechat\_redirect

/*
     * php 四种排序算法的时间与内置的sort排序比较
     * 3000个元素，四种算法的排序所用的时间比较
     * 冒泡排序 857.98192024231ms
     * 选择排序 903.74493598938ms
     * 插入排序 296.8270778656ms
     * 快速排序 15.607833862305ms
     * sort排序 0.95200538635254ms
     * 归并排序 14.61386680603ms
     * */
    
    
    /*
    * @param 冒泡排序
    * 它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。
    * 走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
    * */
    function BubbleSort($arr) {
        $len = count($arr);
        //设置一个空数组 用来接收冒出来的泡
        //该层循环控制 需要冒泡的轮数
        for ($i = 1; $i < $len; $i++) {
            $flag = false;    //本趟排序开始前，交换标志应为假
            //该层循环用来控制每轮 冒出一个数 需要比较的次数
            for ($k = 0; $k < $len - $i; $k++) {
                //从小到大排序
                if ($arr[$k] > $arr[$k + 1]) {
                    $tmp = $arr[$k + 1];
                    $arr[$k + 1] = $arr[$k];
                    $arr[$k] = $tmp;
                    $flag = true;
                }
            }
            if(!$flag) return $arr;
        }
    }
    
    /*
    * @param 选择排序法
    * 每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
    * 选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）
    * */
    function selectSort($array){
        $temp = 0;
        for($i = 0;$i < count($array) - 1;$i++){
            $minVal = $array[$i]; //假设$i就是最小值
            $minValIndex = $i;
            for($j = $i+1;$j < count($array);$j++){
                if($minVal > $array[$j]){ //从小到大排列
                    $minVal = $array[$j]; //找最小值
                    $minValIndex = $j;
                }
            }
            $temp = $array[$i];
            $array[$i] = $array[$minValIndex];
            $array[$minValIndex] = $temp;
        }
    }
    
    /*
    * 插入排序法
    * 每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。
    * 算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。
    * */
    function insertSort($array){ //从小到大排列
    //先默认$array[0]，已经有序，是有序表
        for($i = 1;$i < count($array);$i++){
            $insertVal = $array[$i]; //$insertVal是准备插入的数
            $insertIndex = $i - 1; //有序表中准备比较的数的下标
            while($insertIndex >= 0 && $insertVal < $array[$insertIndex]){
                $array[$insertIndex + 1] = $array[$insertIndex]; //将数组往后挪
                $insertIndex--; //将下标往前挪，准备与前一个进行比较
            }
            if($insertIndex + 1 !== $i){
                $array[$insertIndex + 1] = $insertVal;
            }
        }
    }
    
    /*
    * 快速排序法
    * 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，
    * 然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
    * */
    function quickSort($array){
        if(!isset($array[1]))  return $array;
        $mid = $array[0]; //获取一个用于分割的关键字，一般是首个元素
        $leftArray = array();
        $rightArray = array();
        foreach($array as $v){
            if($v > $mid)
                $rightArray[] = $v; //把比$mid大的数放到一个数组里
            if($v < $mid)
                $leftArray[] = $v; //把比$mid小的数放到另一个数组里
        }
        $leftArray = quickSort($leftArray); //把比较小的数组再一次进行分割
        $leftArray[] = $mid; //把分割的元素加到小的数组后面，不能忘了它哦
        $rightArray = quickSort($rightArray); //把比较大的数组再一次进行分割
        return array_merge($leftArray,$rightArray); //组合两个结果
    }
    
    /*
    * 归并排序
    * 归并排序是指将两个或两个以上有序的数列（或有序表），合并成一个仍然有序的数列（或有序表）。
    * 这样的排序方法经常用于多个有序的数据文件归并成一个有序的数据文件。
    * */
    function mergeSort(&$arr) {
        $len = count($arr);//求得数组长度
        mSort($arr, 0, $len-1);
        return $arr;
    }
    //实际实现归并排序的程序
    function mSort(&$arr, $left, $right) {
        if($left < $right) {
            //说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
            //计算拆分的位置，长度/2 去整
            $center = floor(($left+$right) / 2);
            //递归调用对左边进行再次排序：
            mSort($arr, $left, $center);
            //递归调用对右边进行再次排序
            mSort($arr, $center+1, $right);
            //合并排序结果
            mergeArray($arr, $left, $center, $right);
        }
    }
    //将两个有序数组合并成一个有序数组
    function mergeArray(&$arr, $left, $center, $right) {
        //设置两个起始位置标记
        $a_i = $left;
        $b_i = $center+1;
        while($a_i<=$center && $b_i<=$right) {
            //当数组A和数组B都没有越界时
            if($arr[$a_i] < $arr[$b_i]) {
                $temp[] = $arr[$a_i++];
            } else {
                $temp[] = $arr[$b_i++];
            }
        }
        //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
        while($a_i <= $center) {
            $temp[] = $arr[$a_i++];
        }
        //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
        while($b_i <= $right) {
            $temp[] = $arr[$b_i++];
        }
    
        //将$arrC内排序好的部分，写入到$arr内：
        for($i=0, $len=count($temp); $i<$len; $i++) {
            $arr[$left+$i] = $temp[$i];
        }
    }
    
    
    
    $a = array_rand(range(1,10000), 3000); //生成3000个元素的随机数组
    shuffle($a); //打乱数组的顺序
    $t1 = microtime(true);
    BubbleSort($a); //冒泡排序
    $t2 = microtime(true);
    echo "冒泡排序用时：".(($t2-$t1)*1000).'ms'."\n";
    
    $t3 = microtime(true);
    selectSort($a); //选择排序
    $t4 = microtime(true);
    echo "选择排序用时：".(($t4-$t3)*1000).'ms'."\n";
    
    $t5 = microtime(true);
    insertSort($a); //插入排序
    $t6 = microtime(true);
    echo "插入排序用时：".(($t6-$t5)*1000).'ms'."\n";
    
    $t7 = microtime(true);
    quickSort($a); //快速排序
    $t8 = microtime(true);
    echo "快速排序用时：".(($t8-$t7)*1000).'ms'."\n";
    
    $t9 = microtime(true);
    sort($a);
    $t10 = microtime(true);
    echo "sort排序用时：".(($t10-$t9)*1000)."ms"."\n";
    
    $t11 = microtime(true);
    mergeSort($a);
    $t12 = microtime(true);
    echo "归并排序用时：".(($t12-$t11)*1000)."ms";

转自: [http://www.cnblogs.com/jing1208/p/6289840.html][http_www.cnblogs.com_jing1208_p_6289840.html]

[http_www.cnblogs.com_jing1208_p_6289840.html]: http://www.cnblogs.com/jing1208/p/6289840.html