PHP 排序算法之希尔排序【php教程】

类别：PHP教程 / 日期：2019-12-10 / 浏览：194 / 评论：0

希尔排序之交流排序

● 问题引入：

在插进去排序中，假如数组元素的分列状况比较乐观，那末插进去的次数就比较少，那末效力就很高了，但是许多时刻，数据就是那末的不敬人意，比方以下的一个待 \

排序的数组：[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 排序算法之希尔排序的细致内容，更多请关注ki4网别的相干文章！

打赏

感谢您的赞助~

打开支付宝扫一扫，即可进行扫码打赏哦~

版权声明 : 本文未使用任何知识共享协议授权，您可以任何形式自由转载或使用。

 可能感兴趣的文章

案例分析PHP Web表单生成器_php教程
案例分析PHP Web表单生成器_php教程

php session 会话（专题）_php教程php session 专题包含PHP Session概念、基本函数使用方法、PHP Session使用案例、PHP Session视频教程以及相关精选...

详解之php反序列化_php教程
详解之php反序列化_php教程

案例分析PHP Web表单生成器_php教程这篇文章主要介绍了PHP Web表单生成器，结合具体案例形式分析了PHP Web表单生成器基本功能需求、实现方法与操作注意事项,需要的朋友可以参考下。 1...

学习PHP实现SMTP邮件的发送_php教程
学习PHP实现SMTP邮件的发送_php教程

用 Composer 开源组件构建自己的 PHP 框架_php教程为什么要构建自己的 PHP 框架？ 现在的 PHP 框架很多，当然不止 PHP ，即使是其他编程语言也有很多框架，这篇文章讲 PHP...

您好，欢迎到访网站！
  查看权限

标签列表