【PHP排序算法】PHP排序算法汇总，值得收藏

六、飞梭排序算法：

飞梭排序是冒泡排序的轻微变形。不同的地方在于，飞梭排序是从低到高然后从高到低来回排序，而冒泡排序则仅从低到高去比较序列里的每个元素。

先对数组从左到右进行冒泡排序（升序），则最大的元素去到最右端；再对数组从右到左进行冒泡排序（降序），则最小的元素去到最左端；以此类推，依次改变冒泡的方向，并不断缩小未排序元素的范围，直到最后一个元素结束。

飞梭排序算法源码：

  1. /**
  2.  * ShuttleSort
  3.  *
  4.  * @param array $data
  5.  * @return array
  6.  */
  7. function ShuttleSort(array $data)
  8. {
  9.     /**
  10.      * 替换方法
  11.      *
  12.      * @param array $data
  13.      * @param       $i
  14.      * @param       $j
  15.      * @return array
  16.      */
  17.     $swap = function (array &$data, $i, $j) {
  18.         $temp     = $data[$i];
  19.         $data[$i] = $data[$j];
  20.         $data[$j] = $temp;
  21.         return $data;
  22.     };
  23.     $count = count($data);
  24.     $left  = 0;
  25.     $right = $count - 1;
  26.     while ($left < $right) {
  27.         // 从左到右
  28.         $lastRight = 0;
  29.         for ($i = $left; $i < $right; $i++) {
  30.             if ($data[$i] > $data[$i + 1]) {
  31.                 $swap($data, $i, 1 + $i);
  32.                 $lastRight = $i;
  33.             }
  34.         }
  35.         $right = $lastRight;
  36.         // 从右到左
  37.         $lastLeft = 0;
  38.         for ($j = $right; $left < $j; $j--) {
  39.             if ($data[$j - 1] > $data[$j]) {
  40.                 $swap($data, $j - 1, $j);
  41.                 $lastLeft = $j;
  42.             }
  43.         }
  44.         $left = $lastLeft;
  45.     }
  46.     return $data;
  47. }

七、希尔排序算法：

希尔排序是基于插入排序的，区别在于插入排序是相邻的一个个比较（类似于希尔中h=1的情形），而希尔排序是距离h的比较和替换。

希尔排序中一个常数因子n，原数组被分成各个小组，每个小组由h个元素组成，很可能会有多余的元素。当然每次循环的时候，h也是递减的（h=h/n）。第一次循环就是从下标为h开始。希尔排序的一个思想就是，分成小组去排序。

希尔排序算法源码：

  1. /**
  2.  * ShellSort
  3.  *
  4.  * @param array $container
  5.  * @return array
  6.  */
  7. function ShellSort(array $container)
  8. {
  9.     $count = count($container);
  10.     for ($increment = intval($count / 2); $increment > 0; $increment = intval($increment / 2)) {
  11.         for ($i = $increment; $i < $count; $i++) {
  12.             $temp = $container[$i];
  13.             for ($j = $i; $j >= $increment; $j -= $increment) {
  14.                 if ($temp < $container[$j - $increment]) {
  15.                     $container[$j] = $container[$j - $increment];
  16.                 } else {
  17.                     break;
  18.                 }
  19.             }
  20.             $container[$j] = $temp;
  21.         }
  22.     }
  23.     return $container;
  24. }

八、归并排序算法：

归并排序的算法我们通常用递归实现，先把待排序区间[s,t]以中点二分，接着把左边子区间排序，再把右边子区间排序，最后把左区间和右区间用一次归并操作合并成有序的区间[s,t]。

实现思路：

比较a[i]和b[j]的大小，若a[i]≤b[j]，则将第一个有序表中的元素a[i]复制到r[k]中，并令i和k分别加上1；否则将第二个有序表中的元素b[j]复制到r[k]中，并令j和k分别加上1，如此循环下去，直到其中一个有序表取完，然后再将另一个有序表中剩余的元素复制到r中从下标k到下标t的单元。

归并排序算法源码：

  1. class MergeSort
  2. {
  3.     /**
  4.      * MergeSort constructor.
  5.      * 是开始递归函数的一个驱动函数
  6.      *
  7.      * @param array $arr 待排序的数组
  8.      */
  9.     public function __construct(array $arr)
  10.     {
  11.         $this->mSort($arr, 0, count($arr) - 1);
  12.         var_dump($arr);
  13.     }
  14.     /**
  15.      * 实际实现归并排序的程序
  16.      *
  17.      * @param $arr     array   需要排序的数组
  18.      * @param $left    int     子序列的左下标值
  19.      * @param $right   int     子序列的右下标值
  20.      */
  21.     public function mSort(&$arr, $left, $right)
  22.     {
  23.         if ($left < $right) {
  24.             //说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
  25.             //计算拆分的位置，长度/2 去整
  26.             $center = floor(($left + $right) / 2);
  27.             //递归调用对左边进行再次排序：
  28.             $this->mSort($arr, $left, $center);
  29.             //递归调用对右边进行再次排序
  30.             $this->mSort($arr, $center + 1, $right);
  31.             //合并排序结果
  32.             $this->mergeArray($arr, $left, $center, $right);
  33.         }
  34.     }
  35.     /**
  36.      * 将两个有序数组合并成一个有序数组
  37.      *
  38.      * @param &$arr   , 待排序的所有元素
  39.      * @param $left   , 排序子数组A的开始下标
  40.      * @param $center , 排序子数组A与排序子数组B的中间下标，也就是数组A的结束下标
  41.      * @param $right  , 排序子数组B的结束下标（开始为$center+1)
  42.      */
  43.     public function mergeArray(&$arr, $left, $center, $right)
  44.     {
  45.         echo '| ' . $left . ' - ' . $center . ' - ' . $right . ' - ' . implode(',', $arr) . PHP_EOL;
  46.         //设置两个起始位置标记
  47.         $a_i  = $left;
  48.         $b_i  = $center + 1;
  49.         $temp = [];
  50.         while ($a_i <= $center && $b_i <= $right) {
  51.             //当数组A和数组B都没有越界时
  52.             if ($arr[ $a_i ] < $arr[ $b_i ]) {
  53.                 $temp[] = $arr[ $a_i++ ];
  54.             } else {
  55.                 $temp[] = $arr[ $b_i++ ];
  56.             }
  57.         }
  58.         //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
  59.         while ($a_i <= $center) {
  60.             $temp[] = $arr[ $a_i++ ];
  61.         }
  62.         //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
  63.         while ($b_i <= $right) {
  64.             $temp[] = $arr[ $b_i++ ];
  65.         }
  66.         //将$arrC内排序好的部分，写入到$arr内：
  67.         for ($i = 0, $len = count($temp); $i < $len; $i++) {
  68.             $arr[ $left + $i ] = $temp[ $i ];
  69.         }
  70.     }
  71. }

以上算法由波波收集整理自网络，全部由PHP实现，旨在为喜欢PHP语言的朋友提供一些算法研究的帮助。欢迎大家收藏！

 

1 2
你想把广告放到这里吗？

发表评论

您必须 登录 才能发表留言！