● 成绩引入:
正在拔出排序中,假如数组元素的陈列状况比拟悲观,那末拔出的次数就比拟少,那末效率就很高了,可是不少时分,数据就是那末的没有敬人意,比方以下的一个待 \
排序的数组:[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 php开发教程 php开发资料 php开发自学
抱歉,评论功能暂时关闭!