dmz社区

 找回密码
 立即注册

QQ登录

只需一步,快速开始

查看: 2730|回复: 12

[功能实现] php语言实现的7种基本的排序方法

[复制链接]
  • TA的每日心情

    2024-11-19 20:46
  • 签到天数: 244 天

    [LV.8]以坛为家I

    4434

    主题

    1459

    帖子

    1万

    积分

    会|员

    Rank: 9Rank: 9Rank: 9

    积分
    10734
    发表于 2019-4-23 23:51:48 | 显示全部楼层 |阅读模式

    本站资源全部免费,回复即可查看下载地址!

    您需要 登录 才可以下载或查看,没有帐号?立即注册

    x
    今天总结了一下常用的7种排序方法,并用php语言实现。
    直接插入排序
    [PHP] 纯文本查看 复制代码
    /*
     *    直接插入排序,插入排序的思想是:当前插入位置之前的元素有序,
     *    若插入当前位置的元素比有序元素最后一个元素大,则什么也不做,
     *    否则在有序序列中找到插入的位置,并插入
     */
    function insertSort($arr) {
        $len = count($arr);    
        for($i = 1; $i < $len; $i++) {
            if($arr[$i-1] > $arr[i]) {
                for($j = $i - 1;$j >= 0; $j-- ) {
                    $tmp = $arr[$j+1];
                    if($tmp < $arr[$j]) {
                        $arr[$j+1] = $arr[$j];
                        $arr[$j] = $tmp;
                    }else{
                        break;
                    }                    
                }    
            }
        }    
        return $arr;
    }

    冒泡排序
    [PHP] 纯文本查看 复制代码
    /*
        冒泡排序,冒泡排序思想:进行 n-1 趟冒泡排序, 每趟两两比较调整最大值到数组(子数组)末尾
    */
    function bubbleSort($arr) {
        $len = count($arr);
        for($i = 1; $i < $len; $i++) {
            for($j = 0; $j < $len-$i; $j++) {
                if($arr[$j] > $arr[$j+1]) {
                    $tmp = $arr[$j+1];
                    $arr[$j+1] = $arr[$j];
                    $arr[$j] = $tmp;
                }
            }
        }
        return $arr;
    }

    简单选择排序
    [PHP] 纯文本查看 复制代码
    /*
        简单选择排序, 简单排序思想:从数组第一个元素开始依次确定从小到大的元素
    */
    function selectSort($arr) {
        $len = count($arr);
        for($i = 0; $i < $len; $i++) {
            $k = $i;
            for($j = $i+1; $j < $len; $j++) {
                if($arr[$k] > $arr[$j]) {
                    $k = $j;
                }
            }
            if($k != $i) {
                $tmp = $arr[$i];
                $arr[$i] = $arr[$k];
                $arr[$k] = $tmp;
            }
        }
        return $arr;
    }

    希尔排序
    [PHP] 纯文本查看 复制代码
    /*
        希尔排序,希尔排序原理:将数组按指定步长分隔成若干子序列,然后分别对子序列进行排序(在这是直接)
    */
    function shellSort($arr) {
        $len = count($arr);
        $k = floor($len/2);
        while($k > 0) {
            for($i = 0; $i < $k; $i++) {
                for($j = $i; $j < $len, ($j + $k) < $len; $j = $j + $k) {
                    if($arr[$j] > $arr[$j+$k]) {
                        $tmp = $arr[$j+$k];
                        $arr[$j+$k] = $arr[$j];
                        $arr[$j] = $tmp;
                    }
                }
            }
            $k = floor($k/2);
        }
        return $arr;
    }

    快速排序
    [PHP] 纯文本查看 复制代码
    /*
     *    快速排序,快排思想:通过一趟排序将待排的记录分为两个独立的部分,其中一部分的记录的关键字均不大于
     *    另一部分记录的关键字,然后再分别对这两部分记录继续进行快速排序,以达到整个序列有序,具体做法需要
     *    每趟排序设置一个标准关键字和分别指向头一个记录的关键字和最后一个记录的关键字的指针。
     *    quickSort($arr, 0, count($arr) -1);
     */
    function quickSort(&$arr,$low,$high) {
        if($low < $high) {
            $i = $low;
            $j = $high;
            $primary = $arr[$low];
            while($i < $j) {
                while($i < $j && $arr[$j] >= $primary) {
                    $j--;
                }
                if($i < $j) {
                    $arr[$i++] = $arr[$j];
                }
                while($i < $j && $arr[$i] <= $primary) {
                    $i++;
                }
                if($i < $j) {
                    $arr[$j--] = $arr[$i];
                }
            }
            $arr[$i] = $primary;
            quickSort($arr, $low, $i-1);
            quickSort($arr, $i+1, $high);
        }
    }

    堆排序
    [PHP] 纯文本查看 复制代码
    /*
        堆排序
    */
    
    // 调整子堆的为大根堆的过程,$s为子堆的根的位置,$m为堆最后一个元素位置
    function heapAdjust(&$arr, $s, $m) {
        $tmp = $arr[$s];
        // 在调整为大根堆的过程中可能会影响左子堆或右子堆
        // for循环的作用是要保证子堆也是大根堆
        for($j = 2*$s + 1; $j <= $m; $j = 2*$j + 1) {
            // 找到根节点的左右孩子中的最大者,然后用这个最大者与根节点比较,
            // 若大则进行调整,否则符合大根堆的 特点跳出循环    
            if($j < $m && $arr[$j] < $arr[$j+1]) {
                $j++;
            }
            if($tmp >= $arr[$j] ) {
                break;
            }
            $arr[$s] = $arr[$j];
            $s = $j;
        }
        $arr[$s] = $tmp;
    }
    // 堆排序
    function heapSort($arr) {
        $len = count($arr);
        // 依次从子堆开始调整堆为大根堆
        for($i = floor($len/2-1); $i >= 0; $i--) {
            heapAdjust($arr, $i, $len-1);
        }
        // 依次把根节点调换至最后一个位置,再次调整堆为大根堆,找到次最大值,
        // 依次类推得到一个有序数组
        for($n = $len-1; $n > 0; $n--) {
            $tmp = $arr[$n];
            $arr[$n] = $arr[0];
            $arr[0] = $tmp;
            heapAdjust($arr, 0, $n-1);
        }
        return $arr;
    }

    归并排序
    [PHP] 纯文本查看 复制代码
    /*
        归并排序,这里实现的是两路归并
    */
    // 分别将有序的$arr1[s..m]、$arr2[m+1..n]归并为有序的$arr2[s..n]
    function Merge(&$arr1, &$arr2, $s, $m, $n) {
        for($k = $s,$i = $s, $j = $m+1; $i <= $m && $j <= $n; $k++) {
            if($arr1[$i]<$arr1[$j]) {
                $arr2[$k] = $arr1[$i++];
            }else {
                $arr2[$k] = $arr1[$j++];
            }
        }
        if($i <= $m) {
            for(; $i <= $m; $i++) {
                $arr2[$k++] = $arr1[$i];
            }
        } else if($j <= $n) {
            for(; $j <= $n; $j++) {
                $arr2[$k++] = $arr1[$j];
            }
        }
    }
    
    // 递归形式的两路归并
    function MSort(&$arr1, &$arr2, $s, $t) {
        if($s == $t) {
            $arr2[$s] = $arr1[$s];
        }else {
            $m = floor(($s+$t)/2);
            $tmp_arr = array();
            MSort($arr1, $tmp_arr, $s, $m);
            MSort($arr1, $tmp_arr, $m+1, $t);
            Merge($tmp_arr, $arr2, $s, $m, $t);
        }
    }
    
    // 对一位数组$arr[0..n-1]中的元素进行两路归并
    function mergeSort($arr) {
        $len = count($arr);
        MSort($arr, $arr, 0, $len-1);
        return $arr;
    }



    使用经验
    • 若排序的记录数目n较小时,可以采用直接插入排序和简单选择排序,当记录本身信息量较大时,用简单选择排序方法较好。
    • 若待排序记录按关键字基本有序,适合采用直接插入排序和冒泡排序。
    • 若n值较大时,可以采用快速排序、堆排序和归并排序。另外快速排序被认为是内部排序方法中最好的方法。



    回复

    使用道具 举报

    该用户从未签到

    21

    主题

    7765

    帖子

    881

    积分

    终身会员[A]

    Rank: 7Rank: 7Rank: 7

    积分
    881

    发表于 2019-4-25 10:20:07 | 显示全部楼层
    正需要,支持楼主大人了!
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    5

    主题

    7567

    帖子

    1137

    积分

    技冠群雄

    Rank: 6Rank: 6

    积分
    1137

    发表于 2019-4-27 17:31:31 | 显示全部楼层
    谢谢楼主,共同发展
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    29

    主题

    8020

    帖子

    1015

    积分

    终身会员[A]

    Rank: 7Rank: 7Rank: 7

    积分
    1015

    发表于 2019-5-1 21:57:52 | 显示全部楼层
    正需要,支持楼主大人了!
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    17

    主题

    7860

    帖子

    935

    积分

    终身会员[A]

    Rank: 7Rank: 7Rank: 7

    积分
    935

    发表于 2019-5-2 09:59:04 | 显示全部楼层
    过来看看的
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    28

    主题

    7920

    帖子

    1033

    积分

    终身会员[A]

    Rank: 7Rank: 7Rank: 7

    积分
    1033

    发表于 2019-5-10 13:50:27 | 显示全部楼层
    正需要,支持楼主大人了!
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    4

    主题

    7588

    帖子

    1153

    积分

    技冠群雄

    Rank: 6Rank: 6

    积分
    1153

    发表于 2019-5-13 22:03:52 | 显示全部楼层
    我是来刷分的,嘿嘿
    回复 支持 反对

    使用道具 举报

  • TA的每日心情
    慵懒
    2021-10-21 17:36
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    6

    主题

    3589

    帖子

    205

    积分

    终身会员[A]

    Rank: 7Rank: 7Rank: 7

    积分
    205

    发表于 2019-5-14 00:47:11 | 显示全部楼层
    找到好贴不容易,我顶你了,谢了
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    24

    主题

    7885

    帖子

    962

    积分

    终身会员[A]

    Rank: 7Rank: 7Rank: 7

    积分
    962

    发表于 2019-5-16 08:55:07 | 显示全部楼层
    我是来刷分的,嘿嘿
    回复 支持 反对

    使用道具 举报

    该用户从未签到

    20

    主题

    7880

    帖子

    986

    积分

    终身会员[A]

    Rank: 7Rank: 7Rank: 7

    积分
    986

    发表于 2019-5-27 07:16:46 | 显示全部楼层
    过来看看的
    回复 支持 反对

    使用道具 举报

    您需要登录后才可以回帖 登录 | 立即注册

    本版积分规则

    QQ|Archiver|小黑屋|本站代理|dmz社区

    GMT+8, 2024-12-23 23:41 , Processed in 0.802182 second(s), 42 queries .

    Powered by Discuz! X3.4 Licensed

    Copyright © 2001-2021, Tencent Cloud.

    快速回复 返回顶部 返回列表