站长资讯网
最全最丰富的资讯网站

PHP 排序算法原理及总结

冒泡排序原理

原理描述:

一次比较俩个相邻的元素,大的元素后移,小的元素前移(交换位置)。直到找出最大的元素。就像是气泡一样,大的向下沉,小的向上冒。

流程:

有一个无序数组 $arr = [8, 9, 3, 6, 1, 4]

第一次外循环 :找出最大值 9,要俩俩相比,比 5 次。 8 9 3 6 1 4 第一次, 8 跟 9 比,9 大,所以没有交换位置。 8 3 9 6 1 4 第二次, 9 跟 3 比, 9 大,交换位置。 8 3 6 9 1 4 第三次, 9 跟 6 比, 9 大,交换位置。 8 3 6 1 9 4 第四次, 9 跟 1 比, 9 大,交换位置。 8 3 6 1 4 9 第五次, 9 跟 4 比, 9 大,交换位置。 第二次外循环:找出第二大值 8,要俩俩相比,比 4 次。因为上一步已经找到最大值了。 3 8 6 1 4 9 第一次,8 跟 3 比,8 大, 交换位置。 3 6 8 1 4 9 第二次,8 跟 6 比,8 大, 交换位置。 3 6 1 8 4 9 第三次,8 跟 1 比,8 大, 交换位置。 3 6 1 4 8 9 第四次,8 跟 4 比,8 大, 交换位置。 第三次外循环:找出第三大的值 6,要俩俩相比,比三次。 3 6 1 4 8 9 第一次,3 跟 6 比,6 大,位置没有变化。 3 1 6 4 8 9 第二次,6 跟 1 比,6 大,交换位置。 3 1 4 6 8 9 第三次,6 跟 4 比,6 大,交换位置。 第四次外循环:找出第四大的值 4,要俩俩相比,比 2 次。 1 3 4 6 8 9 第一次, 3 跟 1 比, 3 大,交换位置。 1 3 4 6 8 9 第二次, 3 跟 4 比, 4 大,位置不变。 第五次外循环:找出第五大的值 3, 比一次就够了。 1 3 4 6 8 9 比一次。1 跟 3 比,3 大,位置没有变化。

总结:

1. 外层循环要元素数 – 1次。负责找出最大值。

2. 内层循环逐层递减一次。负责俩俩相比较,交换元素位置。

代码:

<?php         function bubbleSort($arr)          {             $len = count($arr);//获取元素个数             for ($i = 0; $i < $len - 1; $i ++) {//找出最大值                 $flag = 0;//做一个标记                 for($j = 0; $j < $len - 1 - $i; $j++) {//俩俩相比较,交换位置                     if ($arr[$j] > $arr[$j + 1]) {                         //$temp = $arr[$j];//存当前元素                         //$arr[$j] = $arr[$j + 1];//把当前元素的值换成下一个元素的值                         //$arr[$j + 1] = $temp;//把下一个元素的值换成上一个元素的值。                         list($arr[$j], $arr[$j + 1]) = [$arr[$j + 1], $arr[$j]];//来自lovecn的评论,有时候思维有些固化。                         $flag = 1;//交换位置就记录。                     }                 }                 if ($flag == 0) {//没有发生交换位置,说明排序已经完成。可以推出循环。                     break;                 }             }             return $arr;         }

快速排序原理(递归)

原理描述:

从数组中取第一个值作为参照物,比这个值小的放在左边,比这个值大的放在右边,这样就会有俩个新的数组,递归处理俩个数组,然后左边,参照物,右边合并。注意:有递归就要找到递归出口,不然就会一直递归下去。

流程:

用文字叙述流程太麻烦,就从网上找了一个图片,过程很清晰。

PHP 排序算法原理及总结

代码:

    <?php         function quickSort($arr)         {             $len = count($arr);             //递归出口             if($len <= 1) {                 return $arr;             }             $markValue = $arr[0];//参照物。             $left = $right = [];//定义左边和右边。             for($i = 1; $i < $len; $i++) {//从1开始循环,因为第一个元素当作参照物。                 if($arr[$i] > $markValue) {//大于参照物的放在右边。                     $right[] = $arr[$i];                 } else {//小于和等于参照物的元素都放进左边,这样会避免如果数组有重复元素时,会漏掉元素。                     $left[] = $arr[$i];                 }             }             return array_merge(quickSort($left), [$markValue], quickSort($right));         }

插入排序

原理描述:

将要排序的数组分成俩个部分,取数组第一个元素放有序集合中,剩下的放到无序集合中。将需要排序的数,与前面已经排好序的数据从后往前进行比较,直到找到小于或者等于它的数,使其插入到相应的位置。

我的记忆方法:

假设有俩个箱子,第一个箱子是透明并且是空的,要用来装有序元素,第二个箱子是不透明并且是满的,装无序元素。(其实装什么都行,你喜欢的让你容易记住的最好)。

1.第一步:在不透明箱子里随便拿一个元素,直接扔到透明的箱子里
2.第二步:再从不透明的箱子里拿出一个元素,放进透明箱子里前,做比较。如果大就放后面,如果小就放前面。
3.重复第二步,但是我们每次需要比较的次数增加了,因为透明箱子里元素多了,直到找到合适的位置。

流程:

PHP 排序算法原理及总结

<?php     function insertSort($arr)     {         $len = count($arr);         if ($len <= 1) {//一个元素或者没有元素,排序无意义。             return $arr;         }         for($i = 0; $i < $len - 1; $i++) {             for($j = $i + 1; $j > 0; $j--){//每次比较次数增加。因为有序集合元素在增加。                 if ($arr[$j] < $arr[$j - 1]) {                     list($arr[$j], $arr[$j - 1]) = [$arr[$j - 1], $arr[$j]];//交换位置。                 }             }         }         return $arr;     }

选择排序

原理描述:

每次一次从数组中取出最小元素或者最大元素,放到指定位置。

第一步:给第一个元素一个圣火令,和后面到每个元素比较,(我是取最小元素)。遇到比它小到元素就把这个圣火令给它,知道把圣火令交给最小元素手里。

第二步:交换位置,圣火令交给第二哥元素,重复第一步。

流程:

PHP 排序算法原理及总结

<?php     function selectSort($arr)     {         $len = count($arr);         if ($len <= 1) {//一个元素或者没有元素,排序没有意义。             return $arr;         }         for($i = 0; $i < $len - 1; $i++) {             $p = $i;//给第一个元素圣火令。             for($j =  $i + 1; $j < $len; $j++) {                 if ($arr[$j] < $arr[$p]) {//有圣火令的元素和后面的元素比较,把圣火令交给较小的元素。                     $p = $j;                 }             }             list($arr[$p], $arr[$i]) = [$arr[$i], $arr[p]];         }         return $arr;     }

赞(0)
分享到: 更多 (0)
网站地图   沪ICP备18035694号-2    沪公网安备31011702889846号