PHP实现常用排序算法的方法

本文主要介绍了一些常用的排序算法,以及PHP的代码实现等,希望对您能有所帮助。

本文来自于awaimai.com,由火龙果软件Luca编辑推荐。

作为phper,一般接触算法的编程不多。

但基本的排序算法还是应该掌握。

毕竟算法作为程序的核心,算法的好坏决定了程序的质量。

本文将依次介绍一些常用的排序算法,以及PHP实现。

1 快速排序

快速排序是由东尼·霍尔发展的一种排序算法。

在平均状况下,排序 n 个项目要Ο(n log n)次比较。

在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。

事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环可以在大部分的架构上,很有效率地被实现出来。

快速排序采用分治法实现排序,具体步骤:

从数列中挑出一个数作为基准元素。通常选择第一个或最后一个元素。

扫描数列,以基准元素为比较对象,把数列分成两个区。规则是:小的移动到基准元素前面,大的移到后面,相等的前后都可以。分区完成之后,基准元素就处于数列的中间位置。

然后再用同样的方法,递归地排序划分的两部分。

递归的结束条件是数列的大小是0或1,也就是永远都已经被排序好了。

PHP代码实现:

function quickSort($arr)
 {
 $len = count($arr);
 // 先设定结束条件,判断是否需要继续进行
 if($len <= 1) {
 return $arr;
 } 

 // 选择第一个元素作为基准元素
 $pivot = $arr[0]; 

 // 初始化左数组
 $left = $right = array(); 

// 初始化大于基准元素的右数组
 $right = array(); 

 // 遍历除基准元素外的所有元素,按照大小关系放入左右数组内
 for ($i = 1; $i < $len ; $i++) {
 if ($arr[$i] < $pivot) {
 $left[] = $arr[$i];
 } else {
 $right[] = $arr[$i];
 }
 } 

 // 再分别对左右数组进行相同的排序
 $left = quickSort($left);
 $right = quickSort($right); 

 // 合并基准元素和左右数组
 return array_merge($left, array($pivot), $right);
 }

原地排序版本,不需要额外的存储空间:

function partition(&$arr, $leftIndex, $rightIndex)
 {
 $pivot = $arr[($leftIndex + $rightIndex) / 2];
 while ($leftIndex <= $rightIndex) {
 while ($arr[$leftIndex] < $pivot) {
 $leftIndex++;
 }

 while ($arr[$rightIndex] > $pivot) {
 $rightIndex--;
 }

 if ($leftIndex <= $rightIndex) {
 list($arr[$leftIndex], $arr[$rightIndex]) = [$arr[$rightIndex], $arr[$leftIndex]]; 

 $leftIndex++;
 $rightIndex--;
 }
 } 

 return $leftIndex;
 }

function quickSort(&$arr, $leftIndex, $rightIndex)
 {
 if ($leftIndex < $rightIndex) {
 $index = partition($arr, $leftIndex, $rightIndex);

 quickSort($arr, $leftIndex, $index - 1);
 quickSort($arr, $index, $rightIndex);
 }
 } 

2 冒泡排序

冒泡排序是一种简单的排序算法。

算法重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。

走访数列的工作重复地进行,直到没有再需要交换,也就是说该数列已经排序完成。

因为排序过程让较大的数往下沉,较小的往上冒,故而叫冒泡法。

算法步骤:

从第一个元素开始,比较相邻的元素,如果第一个比第二个大,就交换他们两个。

从开始第一对到结尾的最后一对,对每一对相邻元素作同样的工作。比较结束后,最后的元素应该会是最大的数。

对所有的元素重复以上的步骤,除了最后一个。

重复上面的步骤,每次比较的对数会越来越少,直到没有任何一对数字需要比较。

PHP代码实现:

function bubbleSort($arr)
 {
 $len = count($arr);

 for($i = 1; $i < $len; $i++) {
 for($k = 0; $k < $len - $i; $k++) {
 if($arr[$k] > $arr[$k + 1]) {
 $tmp = $arr[$k + 1];
 $arr[$k + 1] = $arr[$k];
 $arr[$k] = $tmp;
 }
 }
 }
 return $arr;
 }

3 插入排序

插入排序是一种简单直观的排序算法。

插入排序的工作原理是:将需要排序的数,与前面已经排好序的数据从后往前进行比较,使其插入到相应的位置。

插入排序在实现上,通常采用in-place排序,即只需用到O(1)的额外空间的排序。

因而,在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

算法步骤:

从第一个元素开始,该元素可以认为已经被排序;

取出下一个元素,在已经排序的元素序列中从后向前扫描;

如果以排序的元素大于新元素,将该元素移到下一位置;

重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;

将新元素插入到该位置中;

重复步骤2。

PHP代码实现:

function insertSort($arr)
 {
 $len = count($arr); 

 for ($i = 1; $i < $len; $i++) {
 $tmp = $arr[$i];
 for ($j = $i - 1; $j >= 0; $j--) {
 if ($tmp < $arr[$j]) {
 $arr[$j + 1] = $arr[$j];
 $arr[$j] = $tmp;
 } else {
 break;
 }
 }
 }

 return $arr;
 }

4 选择排序

选择排序是一种简单直观的排序算法。

算法步骤:

首先,在序列中找到最小元素,存放到排序序列的起始位置;

接着,从剩余未排序元素中继续寻找最小元素,放到已排序序列的末尾。

重复第二步,直到所有元素均排序完毕。

PHP代码实现:

function selectSort($arr)
 {
 $len = count($arr);
 for ($i = 0; $i < $len; $i++) {
 $p = $i;

 for ($j = $i + 1; $j < $len; $j++) {
 if ($arr[$p] > $arr[$j]) {
 $p = $j;
 }
 }

 $tmp = $arr[$p];
 $arr[$p] = $arr[$i];
 $arr[$i] = $tmp;
 }

 return $arr;
 }

5 归并排序

归并排序是建立在归并操作上的一种有效的排序算法。

归并排序将待排序的序列分成若干组,保证每组都有序,然后再进行合并排序,最终使整个序列有序。

该算法是采用分治法的一个非常典型的应用。

算法步骤:

申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;

设定两个指针,最初位置分别为两个已经排序序列的起始位置

比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

重复步骤3直到某一指针达到序列尾

将另一序列剩下的所有元素直接复制到合并序列尾

排序效果:

PHP实现代码:

/**
 * 归并排序
 *
 * @param array $lists
 * @return array
 */
 function merge_sort(array $lists)
 {
 $n = count($lists);
 if ($n <= 1) {
 return $lists;
 }
 $left = merge_sort(array_slice($lists, 0, floor($n / 2)));
 $right = merge_sort(array_slice($lists, floor($n / 2)));
 $lists = merge($left, $right);
 return $lists;
 }
function merge(array $left, array $right)
 {
 $lists = [];
 $i = $j = 0;
 while ($i < count($left) && $j < count($right)) {
 if ($left[$i] < $right[$j]) {
 $lists[] = $left[$i];
 $i++;
 } else {
 $lists[] = $right[$j];
 $j++;
 }
 }
 $lists = array_merge($lists, array_slice($left, $i));
 $lists = array_merge($lists, array_slice($right, $j));
 return $lists;
 }

6 堆排序

堆排序是指利用堆这种数据结构所设计的一种排序算法。

堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

堆排序的平均时间复杂度为Ο(nlogn) 。

算法步骤:

创建一个堆H[0..n-1];

把堆首(最大值)和堆尾互换;

把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置;

重复步骤2,直到堆的尺寸为1。

PHP实现代码:

/**
 * 堆排序
 *
 * @param array $lists
 * @return array
 */
 function heap_sort(array $lists)
 {
 $n = count($lists);
 build_heap($lists);
 while (--$n) {
 $val = $lists[0];
 $lists[0] = $lists[$n];
 $lists[$n] = $val;
 heap_adjust($lists, 0, $n);
 //echo "sort: " . $n . "\t" . implode(', ', $lists) . PHP_EOL;
 }
 return $lists;
 }
function build_heap(array &$lists)
 {
 $n = count($lists) - 1;
 for ($i = floor(($n - 1) / 2); $i >= 0; $i--) {
 heap_adjust($lists, $i, $n + 1);
 //echo "build: " . $i . "\t" . implode(', ', $lists) . PHP_EOL;
 }
 //echo "build ok: " . implode(', ', $lists) . PHP_EOL;
 }

 function heap_adjust(array &$lists, $i, $num)
 {
 if ($i > $num / 2) {
 return;
 }
 $key = $i;
 $leftChild = $i * 2 + 1;
 $rightChild = $i * 2 + 2;

 if ($leftChild < $num && $lists[$leftChild] > $lists[$key]) {
 $key = $leftChild;
 }
 if ($rightChild < $num && $lists[$rightChild] > $lists[$key]) {
 $key = $rightChild;
 }
 if ($key != $i) {
 $val = $lists[$i];
 $lists[$i] = $lists[$key];
 $lists[$key] = $val;
 heap_adjust($lists, $key, $num);
 }
 }

7 希尔排序

希尔排序,也称递减增量排序算法,是插入排序的一种更高效的改进版本。

但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的:

插入排序在对几乎已经排好序的数据操作时, 效率高, 即可以达到线性排序的效率

但插入排序一般来说是低效的, 因为插入排序每次只能将数据移动一位

算法步骤:

先将整个待排序的记录序列分割成为若干子序列,分别进行直接插入排序

待整个序列中的记录“基本有序”时,再对全体记录进行依次直接插入排序。

PHP实现代码:

/**
 * 希尔排序 标准
 *
 * @param array $lists
 * @return array
 */
 function shell_sort(array $lists)
 {
 $n = count($lists);
 $step = 2;
 $gap = intval($n / $step);
 while ($gap > 0) {
 for ($gi = 0; $gi < $gap; $gi++) {
 for ($i = $gi; $i < $n; $i += $gap) {
 $key = $lists[$i];
 for ($j = $i - $gap; $j >= 0 && $lists[$j] > $key; $j -= $gap) {
 $lists[$j + $gap] = $lists[$j];
 $lists[$j] = $key;
 }
 }
 }
 $gap = intval($gap / $step);
 }
 return $lists;
 }

8 基数排序

基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。

由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于整数。

说基数排序之前,我们简单介绍桶排序:

桶排序是将阵列分到有限数量的桶子里。

每个桶子再个别排序,有可能再使用别的排序算法,或是以递回方式继续使用桶排序进行排序。

桶排序是鸽巢排序的一种归纳结果。

当要被排序的阵列内的数值是均匀分配的时候,桶排序使用线性时间O(n)。

但桶排序并不是 比较排序,他不受到 O(n log n) 下限的影响。

简单来说,就是把数据分组,放在一个个的桶中,然后对每个桶里面的在进行排序。

例如,要对大小为[1..1000]范围内的n个整数A[1..n]排序

首先,可以把桶设为大小为10的范围,具体而言,设集合B[1]存储[1..10]的整数,集合B[2]存储 (10..20]的整数,……集合B[i]存储( (i-1)*10, i*10]的整数,i = 1,2,..100。总共有 100个桶。

然后,对A[1..n]从头到尾扫描一遍,把每个A[i]放入对应的桶B[j]中。 再对这100个桶中每个桶里的数字排序,这时可用冒泡,选择,乃至快排,一般来说任 何排序法都可以。

最后,依次输出每个桶里面的数字,且每个桶中的数字从小到大输出,这 样就得到所有数字排好序的一个序列了。

假设有n个数字,有m个桶,如果数字是平均分布的,则每个桶里面平均有n/m个数字。

如果对每个桶中的数字采用快速排序,那么整个算法的复杂度是

O(n + m * n/m*log(n/m)) = O(n + nlogn – nlogm)

从上式看出,当m接近n的时候,桶排序复杂度接近O(n)

当然,以上复杂度的计算是基于输入的n个数字是平均分布这个假设的。这个假设是很强的 ,实际应用中效果并没有这么好。如果所有的数字都落在同一个桶中,那就退化成一般的排序了。

前面说的几大排序算法 ,大部分时间复杂度都是O(n2),也有部分排序算法时间复杂度是O(nlogn)。而桶式排序却能实现O(n)的时间复杂度。但桶排序的缺点是:

1)首先是空间复杂度比较高,需要的额外开销大。排序有两个数组的空间开销,一个存放待排序数组,一个就是所谓的桶,比如待排序值是从0到m-1,那就需要m个桶,这个桶数组就要至少m个空间。

2)其次待排序的元素都要在一定的范围内等等。

/**
 * 基数排序
 *
 * @param array $lists
 * @return array
 */
 function radix_sort(array $lists)
 {
 $radix = 10;
 $max = max($lists);
 $k = ceil(log($max, $radix));
 if ($max == pow($radix, $k)) {
 $k++;
 }
 for ($i = 1; $i <= $k; $i++) {
 $newLists = array_fill(0, $radix, []);
 for ($j = 0; $j < count($lists); $j++) {
 $key = $lists[$j] / pow($radix, $i - 1) % $radix;
 $newLists[$key][] = $lists[$j];
 }
 $lists = [];
 for ($j = 0; $j < $radix; $j++) {
 $lists = array_merge($lists, $newLists[$j]);
 }
 }
 return $lists;
 }

9 总结

各种排序的稳定性,时间复杂度、空间复杂度、稳定性总结如下图:

关于时间复杂度:

(1)平方阶(O(n2))排序

各类简单排序:直接插入、直接选择和冒泡排序;

(2)线性对数阶(O(nlog2n))排序

快速排序、堆排序和归并排序;

(3)O(n1+§))排序,§是介于0和1之间的常数。

希尔排序

(4)线性阶(O(n))排序

基数排序,此外还有桶、箱排序。

关于稳定性:

稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序

不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

总结

以上所述是小编给大家介绍的PHP实现常用排序算法,希望对大家有所帮助!

(0)

相关推荐

  • PHP排序算法之冒泡排序(Bubble Sort)实现方法详解

    本文实例讲述了PHP排序算法之冒泡排序(Bubble Sort)实现方法.分享给大家供大家参考,具体如下: 基本思想: 冒泡排序是一种交换排序,它的基本思想是:两两比较相邻记录的关键字,如果反序则交换,直到没有反序的记录为止. 最简单排序实现: 我们先来看看在没有学习各种排序方法前经常使用的排序方法(至少我是这样....): //这里使用了类型提示(type hint) array,不熟悉或者不习惯的同学大可去掉,不影响运算结果 function MySort(array &$arr){ $le

  • 又一个PHP实现的冒泡排序算法分享

    经典的冒泡排序法一直是许多程序沿用的其中一种排序法,话说冒泡排序法在效率上比PHP系统函数sort更高效.本章不讨论性能,所以就不拿它来跟系统性能做对比了. 冒泡排序大概的意思是依次比较相邻的两个数,然后根据大小做出排序,直至最后两位数.由于在排序过程中总是小数往前放,大数往后放,相当于气泡往上升,所以称作冒泡排序.但其实在实际过程中也可以根据自己需要反过来用,大树往前放,小数往后放. <?php /** * PHP中的冒泡排序法使用 */ // 预先声明一个数组 $arr = array (1

  • PHP冒泡排序算法代码详细解读

    复制代码 代码如下: <?php $arr = array(345,4,17,6,52,16,58,69,32,8,234); $n = count($arr); for($i=1;$i<$n;$i++){ //其中的为什么$n-1是因为数组是从0开始计算的 //接下来是第一次内循环 for($j=$n-1;$j>=$i;$j--) { //如果$arr[10]<$arr[9]; //temp = $arr[9]; if($arr[$j]<$arr[$j-1]){ //$te

  • PHP排序算法之直接插入排序(Straight Insertion Sort)实例分析

    本文实例讲述了PHP排序算法之直接插入排序(Straight Insertion Sort).分享给大家供大家参考,具体如下: 算法引入: 在这里我们依然使用<大话数据结构>里面的一个例子: 扑克牌是我们几乎每个人都玩过的游戏.平时我们开始的时候一般都是一个人发牌,其他人都是一边摸牌,一边理牌,假如你摸上的第一张牌是 5,第二张牌是 3,自然而然的我们把 3 插到 5 的前面:第三张牌是 4,查到 3 和 5 的中间:第四张牌是 6,放到 5 的后面:第五张牌是 2,插到 3 的前面:--.最

  • PHP 快速排序算法详解

    概念 这里借用百度百科的一张图来,非常形象: 快速排序算法是对冒泡算法的一个优化.他的思想是先对数组进行分割, 把大的元素数值放到一个临时数组里,把小的元素数值放到另一个临时数组里(这个分割的点可以是数组中的任意一个元素值,一般用第一个元素,即$array[0]),然后继续把这两个临时数组重复上面拆分,最后把小的数组元素和大的数组元素合并起来.这里用到了递归的思想. PHP实现 复制代码 代码如下: /*     快速排序 */ function quickSort($array) {    

  • PHP简单选择排序算法实例

    简单的选择排序算法:通过n-i次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换 复制代码 代码如下: <?php     class Sort{         /**          * 简单的选择排序          *          * @param unknown_type $arr          */         public function selectSort(&$arr) {            

  • PHP 冒泡排序 二分查找 顺序查找 二维数组排序算法函数的详解

    数据结构很重要,算法+数据结构+文档=程序使用PHP描述冒泡排序算法,对象可以是一个数组 复制代码 代码如下: //冒泡排序(数组排序)function bubble_sort($array) {$count = count($array);if ($count <= 0)return false;for($i=0; $i<$count; $i++){for($j=$count-1; $j>$i; $j–){if ($array[$j] < $array[$j-1]){$tmp =

  • PHP 各种排序算法实现代码

    复制代码 代码如下: <?php // 功能: PHP实现各种排序算法 // Author: windlike // Datetime: 2007-06-09 // 冒泡排序 function BubbleSort($arr){ $num = count($arr); for($i=1;$i<$num;$i++){ for($j=$num-1;$j>=$i;$j--){ if($arr[$j]<$arr[$j-1]){ $iTemp = $arr[$j-1]; $arr[$j-1]

  • PHP实现常用排序算法的方法

    本文主要介绍了一些常用的排序算法,以及PHP的代码实现等,希望对您能有所帮助. 本文来自于awaimai.com,由火龙果软件Luca编辑推荐. 作为phper,一般接触算法的编程不多. 但基本的排序算法还是应该掌握. 毕竟算法作为程序的核心,算法的好坏决定了程序的质量. 本文将依次介绍一些常用的排序算法,以及PHP实现. 1 快速排序 快速排序是由东尼·霍尔发展的一种排序算法. 在平均状况下,排序 n 个项目要Ο(n log n)次比较. 在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见

  • Java常用排序算法及性能测试集合

    现在再回过头理解,结合自己的体会, 选用最佳的方式描述这些算法,以方便理解它们的工作原理和程序设计技巧.本文适合做java面试准备的材料阅读. 先附上一个测试报告: Array length: 20000bubbleSort : 766 msbubbleSortAdvanced : 662 msbubbleSortAdvanced2 : 647 msselectSort : 252 msinsertSort : 218 msinsertSortAdvanced : 127 msinsertSor

  • PHP常用排序算法实例小结【基本排序,冒泡排序,快速排序,插入排序】

    php三种基础算法:冒泡,插入和快速排序法 $array = array(2,3,5,6,9,8,1); //冒泡排序思想,前后元素比较 function sort_bulldle($array){ $num = count($array); for($i=0; $i<$num; $i++){ $tmp = $array[$i]; for ($j=$i-1; $j>=0; $j--) { if ($tmp < $array[$j]) { $arr[$j+1] = $arr[$j]; $a

  • 视觉直观感受若干常用排序算法

    直观感受几种常用排序算法,具体内容如下 1 快速排序 介绍: 快速排序是由东尼·霍尔所发展的一种排序算法.在平均状况下,排序 n 个项目要Ο(n log n)次比较.在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见.事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来,且在大部分真实世界的数据,可以决定设计的选择,减少所需时间的二次方项之可能性. 步骤: 从数列中挑出一个元素,称为 "基准"

  • php实现希尔排序算法的方法分析

    本文实例讲述了php实现希尔排序算法的方法.分享给大家供大家参考,具体如下: 虽然现在各种程序语言都有其各自强大的排序库函数,但是这些底层实现也都是利用这些基础或高级的排序算法. 理解这些复杂的排序算法还是很有意思的,体会这些排序算法的精妙~ 希尔排序(shell sort):希尔排序是基于插入排序的,区别在于插入排序是相邻的一个个比较(类似于希尔中h=1的情形),而希尔排序是距离h的比较和替换. 希尔排序中一个常数因子n,原数组被分成各个小组,每个小组由h个元素组成,很可能会有多余的元素.当然

  • Java数组常用排序算法实例小结

    本文实例讲述了Java数组常用排序算法.分享给大家供大家参考,具体如下: 1.冒泡排序法 SortArray_01.java public class SortArray_01 { public static void main(String args[]) { int[] array = { 14, 5, 86, 4, 12, 3, 21, 13, 11, 2, 55, 66, 22 }; // 创建一个初始化的一维数组array System.out.println("未排序的数组:&quo

  • 10个python3常用排序算法详细说明与实例(快速排序,冒泡排序,桶排序,基数排序,堆排序,希尔排序,归并排序,计数排序)

    我简单的绘制了一下排序算法的分类,蓝色字体的排序算法是我们用python3实现的,也是比较常用的排序算法. Python3常用排序算法 1.Python3冒泡排序--交换类排序 冒泡排序(Bubble Sort)也是一种简单直观的排序算法. 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来. 走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成.这个算法的名字由来是因为越小的元素会经由交换慢慢"浮"到数列的顶端. 作为最简单的排序算法

  • c语言实现的几种常用排序算法

    概述 最近重新回顾了一下数据结构和算法的一些基本知识,对几种排序算法有了更多的理解,也趁此机会通过博客做一个总结. 1.选择排序-简单选择排序 选择排序是最简单的一种基于O(n2)时间复杂度的排序算法,基本思想是从i=0位置开始到i=n-1每次通过内循环找出i位置到n-1位置的最小(大)值. 算法实现: void selectSort(int arr[], int n) { int i, j , minValue, tmp; for(i = 0; i < n-1; i++) { minValue

  • C/C++ 常用排序算法整理汇总分享

    (伪)冒泡排序算法: 相邻的两个元素之间,如果反序则交换数值,直到没有反序的记录为止. #include <stdio.h> void BubbleSort(int Array[], int ArraySize) { int x, y, temporary; for (x = 0; x < ArraySize - 1; x++) { for (y = x + 1; y < ArraySize; y++) { if (Array[x] > Array[y]) { tempora

  • js实现常用排序算法

    本文为大家分享了js实现常用排序算法,具体内容如下 1.冒泡排序 var bubbleSort = function (arr) { var flag = true; var len = arr.length; for (var i = 0; i < len - 1; i++) { flag = true; for (var j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j + 1]) { var temp = arr[j+1]; arr

随机推荐