一、前言

排序算法是一种将一组无序的数据元素按照某个规则(大小、字母序等)排列成有序的序列的算法。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。

1.快速排序：选择一个基准元素，根据比基准元素小的和比基准元素大的将序列分为两部分，对两部分递归地进行排序。

2.插入排序：将未排序部分逐个插入到已排序部分中的正确位置，使得已排序部分一直有序。

3.选择排序：每次选取当前未排序部分中最小的元素，放到已排序部分的末尾。

4.冒泡排序：比较相邻元素的大小，如果前面比后面大，则交换两个元素。通过多轮扫描，最大的元素被交换到了最后一位。

5.归并排序：将序列拆分成长度为一的子序列，然后将相邻的子序列合并，不断重复直到序列有序。

以上这些排序算法都有各自的优点和缺点，在实际应用中需要根据具体情况选择合适的算法。本文将对5种排序算法进行讲解。

二、5种排序算法

本文使用到的数据生成工具类代码如下：

<?php
class Generate {
    private $n = 0;

    public function __construct($n)
    {
        $this->n = $n;
    }

    public function randNumberArray()
    {
        $data = [];
        for ($i = 0; $i< $this->n; $i++) {
            $data[] = rand(1, 100);
        }
        return $data;
    }
}

2.1 快速排序

快速排序是一种常用的排序算法，它以递归的方式对待排序数据进行排序。快速排序的基本思路是将待排序数据序列划分成两个子序列，一个子序列中所有元素都比另一个子序列中的元素小（或大），再对这两个子序列递归进行快速排序，直到每个子序列只有一个元素为止。

具体来说，快速排序要选择一个基准元素，把待排序数据按照这个基准元素进行划分。一般情况下，我们选择第一个元素作为基准元素（也可以随机选择），然后从序列 的右端开始往左扫描，找到第一个比基准元素小的元素，并将其与基准元素交换；接着从序列的左端开始往右扫描，找到第一个比基准元素大的元素，并将其与基准元素交换。这样就完成了一次划分，基准元素也就排好了位置。然后对左右两个子序列递归进行快速排序即可。

快速排序的时间复杂度为O(nlogn)，空间复杂度为O(logn)。但是快速排序也有缺点，当数据已经有序或近似有序时，快排效率会非常低，甚至退化到O(n^2)的时间复杂度。因此，实际应用中需要根据具体情况选择合适的排序算法。

<?php
include '../Generate.php';

/**
 * 思路分析：选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。
 * 此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。
 */
class QuickSort {

    public function run($data)
    {
        return $this->_quickSort($data);
    }

    // 将一个数组分成两部分，左边部分大于第一个元素，右边部分小于第一个元素，最后把第一个元素放在他们中间
    private function _quickSort($data)
    {
        if(count($data) <= 1) {
            return $data;
        }
        $left = $right = [];
        $targetValue = $data[0];
        $r = count($data);
        for ($i = 1; $i < $r; $i ++ ) {
            if($data[$i] < $targetValue) {
                $left[] = $data[$i];
            }else {
                $right[] = $data[$i];
            }
        }
        return array_merge($this->_quickSort($left), [$data[0]], $this->_quickSort($right));
    }
}

$res = (new QuickSort())->run((new Generate(100))->randNumberArray());
echo json_encode($res);

2.2 插入排序

插入排序是一种简单直观的排序算法，其核心思想是将待排序的元素插入到已排好序的序列中，通过不断地插入和比较，最终完成排序。具体实现流程如下：

• 将第一个元素视为已排序序列，从第二个元素开始遍历；
• 依次将每个元素插入到已排序序列中的正确位置，插入过程中需要比较大小并交换位置；
• 重复步骤2，直到所有元素都插入到已排序序列中，排序完成。

插入排序的时间复杂度为O(n^2)，空间复杂度为O(1)，适用于小规模数据的排序。此外，插入排序还具有稳定性，即相等元素的相对位置不会改变。

include '../Generate.php';
class InsertSort {

    public function swap($i, $j, &$data) {
        $tmp = $data[$i];
        $data[$i] = $data[$j];
        $data[$j] = $tmp;
    }

    public function run($data)
    {
        $n = count($data);
        // i 依次从前往后取，时刻维护i前面的顺序是有序的，不是有序的变成有序的
        for ($i = 1; $i < $n; $i++) {
            // 用j 依次取i前面的数和i比较，当前面存在大于j位置的数，就发生交换行为
            for ($j = $i-1; $j >= 0; $j--) {
                if($data[$j] > $data[$i]) {
                    $this->swap($j, $i, $data);
                    $i --;
                } else {
                    // 前面数据本身是有序的，如果不存在交换，表示已经是有序，可直接退出
                    break;
                }
            }
        }
        return $data;
    }
}

$res = (new InsertSort())->run((new Generate(100))->randNumberArray());
echo json_encode($res);

2.3 选择排序

选择排序（Selection Sort）是一种简单直接的排序算法，它的基本思想是： 每趟从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。

具体实现过程如下：

• 遍历数组，找到最小的元素，将其与第一个元素交换；
• 从第二个元素开始遍历，找到剩余元素中最小的元素，将其与第二个元素交换；
• 重复上述步骤，直到排序完成。

选择排序算法的时间复杂度为O(n^2)，其中n为待排序元素的个数，需要进行的比较次数和交换次数都很多。虽然效率不如其他高级排序算法，但由于其简单直观，是初学者学习排序算法的良好入门知识点。

class SelectSort {

    public function swap($i, $j, &$data) {
        $tmp = $data[$i];
        $data[$i] = $data[$j];
        $data[$j] = $tmp;
    }

    public function run($data)
    {
        $n = count($data);
        for ($i = 0; $i < $n; $i++) {
            $min = $data[$i];
            $k = $i;
            for($j = $i + 1; $j < $n; $j ++) {
                // 依次找到最小值对应的索引 k
                if($data[$j] < $min) {
                    $min = $data[$j];
                    $k = $j;
                }
            }
            if($k != $i) {
                $this->swap($k, $i, $data);
            }
        }
        return $data;
    }
}

$res = (new SelectSort())->run((new Generate(100))->randNumberArray());
echo json_encode($res);

2.4 冒泡排序

冒泡排序是一种基本的排序算法，它的原理是比较相邻元素的大小并交换位置，重复该过程直到所有元素排序完毕。

具体步骤如下：

• 从第一个元素开始，依次比较相邻两个元素的大小（如果是升序，则比较前一个元素是否大于后一个元素；如果是降序，则比较前一个元素是否小于后一个元素），如果不符合要求，则交换它们的位置。
• 继续比较下一个相邻元素，直到最后一个元素，此时最大或最小的元素已经排在了最后。
• 重复以上步骤，每次比较的元素数减少1，直到所有的元素都排序完成。

冒泡排序的算法复杂度是O(n²)，在数据量比较小的场景下，可以使用冒泡排序，但对于大量数据的排序，建议使用其他更高效的排序算法。

class BubbleSort {

    public function swap($i, $j, &$data) {
        $tmp = $data[$i];
        $data[$i] = $data[$j];
        $data[$j] = $tmp;
    }

    public function run($data)
    {
        $n = count($data);
        for ($i = 0; $i < $n; $i++) {
            for($j = $i + 1; $j < $n; $j++) {
                if($data[$j] < $data[$i]) {
                    $this->swap($j, $i, $data);
                }
            }
        }
        return $data;
    }
}

$res = (new BubbleSort())->run((new Generate(100))->randNumberArray());
echo json_encode($res);

2.5 归并排序

归并排序是一种基于分治思想的排序算法，它将待排序序列划分为若干个子序列，每个子序列都是有序的，然后再将子序列合并成一个有序的序列。具体步骤如下：

• 将待排序序列不断二分，直到每个子序列只有一个元素。
• 将相邻的子序列两两合并，合并后仍然保持有序。
• 重复上述步骤，直到所有的子序列合并成一个有序的序列。

归并排序的时间复杂度为O(nlogn)，它是一种稳定的排序算法，但空间复杂度比较高，需要额外的存储空间来存储子序列。虽然归并排序不如快速排序在大部分情况下快速，它对数据的分布没有要求，因此在处理大规模数据时更加稳定和可靠。

<?php
include '../Generate.php';

/**
 *
 */
class MergeSort {

    /**
     * 入口
     * @param $data
     * @return array|mixed
     */
    public function run($data)
    {
        return $this->_mergeSort($data);
    }

    /**
     * 排序核心算法
     * @param $data
     * @return array
     */
    public function _sort($data)
    {
        // 归并算法需要依靠一个额外的数组来完成排序结果，在排序的时候保证左边的数据和右边的数据分别是有序的，
        // 然后依次比较左右两边的数据将相对较小的数据放入final中
        $final = [];
        $r = count($data) - 1;
        $mid = floor($r/2);
        $i = 0;
        $j = $mid + 1;
        // i 开始指向左边的第一个数字，j指向右边的第一个数字，依次比较

        // 初始状态
        // []
        // [1 3 5 7 ｜ 2 4 6 8]
        // [i       |  j     ]

        // 第一次排序
        // [1]
        // [1 3 5 7 ｜ 2 4 6 8]
        // [  i     |  j     ]

        // 第二次排序
        // [1 2]
        // [1 3 5 7 ｜ 2 4 6 8]
        // [  i     |    j    ]

        // 第三次排序
        // [1 2 3]
        // [1 3 5 7 ｜ 2 4 6 8]
        // [    i        j    ]
        for($k = 0; $k <= $r; $k++ ) {
            // 1. 如果右边位置j对应的数据更小，将j对应的值放到final的位置，然后j位置后移等待下一次考察
            // 2. 如果$i > $mid 表示左边i位置已经遍历完了，就依次把右边的数放到final后面，因为数组本身就是有序的
            // 3. $j <= $r表示如果j已经到了右边的末尾了，则把左边数据依次放到final后面，因为数组本身就是有序的，else其他情况移动i，和1 2中逻辑相同
            if(
                ($data[$j] < $data[$i] || $i > $mid)
                &&
                $j <= $r
            ) {
                $final[$k] = $data[$j];
                $j++;
            }else {
                $final[$k] = $data[$i];
                $i++;
            }
        }
        return $final;
    }

    /**
     *
     * @param $data
     * @return array
     */
    private function getBisect($data)
    {
        $left = $right = [];
        $mid = floor((count($data) - 1)/2);
        for ($i = 0; $i < count($data); $i ++) {
            $i <= $mid ? $left[] = $data[$i] : $right[] = $data[$i];
        }
        return [$left, $right];
    }


    /**
     *
     * @param $data
     * @return array|mixed
     */
    private function _mergeSort($data)
    {
        if(count($data) <= 1) {
            return $data;
        }

        list($left, $right) = $this->getBisect($data);

        return $this->_sort(
            array_merge(
                $this->_mergeSort($left),
                $this->_mergeSort($right)
            )
        );
    }
}
$res = (new MergeSort())->run((new Generate(100))->randNumberArray());
echo json_encode($res);

总结

以上就是关于本篇文章介绍的内容，用PHP实现经典的4种排序算法，喜欢点个收藏关注吧。