浅析三种排序和我写的一种排序

要说起对数组进行排序，php很擅长，php有非常多的数组函数，其中就包括了排序。冒泡排序，选择排序，插入排序，今天将这三种排序思想及原理进行记录，及自己写的一个排序函数。

冒泡

冒泡排序法，名字很有意思，也是我认为最好理解其思想及原理的一个排序法。

第一层循环只做循环次数限制，第二层循环两两相邻的比较，数值大的往下沉，数值小的往上浮

public function bubbleSort($arr)
{    
    for ($i = 0; $i < count($arr) - 1; $i += 1) {
            $temp = 0;//交换变量
            $flag = true;//一个记录标志
            for ($j = 0; $j < count($arr) - 1 - $i; $j += 1) {
                   if ($arr[$j] > $arr[$j + 1]) {
                        $temp = $arr[$j];
                        $arr[$j] = $arr[$j + 1];
                        $arr[$j + 1] = $temp;
                        $flag = false;
                        }        
             }
            if ($flag === true) {
                return $arr;//已经是有序的了        
            }    
     }  
         return $arr;
}

传进来一个数组，循环这个数组，第一层 for 循环判断-1是因为按照冒泡排序来讲，假设有5个键，有四个确认了位置的话第五个自然是在它该在的位置，所以无需多循环一遍。

第二层 for 循环开始取相邻的比较，如果判断成立则利用 temp 变量互换位置，然后再挨个比较。
假设传进去的数组是这样array(5,0,-1);在第一次排序后也就是第二层循环的第一次循环，$arr 是(0,5,-1) ,第二次 $arr(0,-1,5) ,第三次第二层已跳出，判断已经不成立，跳回第一层循环，继续开始第二层循环第二层循环只会执行一遍 $arr(-1,0,5)执行完毕后返回已排好序的数组。

flag有优化代码的作用，如果传进来的数组本身就是一个有序数组的话，是不会走第二层循环的if条件的，所以flag===true，第二层循环完成后就会直接返回不会再经过第一层循环了。
冒泡排序利用第二层的相邻的两个键值做对比，完成互换位置，这是核心思想。这个冒泡应该是再没得优化了，网上那些优化顶多也就优化成这样。

选择排序

public function selectSort($arr)//假设当前的值为最小的，如果找到比他还小的就互换位置
{
    for ($i = 0; $i < count($arr); $i += 1) {
         $minval = $arr[$i];
         $minkey = $i;
         $flag = true;
         for ($j = $i + 1; $j < count($arr); $j += 1) {//循环过后最终最小值出现
             if ($arr[$j] < $minval) {
                 $minval = $arr[$j];
                 $minkey = $j;
                 $flag = false;
             }
         }
         if ($flag == false) {//说明最小值有经过交换到$i位
             $arr[$minkey] = $arr[$i];
             $arr[$i] = $minval;
         }
    }
     return $arr;
}

选择排序法的思想，假设第一个键为最小值，从第二层循环开始轮番跟假设值进行比较比较成功后进行换为，第二层循环结束后，此数组中最小的值被交换到最前面，接着又开始第一层循环。

这个选择排序法，我看很多网上还加了一个交换变量，其实这里没必要用到交换变量，因为假设值的键和值都已经做了存储了。

选择排序法在跳出第二层循环的时候就会永久确认一个数值的位置，这点和冒泡不一样。

其实选择排序法还有更加简洁的办法，我写的这个选择排序在网上能查到的应该算是简洁明了的了，但是其实这个选择排序法还能更加简洁！

我自己写的排序最后讲，那是第一次尝试写冒泡中，当时思维比较混乱的时候写出来的，思想其实跟选择排序是一样的，但是比这个选择排序要简洁得多，但是相对起理解选择排序法来说，还是这个更好去理解。

插入排序

public function insertSort($arr)
{    
//先默认键为0的值已经为有序，键值为$i的为待插入数，只要待插入数小于前面的数，就代表不确定插入位置，    
//插入位置的确定是待插入数$i,$i要比$i-1要大比$i+1要小
    for ($i = 1; $i < count($arr); $i += 1) {
        $inserval = $arr[$i];//待插入数
        $inserindex = $i - 1;//与前面一位数字进行比较
        while ($inserindex >= 0 && $inserval < $arr[$inserindex]) {//只要键大于或等于0并且待插入数要小于前面一位数，
            $arr[$inserindex + 1] = $arr[$inserindex];//如果小于的话，把比较数往后面挪一下
            $inserindex -= 1;//此时将比较数再往前一步，相当于带插入数还不确定位置，还要跟前面的再次比较一下
        }        
        //当以上条件不满足，即将走到这一步，        
        $arr[$inserindex + 1] = $inserval;//将待插入数插入(插入位置绝对是比较数字位置后一位)    
    }    
    return $arr;
}       

插入排序，跟玩牌一样，确认一张牌不动，比不动牌小的往左放，大的往右边放。

插入排序效率要相对于高一些。
下面要贴出来的是我巧合之中自己摸索出来的一个排序，核心思想其实还是跟选择排序一样，但是你多看几遍会发现其实完全没有必要将 $arr[$i] 的键值保存下来，因为在当前循环中 $i 并不会改变,只需要一个交换变量就够了。所以看下面。

我写的排序

public function mySort($arr)//在一轮中找到最小值{
    $temp = 0;
     for ($i = 0; $i < count($arr) - 1; $i += 1) {
          for ($j = 0 + $i; $j < count($arr); $j += 1) { 
              if ($arr[$i] > $arr[$j]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$j];
                $arr[$j] = $temp;
              }        
          }    
     }
     return $arr;
}

这看起来是不是更加简洁明了？核心思想其实是跟选择排序一模一样哦。

原文链接:浅析三种排序和我写的一种排序-PHP