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

我们在网上经常可以看到C语言、JAVA语言实现的各类排序算法，但是很少见有人分享用PHP实现的排序算法，究其原因在于一方面PHP属于解释型语言，另一方面PHP已经为我们写好了相关排序算法，无需程序员再手动去写，毕竟我们自己实现的算法不管是从时间复杂度还是空间复杂度都未必有原生的算法优秀。

PHP排序算法汇总

尽管如此，波波还是希望通过这篇笔记将常用的排序算法进行一个汇总，在此之前波波也零星的分享了一些排序算法，所以喜欢研究算法的朋友收藏这一篇笔记就够了。

一、冒泡排序算法：

冒泡排序简单的理解就是一组数据，两个两个进行比较，把最小的气泡升到最前面，把最大的气泡沉到底。

冒泡排序源码：

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

二、快速排序算法：

从数列中挑出一个元素，称为 “基准”（pivot)。所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。C 语言中的 qsort就是快速排序。

快速排序算法源码：

  1. /**
  2.  * QuickSort
  3.  *
  4.  * @param array $container
  5.  * @return array
  6.  */
  7. function QuickSort(array $container)
  8. {
  9.     $count = count($container);
  10.     if ($count <= 1) { // 基线条件为空或者只包含一个元素，只需要原样返回数组
  11.         return $container;
  12.     }
  13.     $pivot = $container[0]; // 基准值 pivot
  14.     $left  = $right = [];
  15.     for ($i = 1; $i < $count; $i++) {
  16.         if ($container[$i] < $pivot) {
  17.             $left[] = $container[$i];
  18.         } else {
  19.             $right[] = $container[$i];
  20.         }
  21.     }
  22.     $left  = QuickSort($left);
  23.     $right = QuickSort($right);
  24.     return array_merge($left, [$container[0]], $right);
  25. }

三、插入排序算法：

算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

插入排序算法源码：

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

四、选择排序算法：

选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

选择排序算法源码：

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

五、大根堆排序：

堆排序(HeapSort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。可以利用数组的特点快速定位指定索引的元素。堆分为大根堆和小根堆，是完全二叉树。

堆排序利用了大根堆堆顶记录的关键字最大（或最小）这一特征。大根堆的要求是每个节点的值都不大于其父节点的值，即A[PARENT[i]] >= A[i]。在数组的非降序排序中，需要使用的就是大根堆，

大根堆排序源码：

  1. class HeapSort
  2. {
  3.     /**
  4.      * @var int
  5.      */
  6.     protected $count;
  7.     /**
  8.      * @var array
  9.      */
  10.     protected $data;
  11.     /**
  12.      * HeapSort constructor.
  13.      *
  14.      * @param array $data
  15.      */
  16.     public function __construct(array $data)
  17.     {
  18.         $this->count = count($data);
  19.         $this->data  = $data;
  20.     }
  21.     /**
  22.      * Action
  23.      *
  24.      * @return array
  25.      */
  26.     public function run()
  27.     {
  28.         $this->createHeap();
  29.         while ($this->count > 0) {
  30.             /* 这是一个大顶堆 , 所以堆顶的节点必须是最大的
  31.                根据此特点 , 每次都将堆顶数据移到最后一位
  32.                然后对剩余数据节点再次建造堆就可以 */
  33.             $this->swap($this->data[0], $this->data[--$this->count]);
  34.             $this->buildHeap($this->data, 0, $this->count);
  35.         }
  36.         return $this->data;
  37.     }
  38.     /**
  39.      * 创建一个堆
  40.      */
  41.     public function createHeap()
  42.     {
  43.         $i = floor($this->count / 2) + 1;
  44.         while ($i--) {
  45.             $this->buildHeap($this->data, $i, $this->count);
  46.         }
  47.     }
  48.     /**
  49.      * 从 数组 的第 $i 个节点开始至 数组长度为0 结束 , 递归的将其 ( 包括其子节点 ) 转化为一个小顶堆
  50.      *
  51.      * @param $data
  52.      * @param $i
  53.      * @param $count
  54.      */
  55.     public function buildHeap(array &$data, $i, $count)
  56.     {
  57.         if (false === $i < $count) {
  58.             return;
  59.         }
  60.         // 获取左 / 右节点
  61.         $right = ($left = 2 * $i + 1) + 1;
  62.         $max   = $i;
  63.         // 如果左子节点大于当前节点 , 那么记录左节点键名
  64.         if ($left < $count && $data[$i] < $data[$left]) {
  65.             $max = $left;
  66.         }
  67.         // 如果右节点大于刚刚记录的 $max , 那么再次交换
  68.         if ($right < $count && $data[$max] < $data[$right]) {
  69.             $max = $right;
  70.         }
  71.         if ($max !== $i && $max < $count) {
  72.             $this->swap($data[$i], $data[$max]);
  73.             $this->buildHeap($data, $max, $count);
  74.         }
  75.     }
  76.     /**
  77.      * 交换空间
  78.      *
  79.      * @param $left
  80.      * @param $right
  81.      */
  82.     public function swap(&$left, &$right)
  83.     {
  84.         list($left, $right) = array ($right, $left);
  85.     }
  86. }
1 2
你想把广告放到这里吗？

发表评论

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