利用PHP实现常用的数据结构之排序（小白系列文章七）

jayzou 发布于2019-06-28 13:56 / 2906人阅读

摘要：排序严格来说不算数据结构，更应该归于算法一类，因为数据结构指的是数据与数据之间的关系，排序参与其中，更多的是让数据状态发生了改变。

排序严格来说不算数据结构，更应该归于算法一类，因为数据结构指的是数据与数据之间的关系，排序参与其中，更多的是让数据状态发生了改变。
于是，我们开始用PHP来聊聊算法。

引子

其实有一句话说的是不错的，“不必重复造轮子”，所以下面我将引用别人的文章作为本文的引文，直观的感受一下排序过程，同时我将加入自己的理解和代码+注释（其实很多话都在注释里面了）。事实上，如果作为一名纯粹的PHP Developer在日常开发中，有很多数据结构与算法是封装好了的，之所以要自己动手实现一下函数库，我认为有的人是为了装逼，当然有的人也确实能从中领悟到更复杂的逻辑和计算机底层执行规律从而提高编程能力，我是为了应试，这同样是一种能力。

引文

原文出自：[直观学习排序算法] 视觉直观感受若干常用排序算法

1 快速排序
介绍：

　　快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下，排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较，但这种状况并不常见。事实上，快速排序通常明显比其他Ο(n log n) 算法更快，因为它的内部循环（inner loop）可以在大部分的架构上很有效率地被实现出来，且在大部分真实世界的数据，可以决定设计的选择，减少所需时间的二次方项之可能性。

步骤：

从数列中挑出一个元素，称为 "基准"（pivot），
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。
排序效果：

代码实现：

= $pivot){ $high --; #如果数组的高值端（假定）大于枢轴单元，则高值端从后往前移动，说明真的是高值不必交换 } swap($arr,$low,$high); #直到高值端小等于枢轴单元，则交换元素，将较大值放到高值端，较小值放到低值端，注意交换的是数组单元 while($low < $high && $arr[$low] <= $pivot){ $low ++; #如果数组的低值端（假定）小于枢轴单元（注意，因为此前low和high已经交换过值了，现在的$arr[$low]已经不等于原先的值了），则高值端从后往前移动 } swap($arr,$low,$high); #直到低值端大等于枢轴单元，则交换元素，将较大值放到高值端，较小值放到低值端 } return $low; #随着low不断++，high不断--，它们在某处相遇，即枢轴下标，返回 } $arr = [4,7,3,2,7,6,8]; $res = main($arr); echo "

";
print_r($res);

2 归并排序
介绍：

　　归并排序（Merge sort，台湾译作：合并排序）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用

步骤：

申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列
设定两个指针，最初位置分别为两个已经排序序列的起始位置
比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置
重复步骤3直到某一指针达到序列尾
将另一序列剩下的所有元素直接复制到合并序列尾
排序效果：

代码实现：

";
print_r($res);

3 堆排序
介绍：

　　堆积排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆性质：即子结点的键值或索引总是小于（或者大于）它的父节点。

步骤：

这里补充一下原文空白
a.构造大（小）顶堆
b.每构造出一个顶堆，便能获取到最大或最小值，与尾节点交换，取出
c.循环构造顶堆，取值

排序效果：

代码实现：

0;$s--){
         createHeap($arr,$s,$m);
    }
    return $arr;
}

/**
 * TODO:构建大顶堆
 * @param $arr Array 待构数组
 * @param $s   int   开始下标（二叉树中最后一个拥有两个孩子的父节点序号）
 * @param $m   int   数组长度
 
   例：
           50
      /      
    30    60
  /      
 70      20    (这是不满足堆的定义的，需要重新构造)

 */


function createHeap(&$arr,$s,$m){
    $temp = $arr[$s];    #二叉树中最后一个拥有两个孩子的父节点
    for($i=2*$s;$i<$m;$i*=2){                            
        if($arr[$i]<$arr[$i+1]){    # i=2s i+1=2s+1 是s节点的左右孩子节点，先左右孩子节点比较大小，找出较大值
            $i++;
        }
        if($temp>=$arr[$i]){    #再将较大值与父节点比较，如果父节点大跳出循环
            break;
        }
        #如果父节点小，则交换父节点和该子节点值(无须额外辅助空间 空间复杂度为O(1))
         $arr[$s] = $arr[$i];    
         $s = $i;
    }
    $arr[$s] = $temp;
}


/**
 * TODO:堆排序
 */
function heapSort(&$arr){
    $length = count($arr)-1;
    for($i=$length;$i>1;$i--){    #这里i不需要和本身交换，所以不需要等于1
        swap($arr,1,$i);
        createHeap($arr,1,$i);#注意这里数组的长度会递减
    }
    return $arr;
}


$data = [0,5,1,9,3,7,4,8,6,2];
$res = main($data);
//$heapArr = heapSort($res);
echo "";
print_r($data);
4 选择排序
介绍：
　　选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
排序效果：

详细过程：
5 冒泡排序
介绍：
　　冒泡排序（Bubble Sort，台湾译为：泡沫排序或气泡排序）是一种简单的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
步骤：
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。
持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。
排序效果：

详细过程：
6 插入排序
介绍：
　　插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常采用in-place排序（即只需用到O(1)的额外空间的排序），因而在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
步骤：
从第一个元素开始，该元素可以认为已经被排序
取出下一个元素，在已经排序的元素序列中从后向前扫描
如果该元素（已排序）大于新元素，将该元素移到下一位置
重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
将新元素插入到该位置中
重复步骤2
排序效果：
（暂无）
详细过程：
7 希尔排序
介绍：
　　希尔排序，也称递减增量排序算法，是插入排序的一种高速而稳定的改进版本。
　　希尔排序是基于插入排序的以下两点性质而提出改进方法的：
插入排序在对几乎已经排好序的数据操作时， 效率高， 即可以达到线性排序的效率
但插入排序一般来说是低效的， 因为插入排序每次只能将数据移动一位
排序效果：


有时间再更。

GPU云服务器云服务器系列之系列之二架构之坑系列用php实现插入排序

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/25970.html

利用PHP实现常用的数据结构之数据结构浅析（小白系列文章二）

摘要：数据结构基本概念拆成数据和结构两个词来看，结构就是经过排列组合后映射到内存的一种关系，你想想化学中的分子结构就明白了，所以数据结构就是数据之间的一种关系，利用这些关系去处理强逻辑问题。该结构的数据元素之间存在着多对多的关系，也称网状结构。数据结构起源与起因起因：因为现实世界问题大多数是复杂的而非简单的数值计算，将数据进行适当的排序、组合将有利于计算机对复杂性逻辑问题的...

DesGemini 2019-06-27 16:23 评论0 收藏0
利用PHP实现常用的数据结构之数据结构浅析（小白系列文章二）

摘要：数据结构基本概念拆成数据和结构两个词来看，结构就是经过排列组合后映射到内存的一种关系，你想想化学中的分子结构就明白了，所以数据结构就是数据之间的一种关系，利用这些关系去处理强逻辑问题。该结构的数据元素之间存在着多对多的关系，也称网状结构。数据结构起源与起因起因：因为现实世界问题大多数是复杂的而非简单的数值计算（例如：图像、视频、声音），将数据进行适当的排序、组合将有利...

Yumenokanata 2019-06-28 13:56 评论0 收藏0
利用PHP实现常用的数据结构之二叉树（小白系列文章五）

摘要：回来更新一波，最近刷剑指，才又发现树真是一个大头，二叉树的题目和变化运用好多啊二叉树算法引子很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书回来更新一波，最近刷《剑指offer》，才又发现树真是一个大头，二叉树的题目和变化运用好多啊～ /** * PHP二叉树算法 * Create...

developerworks 2019-06-27 16:27 评论0 收藏0
利用PHP实现常用的数据结构之二叉树（小白系列文章六）

摘要：回来更新一波，最近刷剑指，才又发现树真是一个大头，二叉树的题目和变化运用好多啊二叉树算法引子很多人说二叉树没什么卵用，我觉得是他的工资和公司让他跨不过这个坎还有很多人学了一些树的知识，发现也用不上，我想说的是，读一本书体现不了这本书回来更新一波，最近刷《剑指offer》，才又发现树真是一个大头，二叉树的题目和变化运用好多啊～ /** * PHP二叉树算法 * Create...

Cympros 2019-06-28 13:56 评论0 收藏0
利用PHP实现常用的数据结构之写在前面（小白系列文章一）

摘要：概述本系列文章主要运用以实现常用的数据结构，包括基本结构展现基本结构实现应用场景实现文章总体来说毕竟浅显，适合新手阅读和学习讨论，欢迎指教，其实每一个作者都是期待读者的反馈的。之前都放在文章里，还是有点零散，刚好SF专栏门槛较低，便寻思着把文章重新整理一遍，这里也谢谢SF了。概述本系列文章主要运用PHP以实现常用的数据结构，包括： 1.基本结构展现 2.基本结构实现 3.应用场...

guqiu 2019-06-28 13:56 评论0 收藏0