PHP数组排序算法实现(14种)

aisuhua 发布于2019-06-27 13:54 / 2367人阅读

摘要：本文将介绍快速排序计数排序梳排序堆排序归并排序希尔排序选择排序插入排序地精排序联合冒泡排序鸡尾酒排序冒泡排序奇偶排序使用标志的冒泡排序种排序算法的实现。是一种不稳定的排序算法。

本文将介绍快速排序、计数排序、梳排序、堆排序、归并排序、希尔排序、选择排序、插入排序、地精排序、联合冒泡排序、鸡尾酒排序、冒泡排序、奇偶排序、使用标志的冒泡排序14种排序算法的实现。本文是由于阅读了文章《测试评估：14种排序算法和PHP数组》，才有想法学习、实现并总结这些算法，特此分享，陆续补充。

快速排序

1、思想：主要采用了递归和分治的思想。选择标尺后，进行遍历数组，将大于标尺的放到一个数组，将小于标尺的放置到一个数组。再递归调用本函数并记录结果。

2、实现

function quickSort($arr) {
        //先判断是否需要继续进行
        $length = count($arr);
        if($length <= 1) {return $arr;}

        //选择一个标尺,通常选择第一个元素
        $base_num = $arr[0];

        //初始化
        $left = array();//小于标尺的
        $right = array();//大于标尺的

        for($i=1;$i<$length;$i++) {
            if($base_num > $arr[$i]) {
                $left[] = $arr[$i];
            }else {
                $right[] = $arr[$i];
            }
        }

        //递归调用并记录
        $left = $this->quickSort($left);
        $right = $this->quickSort($right);

        //合并
        return array_merge($left,array($base_num), $right);

3、输入$arr = array(12, 100, 3, 20, 11,50);

4、输出

array:6 [▼
  0 => 3
  1 => 11
  2 => 12
  3 => 20
  4 => 50
  5 => 100
]

计数排序

1、此算法，是一种稳定的线性时间排序算法。其基本思想是，用待排序的数作为计数数组的下标，统计每个数字的个数。然后依次输出即可得到有序序列。但是理解比较难，本人还没理解通透，但是总结了几个步骤：

找出数组$arr中最大的数$max

初始化用来计数的数组$count_arr，数组大小为$max

对于计数数组$count_arr键值等于$arr[$i]的值加1

计数数组$count_arr相邻的两个值相加

键值翻转得到数组$over_turn

loop$over_turn，按照顺序push到最终的数组$result

2、实现

function countingSort($arr) {

        $length = count($arr);
        if($length <= 1) return $arr;

        $size = count($arr);
        $max = $arr[0];

        //找出数组中最大的数
        for($i=1;$i<$size;$i++) {
            if($max < $arr[$i]) $max = $arr[$i];
        }

        //初始化用来计数的数组
        for ($i=0;$i<=$max;$i++) {
            $count_arr[$i] = 0;
        }

        //对计数数组中键值等于$arr[$i]的加1
        for($i=0;$i<$size;$i++) {
            $count_arr[$arr[$i]]++;
        }

        //相邻的两个值相加
        for($i=1;$i<=$max;$i++) {
            $count_arr[$i] = $count_arr[$i-1] + $count_arr[$i];
        }

        //键与值翻转
        for ($i=$size-1;$i>=0;$i--) {
            $over_turn[$count_arr[$arr[$i]]] = $arr[$i];
            $count_arr[$arr[$i]]--; // 前一个数找到位置后，那么和它值相同的数位置往前一步
        }

        //按照顺序排列
        $result = array();
        for ($i=1;$i<=$size;$i++) {
            array_push($result,$over_turn[$i]);
        }

        return $result;
    }

3、输入$arr = array(8,6,1,3,4)

4、输出

array:5 [▼
  0 => 1
  1 => 3
  2 => 4
  3 => 6
  4 => 8
]

梳排序

1、思想：梳排序同样基于冒泡排序，梳排序比较的是固定距离处的数的比较和交换,类似希尔那样。是一种不稳定的排序算法。

2、实现

function combSort($arr) {
    $length = count($arr);
    $step = (int)floor($length/1.3);
    while($step >= 1) {
        for($i=0;$i<$length;$i++) {

            if($i+$step<$length && $arr[$i]>$arr[$i+$step]) {
                $temp = $arr[$i];
                $arr[$i] = $arr[$i+$step];
                $arr[$i+$step] = $temp;
            }

            if($i+$step>$length) {
                break;
            }

        }
        $step = (int)floor($step/1.3);
    }
        return $arr;
    }

3、输入$arr = array(8,4,3,7,6,5,2,1)

4、输出

array:8 [▼
  0 => 1
  1 => 2
  2 => 3
  3 => 4
  4 => 5
  5 => 6
  6 => 7
  7 => 8
]

待补充

参考文章
测试评估：14种排序算法和PHP数组：http://blog.jobbole.com/68774/

GPU云服务器云服务器 java三种排序算法字符串排序数组排序算法数组排序算法c语言 php 四种排序

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

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

PHP 计数排序

摘要：计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。计数排序不是基于比较的排序算法，其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。算法描述找出待排序的数组中最大和最小的元素；...

孙吉亮 2019-07-01 10:25 评论0 收藏0
PHP面试：常见查找算法一篇说透

摘要：我们现在来看二分搜索算法的两种变形插值搜索和指数搜索。插值搜索是对二分搜索算法的改进，插值搜索可以基于搜索的值选择到达不同的位置。预警在本篇文章中，将为各位老铁介绍不同的搜索算法以及它们的复杂度。因为力求通俗易懂，所以篇幅可能较长，大伙可以先Mark下来，每天抽时间看一点理解一点。本文配套的Github Repo，欢迎各位老铁star，会一直更新的。开篇和排序类似，搜索或者叫做...

付永刚 2019-07-01 10:47 评论0 收藏0
php 经典排序算法（解析）

摘要：介绍三种排序算法快速排序选择排序冒泡排序选择排序选择排序是一种简单直观的排序算法。介绍三种排序算法快速排序选择排序冒泡排序选择排序选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3...

FuisonDesign 2019-06-28 14:08 评论0 收藏0
[讨论]php 排序系列的函数内部的C实现是用了哪种排序算法？

摘要：在算法中，比快速排序还快的，无疑是基数排序，粗略看了一下算法，可能是基础排序中的桶排序。桶排序是稳定的桶排序是常见排序里最快的一种，比快排还要快大多数情况下桶排序非常快，但是同时也非常耗空间以空间换时间 ext/standard/php_array.h https://github.com/php/php-src/blob/master/ext/standard/php_array....

chanthuang 2019-06-27 10:27 评论0 收藏0
JavaScript 数据结构与算法之美 - 归并排序、快速排序、希尔排序、堆排序

摘要：之所以把归并排序快速排序希尔排序堆排序放在一起比较，是因为它们的平均时间复杂度都为。归并排序是一种稳定的排序方法。因此，快速排序并不稳定。希尔排序思想先将整个待排序的记录序列分割成为若干子序列。 showImg(https://segmentfault.com/img/bVbvpYZ?w=900&h=250); 1. 前言算法为王。想学好前端，先练好内功，只有内功深厚者，前端之路才...

haitiancoder 2019-08-26 10:20 评论0 收藏0