最新公告
  • 欢迎您访问爱上源码网,分享精品整站源码,网站模板,游戏源码,APP小程序源码以及视频教程免费下载;服务永无止境!立即加入我们
  • PHP 排序算法之希尔排序

    希尔排序之交换排序

    ● 问题引入:

    在插入排序中,如果数组元素的排列情况比较乐观,那么插入的次数就比较少,那么效率就很高了,可是很多时候,数据就是那么的不敬人意,比如如下的一个待 \

    排序的数组:[2,3,4,5,6,7,1],这个数组,如果使用插入排序,那么就会发生如下的样子:

    1. 第一轮:[2,3,4,5,6,7,7]

    2. 第二轮:[2,3,4,5,6,6,7]

    3. 第三轮:[2,3,4,5,5,6,7]

    4. 第四轮:[2,3,4,4,5,6,7]

    5. 第五轮:[2,3,3,4,5,6,7]

    6. 第六轮:[2,2,3,4,5,6,7]

    7. 第七轮:[1,2,3,4,5,6,7]

    这样的就是最不乐观的情况,很浪费时间,所以,后来就有大神研究了一下,优化优化,就发明了希尔排序。

    希尔排序 (Shell’s Sort) 是插入排序的一种又称 “缩小增量排序”(Diminishing Increment Sort),是直接插入排序算法的一种更高效的改进版本。

    希尔排序是非稳定排序算法。该方法因 D.L.Shell 于 1959 年提出而得名。

    希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,

    整个文件恰被分成一组,算法便终止

    数组实例说明:

    1. 比如有一个待排序的数组 [9,6,1,3,0,5.7,2,8,4]

    2. 上面的数组一共有 10 个元素,它把数组第一次分为 10/2 = 5 组,然后两两比较,大小位置交换:如下:

    <?php
    $arr = [9,6,1,3,0, 5,7,2,8,4];
    $arr[0] > $arr[5] ? '交换位置,小数交换在前,大数交换在后' : '不交换位置';
    $arr[1] > $arr[6] ? '交换位置,小数交换在前,大数交换在后' : '不交换位置';
    $arr[2] > $arr[7] ? '交换位置,小数交换在前,大数交换在后' : '不交换位置';
    $arr[3] > $arr[8] ? '交换位置,小数交换在前,大数交换在后' : '不交换位置';
    $arr[4] > $arr[9] ? '交换位置,小数交换在前,大数交换在后' : '不交换位置';
    for ($i = 5; $i < 10; $i++) {
         for ($j = $i - 5; $j >= 0; $j-=5) {
             if ($data[$j] > $data[$j+5]) {
             $temp = $data[$j];
             $data[$j] = $data[$j+5];
             $data[$j+5] = $temp; 
             } 
         }
     }

    最后第一轮得到的结果就是:[5,6,1,3,0,9,7,2,8,4]

    3. 第二轮又开始比较,第二轮是在之前第一轮的基础上,再次分为 5/2 = 2 组,然后两两交换位置,大小指互换:如下:

    <?php
    $arr = [5,6,1,3,0,9,7,2,8,4];
    $arr[0] > $arr[2];//1,5  [1,6,5,3,0,9,7,2,8,4]
    $arr[2] > $arr[4];//0,5  [1,6,0,3,5,9,7,2,8,4]
    $arr[4] > $arr[6];//5,7  [1,6,0,3,5,9,7,2,8,4]
    $arr[6] > $arr[8];//7,8  [1,6,0,3,5,9,7,2,8,4]
    $arr[1] > $arr[3];//3,6  [1,3,0,6,5,9,7,2,8,4]
    $arr[3] > $arr[5];//6,9  [1,3,0,6,5,9,7,2,8,4]
    $arr[5] > $arr[7];//2,9  [1,3,0,6,5,2,7,9,8,4]
    $arr[7] > $arr[9];//4,9  [1,3,0,6,5,2,7,4,8,9]
    ...
    for ($i = 2; $i < 10; $i++) {
         for ($j = $i - 2; $j >= 0; $j-=2) {
             if ($data[$j] > $data[$j+2]) {
             $temp = $data[$j];
             $data[$j] = $data[$j+2];
             $data[$j+2] = $temp; 
             } 
         }
     }

    最后得到的结果就是:[0,2,1,3,6,4,7,6,8,9]

    4. 最后再次分组比较:2/2 = 1 组。也就是最后,每两个都要比较,然后再次互换位置

    <?php
    $arr = [0,2,1,3,5,4,7,6,8,9];
    $arr[0] > $arr[1];//[1,3,0,6,5,2,7,4,8,9]
    $arr[1] > $arr[2];//[1,0,3,6,5,2,7,4,8,9]
    $arr[2] > $arr[3];//[1,0,3,6,5,2,7,4,8,9]
    $arr[3] > $arr[4];//[1,0,3,5,6,2,7,4,8,9]
    $arr[4] > $arr[5];//[1,0,3,5,2,6,7,4,8,9]
    $arr[5] > $arr[6];//[1,0,3,5,2,6,7,4,8,9]
    $arr[6] > $arr[7];//[1,0,3,5,2,6,4,7,8,9]
    $arr[7] > $arr[8];//[1,0,3,5,2,6,4,7,8,9]
    $arr[8] > $arr[9];//[1,0,3,5,2,6,4,7,8,9]
    ...
    for ($i = 1; $i < 10; $i++) {
         for ($j = $i - 1; $j >= 0; $j-=1) {
             if ($data[$j] > $data[$j+1]) { 
             $temp = $data[$j]; 
             $data[$j] = $data[$j+1];
             $data[$j+1] = $temp;
             }
         }
     }

    最后就得到结果:[0,1,2,3,4,5,6,7,8,9]

    完整代码如下:

    <?php
    class ShellSort
    {
     /*** Notes: 希尔排序之交换法排序
     * User: LiYi\ * Date: 2019/11/12 0012\ * Time: 14:30\ * @param array $data\ * @return array\ */\
     public static function shellSortArray(array $data):array
     {
     if (!is_array($data)) {
     return ['message' => '必须传入数组比较排序'];
     }
     $count = count($data);//得到数组的个数
     //如果数组的个数小于等于1就直接返回
     if ($count <= 1) {return $data;}
     //$gap 是每次减半的分组,直到只可以分为一组结束,在php里面需要注意,两个整数相除,除不尽的情况下,得到的是一个浮点数,不是一个向下
     //取整的的整数,所以在最后判断gap 退出循环的时候,需要判断它 >= 1
     for ($gap = $count / 2; $gap >= 1; $gap /= 2) {
             for ($i = $gap; $i < $count; $i++) {
                 for ($j = $i - $gap; $j >= 0; $j-=$gap) {
                     if ($data[$j] > $data[$j+$gap]) {
                     //这个地方是比较第一个数和它的步长做比较,交换也是一样
                     $temp = $data[$j]; 
                     $data[$j] = $data[$j+$gap];
                     $data[$j+$gap] = $temp;
                     }
                 }
             }
         }
         return $data;
     }
     public static function validate(array $data)
     {
          if (!is_array($data)) {
          return ['message' => '必须传入数组比较排序'];
         }
     $count = count($data);//得到数组的个数
     //如果数组的个数小于等于1就直接返回
     if ($count <= 1){
     return $data;
     }
     return [$data, $count];
     }
     /**\ * Notes: 希尔排序之移位法排序
     * User: LiYi
     * Date: 2019/11/12 0012
     * Time: 14:29
     * @param array $data
     * @return array*/
     public static function ShellSortMoveArray(array $data)
     {
     $count = count($data);//得到数组总数
     for ($gap = $count / 2; $gap > 0; $gap /= 2) {
     //缩小增量,每次减半
     $gap = floor($gap);
     for ($i = $gap; $i < $count; $i++) {
     // $insertIndex = $i;//待插入元素的下表
     $insertValue = $data[$insertIndex];//待插入元素的值
     echo "insertIndex=$insertIndex" . PHP_EOL;
     echo "insertValue=$insertValue" . PHP_EOL;
     if ($data[$insertIndex] < $data[$insertIndex - $gap]) {
     //判断待插入元素和它步长的元素比较,待插入元素小就进入循环
     //判断是否越界了,第一个元素的下标是要大于等于0的,否则退出循环
     //判断后面的元素比前面的元素小,进入循环,否则退出循环
     while ($insertIndex - $gap >= 0 && $insertValue < $data[$insertIndex - $gap]) {
     //把步长前面的大的值向后移动
     $data[$insertIndex] = $data[$insertIndex - $gap];
     $insertIndex -= $gap;//每循环一次就把带插入的坐标减去补偿\
     } //把带插的小值插入到前面
     $data[$insertIndex] = $insertValue;
     }
     }
     }
     return $data;
     }
     public static function testShellOne(array $data)
     {
     $temp = 0;
     $count = count($data);
     for ($i = 5; $i < $count; $i++) {
     for ($j = $i - 5; $j >= 0; $j-=5) {
     if ($data[$j] > $data[$j+5]) {
     $temp = $data[$j];
     $data[$j] = $data[$j+5];
     $data[$j+5] = $temp;
     }
     }
     }
     for ($i = 2; $i < $count; $i++) {
     for ($j = $i - 2; $j >= 0; $j-=2) {
     if ($data[$j] > $data[$j+2]) {
     $temp = $data[$j];
     $data[$j] = $data[$j+2];
     $data[$j+2] = $temp;
      }
      } 
      }
     for ($i = 1; $i < 10; $i++) {
     for ($j = $i - 1; $j >= 0; $j-=1) {
     if ($data[$j] > $data[$j+1]) {
     $temp = $data[$j];
     $data[$j] = $data[$j+1];
     $data[$j+1] = $temp;
     } 
     }
     }
     var_dump($data);
     }
     }
    var_dump(ShellSort::shellSortMoveArray([0 => 9, 1 => 6, 2 => 1, 3 => 3, 4 => 0, 5 => 5, 6 => 7, 7 => 2, 8 => 8, 9 => 4]));
    // $gap = 10 / 2 = 5
    // $insertIndex  = $i = $gap = 5
    // $insertValue = $data[$insertIndex] = $data[5] = 5;
    // $data[$insertIndex] < $data[$insertIndex - $gap] == $data[5] < $data[5-5] = $data[0] ==> 5 < 9
    // while(5 - 5 >= 0 && 5 < 9) {
    //  $data[5] = $data[5-5] = $data[0] = 9
    //  $insertIndex -= 5 = 0;
    //}
    // $data[$insertIndex] = $data[0] = $insertValue = 5
    // $i++ = 6;
    // $insertIndex  = $i =  6
    // $insertValue = $data[$insertIndex] = $data[6] = 7;
    // $data[$insertIndex] < $data[$insertIndex - $gap] == $data[6] < $data[6-5] = $data[1] ==> 7 < 6
    // $i++ = 7;
    // $insertIndex  = $i =  7
    // $insertValue = $data[$insertIndex] = $data[7] = 2;
    // $data[$insertIndex] < $data[$insertIndex - $gap] == $data[7] < $data[7-5] = $data[2] ==> 2 < 1
    // $i++ = 8;
    // $insertIndex  = $i =  8
    // $insertValue = $data[$insertIndex] = $data[8] = 8;
    // $data[$insertIndex] < $data[$insertIndex - $gap] == $data[8] < $data[8-5] = $data[3] ==> 8 < 3
    // $i++ = 9;
    // $insertIndex  = $i =  9
    // $insertValue = $data[$insertIndex] = $data[9] = 4;
    // $data[$insertIndex] < $data[$insertIndex - $gap] == $data[9] < $data[9-5] = $data[4] ==> 4 < 0

    以上就是PHP 排序算法之希尔排序的详细内容,更多请关注爱上源码网其它相关文章!

  • 微信
  • 分享
  • 相关标签:PHP
  • 本文转载于:learnku,如有侵犯,请联系916990011@qq.com删除
    • 上一篇:PHP实现微信支付(jsapi支付)流程的方法
    • 下一篇:PHP 排序算法之插入排序

    相关文章

    相关视频

    • php怎么获得昨天0点的时间戳
    • PHP怎么实现微信申请退款
    • PHP实现微信支付(jsapi支付)流程的方法
    • ThinkPHP中实现微信支付(jsapi支付)流…
    • PHP 排序算法之希尔排序
    • PHP使用api操作memcache
    • Thinkphp5集成memcache

    本文有爱上源码下载完入驻作者发布,如果对您版权造成侵害,可以联系本站站长管理进行维权删除,本站收到维权24小时内进行处理,谢谢您关注23ym.cn!
    本站分享大量程序员技术文章以及对编程开发的初级入门教程,包括图文讲解笔记和高清视频下载~

    重要声明:
    1.本站视频教程,软件及网站源码版权均属于原作者所有,您必须在下载后的24个小时之内,从您的电脑中删除!非法商业用途,后果自负!
    2.本站不保证所提供下载资源的安全性和完整性,仅供下载学习之用!如链接失效或资源含外站广告,请联系客服处理!给予奖励!
    3.本站所有资源来源于用户上传和网络,因此不包含技术服务请大家谅解!本站提供有偿服务!如有侵权请联系在线客服!
    4.如您手中有优质资源或教程,可以自助投稿发布,成功分享后有奖励和额外收入!
    5.如您需要正版微擎模块可联系本站客服,我们有价值30w+商业微擎应用出售微擎坑位和招收代理!
    6.400电话/软著/ICP,EDI许可证/商标特价办理中!
    爱上源码下载网 » PHP 排序算法之希尔排序

    常见问题FAQ

    从网站下载的源码都有安装教程么?不会安装怎么办?
    本站发布的网站源码和模板资源大部分在压缩包内都有教程,如您不会安装可以联系本站在线技术进行付费安装。
    爱上源码的所有源码都是亲测能正常运行的么?
    本站目前拥有资源10w+,包含整站源码,网站模板,游戏源码,小程序源码,视频教程,破解软件等,每天也在测试更新;因时间和精力有限我们无法对资源进行一一测试,只能保证所分享资源内容无误,希望理解。
    我手中的优质资源可以在你这换钱或者VIP么?
    爱上源码支持投稿,欢迎发布您手中的优质资源进行售卖;本站VIP支持免费获取,目前邀请10人注册爱上源码即可免费获取VIP。
    爱上源码除了资源分享还有其他业务没?
    【价值30W+微擎模块出售正版商业微擎坑位及招收代理,详情咨询本站客服!】我们团队目前运营并推广几套商业化saas智能小程序系统能满足大部分小程序开发需求,并由SaaS和独立部署版商城小程序系统;另外销售400电话,各种ICP/EDI资质证书办理,软著和商标注册服务等。

    发表评论

    • 30会员总数(位)
    • 35644资源总数(个)
    • 0本周发布(个)
    • 0 今日发布(个)
    • 616稳定运行(天)

    提供最优质的资源集合

    开通VIP 源码下载