【PHP + 代码审计】数组排序算法

🍬 博主介绍

👨‍🎓 博主介绍：大家好，我是 hacker-routing ，很高兴认识大家~
✨主攻领域：【渗透领域】【应急响应】 【Java、PHP】 【VulnHub靶场复现】【面试分析】
🎉点赞➕评论➕收藏 == 养成习惯（一键三连）😋
🎉欢迎关注💗一起学习👍一起讨论⭐️一起进步📝文末有彩蛋
🙏作者水平有限，欢迎各位大佬指点，相互学习进步！

冒泡排序

选择排序

插入排序

快速排序

查找算法

查找算法含义

顺序查找算法

二分查找算法

冒泡排序

冒泡排序（Bubble Sort），是一种计算机科学领域的较简单的排序算法。

它重复地走访过要排序的数列，一次比较两个元素，如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序的算法思路：

1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3）针对所有的元素重复以上的步骤，除了最后一个。

4）持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

<?php
//数组排序算法，冒泡排序

$arr = array(1, 3, 6, 5, 8, 9);

// 外层循环每次找出最大值的代码重复执行
for ($i = 0, $len = count($arr); $i < $len - 1; $i++) {
    // 内层循环将最大的值放到最右边
    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;
        }
    }
}

// 输出排序后的数组
echo '<pre>';
print_r($arr);

选择排序

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。选择排序是不稳定的排序方法（比如序列[5， 5， 3]第一次就将第一个[5]与[3]交换，导致第一个5挪动到第二个5后面）。

选择排序的算法思路：

1）假设第一个元素为最小元素，记下下标。

2）寻找右侧剩余的元素，如果有更小的，重新记下最新的下标。

3）如果有新的最小的，交换两个元素。

4）往右重复以上步骤，直到元素本身是最后一个。

<?php
//数组排序算法 ：选择排序
$arr = array(1, 3, 6, 2, 8, 5);
$len = count($arr);

for ($i = 0; $i < $len; $i++) {
    $min = $i;

    for ($j = $i + 1; $j < $len; $j++) {
        if ($arr[$j] < $arr[$min]) {
            $min = $j;
        }
    }

    if ($min != $i) {
        $temp = $arr[$i];
        $arr[$i] = $arr[$min];
        $arr[$min] = $temp;
    }
}
echo '<pre>';
print_r($arr);

插入排序

插入排序（Insert sort）,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。

插入排序的基本思想是：每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

插入排序的算法思路：

1）设置监视哨r[0]，将待插入纪录的值赋值给r[0]；

2）设置开始查找的位置j；

3）在数组中进行搜索，搜索中将第j个纪录后移，直至r[0].key≥r[j].key为止；

4）将r[0]插入r[j+1]的位置上。

1、认定第一个元素已经排好序；

2、取出第二个元素，作为待插入数据；

3、与已经排好序的数组的最右侧元素开始进行比较

4、如果后面的小于前面的：说明前面已经排好序的那个数组元素不在对的位置（向后移一个），然后让新的元素填充进去（继续向前比：高级）

5、重复前面的步骤：直到当前元素插入到对位置；

6、重复以上步骤，直到所有的数组元素都插入到对的位置。

<?php
//PHP数组排序 ：插入排序
$arr = array(4, 2, 3, 5, 9, 8);
$len = count($arr);

for ($i = 1; $i < $len; $i++) {
    $temp = $arr[$i];
    $positionCorrect = false; // 标记位置是否正确

    for ($j = $i - 1; $j >= 0; $j--) {
        if ($arr[$j] > $temp) {
            $arr[$j + 1] = $arr[$j];
            $arr[$j] = $temp;
        } else {
            $positionCorrect = true; // 标记位置正确
            break;
        }
    }

    if (!$positionCorrect) {
        $arr[$i] = $temp;
    }
}

echo '<pre>';
print_r($arr);

快速排序

快速排序（Quicksort）是对冒泡排序的一种改进。通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。（递归）

设要排序的数组是A[0]……A[N-1]，首先任意选取一个数据（通常选用数组的第一个数）作为关键数据，然后将所有比它小的数都放到它前面，所有比它大的数都放到它后面，这个过程称为一趟快速排序。值得注意的是，快速排序不是一种稳定的排序算法，也就是说，多个相同的值的相对位置也许会在算法结束时产生变动。

快速排序的算法是：

1）从数组中选出一个元素（通常第一个），作为参照对象。

2）定义两个数组，将目标数组中剩余的元素与参照元素挨个比较：小的放到一个数组，大的放到另外一个数组。

3）第二步执行完之后，前后的数组顺序不确定，但是确定了自己的位置。

4）将得到的小数组按照第1到第3部重复操作（子问题）。

5）回溯最小数组（一个元素）。

<?php
//快速排序
$arr = [1,2,3,7,4,8,6,5];
function quick_sort($arr){
    //递归出口
    $len = count($arr);
    if($len <= 1) return $arr;

    //取出某个元素，然后将剩余的数组元素，分散到两个不同的数组中
    $left = $right = array();
    for ($i = 1;$i < $len;$i++){
        //第一个元素作为比较元素
        //比较：小的放在left中，大的放right中
        if($arr[$i] < $arr[0]){
            $left[] = $arr[$i];
        }else{
            $right[] = $arr[$i];
        }
    }

    //合并三个数组
    return array_merge($left,array($arr[0]),$right);
}

echo '<pre>';
print_r(quick_sort($arr));