排序算法

• 冒泡排序

  /**
  * 冒泡排序
  *
  * @params $arr 要排序的数组
  * @params $sot 默认升序排序，false 降序排序
  */
    function bubble_sort($arr,$sot = true)
    {
        $len = count($arr);
        for($i=0;$i<$len-1;$i++){
            //用来判断是否发生交换，没有则可以结束排序
            $flag = false;
            $mid = null;
            for($j=0;$j<$len-$i-1;$j++){
                if($sot){
                    //升序排序
                    if($arr[$j]>$arr[$j+1]){
                        $mid = $arr[$j];
                        $arr[$j] = $arr[$j+1];
                        $arr[$j+1] = $mid;
                        $flag = true;
                    }
                }else{
                    //降序排序
                    if($arr[$j]<$arr[$j+1]){
                        $mid = $arr[$j];
                        $arr[$j] = $arr[$j+1];
                        $arr[$j+1] = $mid;
                        $flag = true;
                    }
                }
            }
            if(!$flag){
                //排序已完成
                break;
            }
        }
        return $arr;
    }

• 插入排序

     /**
     * 插入排序
     *
     * @params $arr 要排序的数组
     * @params $flag 默认升序排序 false时，降序排序
     */
    function insertSort($arr,$flag = true)
    {
        $len = count($arr);
  
        for($i = 0;$i<$len-1;$i++){
            $preIndex = $i; //记录位置
            $current = $arr[$preIndex+1];//记录下一个的值
  
            while($preIndex >=0){
                if($flag){
                    if(($current > $arr[$preIndex])){
                        break;
                    }
                }else{
                    if($current < $arr[$preIndex]){
                        break;
                    }
                }
                $arr[$preIndex+1] = $arr[$preIndex];
                $preIndex--;
            }
            $arr[$preIndex+1] = $current;
        }
        return $arr;
    }

• 选择排序

  /**
     * 选择排序
     *
     * @params $arr 要排序的数组
     * @params $flag 默认true时，升序排序，否则降序排序
     */
    function select_sort($arr,$flag = true)
    {
        $len = count($arr);
  
        for($i=0;$i<$len;$i++){
            $currentIndex = null;
            $currentIndex = $i; //当前比较元素的位置
            for($j=$i+1;$j<$len;$j++){
                if($flag ? $arr[$j]<$arr[$currentIndex] : $arr[$j]>$arr[$currentIndex]){
                    $currentIndex = $j;
                }
            }
            //交换元素
            $mid = null;
            if($i != $currentIndex){
                $mid = $arr[$i];
                $arr[$i] = $arr[$currentIndex];
                $arr[$currentIndex] = $mid;
            }
        }
        return $arr;
    }

• 希尔排序

  /**
     * 希尔排序
     * @params $arr 排序数组
     * @params $flag 默认升序排序 false 则降序排序
     */
    function shell_sort($arr,$flag = true)
    {
        $len = count($arr);
        for($gap = floor($len/2);$gap > 0;$gap = floor($gap/2)){
            for($j = $gap;$j < $len;$j++){
                for($k = $j-$gap;$k >=0 && ($flag ? $arr[$k+$gap] < $arr[$k] : $arr[$k+$gap] > $arr[$k]);$k -= $gap){
                    $temp = $arr[$k];
                    $arr[$k] = $arr[$k+$gap];
                    $arr[$k+$gap] = $temp;
                }
            }
        }
        return $arr;
    }

• 二路归并排序

  $arr = [10, 2, 4, 56, 29, 33, 293, 83, 2, 22];
  function mergeSort(&$arr)
  {
     $left = 0; //第一个元素的下标
     $right = count($arr) -1; //最后一个元素的下标
     divSort($arr,$left,$right);
  }
  function divSort(&$arr,$left,$right)
  {
     if($left < $right) {
     //找出中间索引
     $mid = floor(($left + $right) / 2); //分成两组
     //对左边数组进行递归分组
     divSort($arr,$left,$mid);
     //对右边数组进行递归分组
     divSort($arr,$mid+1,$right);
     //将左右排好顺序的数组进行合并排序
     merge($arr,$left,$mid,$right);
  }
    //将两个有序数组合并成一个有序数组
  function merge(&$arr,$left,$mid,$right)
  {
    $i = $left;
    $j = $mid + 1;
    $temp = []; //临时合并数组
  
  while($i <= $mid && $j <= $right)
  {
    if($arr[$i] < $arr[$j]){
        $temp[] = $arr[$i];
        $i++;
    }else{
        $temp[] = $arr[$j];
    $j++;
  }
  }  //比完之后，假如左数组仍有剩余，则全部复制到 temp 数组
  while($i <= $mid) {
     $temp[] = $arr[$i];
     $i++;
  }
  //比完之后，假如右数组仍有剩余，则全部复制到 temp 数组
  while($j <= $right) {
     $temp[] = $arr[$j];
     $j++;
  }
  //将合并序列复制到原始序列中
  for($k = 0; $k < count($temp); $k++) {
     $arr[$left + $k] = $temp[$k];
  }
  }
  //测试
  
  mergeSort($arr);
  var_dump($arr);

• 快速排序

  function quickSort($arr)
  {
    $len = count($arr);
    if($len < 2) {
        return $arr;
    }
  
    $pivot = $arr[0];   //基准值
    $leftArray = $rightArray = array();
  
    for($i = 1; $i < $len; $i++) {
        if($arr[$i] < $pivot) {
            $leftArray[] = $arr[$i];
        }else{
            $rightArray[] = $arr[$i];
        }
    }
    $leftArray = quickSort($leftArray);
    $rightArray = quickSort($rightArray);
  
    return array_merge($leftArray,array($pivot),$rightArray);
  }
    //测试
    $newArr = quickSort($arr);
    var_dump($newArr);

• 计数排序

  function countingSort($arr, $maxValue = null)
    {
        if ($maxValue === null) {
            $maxValue = max($arr);
        }
        for ($m = 0; $m < $maxValue + 1; $m++) {
            $bucket[] = null;
        }
        $arrLen = count($arr);
        for ($i = 0; $i < $arrLen; $i++) {
            if (!array_key_exists($arr[$i], $bucket)) {
                $bucket[$arr[$i]] = 0;
            }
            $bucket[$arr[$i]]++;
        }
        $sortedIndex = 0;
        foreach ($bucket as $key => $len) {
            if ($len !== null){
                while($len > 0){
                    $arr[$sortedIndex++] = $key;
                    $len--;
                }
            }
  
        }
  
        return $arr;
    }
    //测试
    $newArr = countingSort($arr);
    var_dump($newArr);

本作品采用《CC 协议》，转载必须注明作者和本文链接