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
    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;
    }

php