@TOC

一、前言

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

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

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

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

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

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

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

二、5种排序算法

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

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

    public function __construct($n)
    {
   
   
        {
   
   mathJaxContainer[0]}n;
    }

    public function randNumberArray()
    {
   
   
        $data = [];
        for ({
   
   mathJaxContainer[1]}i< {
   
   mathJaxContainer[2]}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 {
   
   mathJaxContainer[3]}data);
    }

    // 将一个数组分成两部分，左边部分大于第一个元素，右边部分小于第一个元素，最后把第一个元素放在他们中间
    private function _quickSort($data)
    {
   
   
        if(count($data) <= 1) {
   
   
            return $data;
        }
        {
   
   mathJaxContainer[4]}right = [];
        {
   
   mathJaxContainer[5]}data[0];
        {
   
   mathJaxContainer[6]}data);
        for ({
   
   mathJaxContainer[7]}i < {
   
   mathJaxContainer[8]}i ++ ) {
   
   
            if({
   
   mathJaxContainer[9]}i] < $targetValue) {
   
   
                {
   
   mathJaxContainer[10]}data[$i];
            }else {
   
   
                {
   
   mathJaxContainer[11]}data[$i];
            }
        }
        return array_merge({
   
   mathJaxContainer[12]}left), [{
   
   mathJaxContainer[13]}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({
   
   mathJaxContainer[14]}j, &$data) {
   
   
        {
   
   mathJaxContainer[15]}data[$i];
        {
   
   mathJaxContainer[16]}i] = {
   
   mathJaxContainer[17]}j];
        {
   
   mathJaxContainer[18]}j] = $tmp;
    }

    public function run($data)
    {
   
   
        {
   
   mathJaxContainer[19]}data);
        // i 依次从前往后取，时刻维护i前面的顺序是有序的，不是有序的变成有序的
        for ({
   
   mathJaxContainer[20]}i < {
   
   mathJaxContainer[21]}i++) {
   
   
            // 用j 依次取i前面的数和i比较，当前面存在大于j位置的数，就发生交换行为
            for ({
   
   mathJaxContainer[22]}i-1; {
   
   mathJaxContainer[23]}j--) {
   
   
                if({
   
   mathJaxContainer[24]}j] > {
   
   mathJaxContainer[25]}i]) {
   
   
                    {
   
   mathJaxContainer[26]}j, {
   
   mathJaxContainer[27]}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({
   
   mathJaxContainer[28]}j, &$data) {
   
   
        {
   
   mathJaxContainer[29]}data[$i];
        {
   
   mathJaxContainer[30]}i] = {
   
   mathJaxContainer[31]}j];
        {
   
   mathJaxContainer[32]}j] = $tmp;
    }

    public function run($data)
    {
   
   
        {
   
   mathJaxContainer[33]}data);
        for ({
   
   mathJaxContainer[34]}i < {
   
   mathJaxContainer[35]}i++) {
   
   
            {
   
   mathJaxContainer[36]}data[$i];
            {
   
   mathJaxContainer[37]}i;
            for({
   
   mathJaxContainer[38]}i + 1; {
   
   mathJaxContainer[39]}n; $j ++) {
   
   
                // 依次找到最小值对应的索引 k
                if({
   
   mathJaxContainer[40]}j] < $min) {
   
   
                    {
   
   mathJaxContainer[41]}data[$j];
                    {
   
   mathJaxContainer[42]}j;
                }
            }
            if({
   
   mathJaxContainer[43]}i) {
   
   
                {
   
   mathJaxContainer[44]}k, {
   
   mathJaxContainer[45]}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({
   
   mathJaxContainer[46]}j, &$data) {
   
   
        {
   
   mathJaxContainer[47]}data[$i];
        {
   
   mathJaxContainer[48]}i] = {
   
   mathJaxContainer[49]}j];
        {
   
   mathJaxContainer[50]}j] = $tmp;
    }

    public function run($data)
    {
   
   
        {
   
   mathJaxContainer[51]}data);
        for ({
   
   mathJaxContainer[52]}i < {
   
   mathJaxContainer[53]}i++) {
   
   
            for({
   
   mathJaxContainer[54]}i + 1; {
   
   mathJaxContainer[55]}n; $j++) {
   
   
                if({
   
   mathJaxContainer[56]}j] < {
   
   mathJaxContainer[57]}i]) {
   
   
                    {
   
   mathJaxContainer[58]}j, {
   
   mathJaxContainer[59]}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 {
   
   mathJaxContainer[60]}data);
    }

    /**
     * 排序核心算法
     * @param $data
     * @return array
     */
    public function _sort($data)
    {
   
   
        // 归并算法需要依靠一个额外的数组来完成排序结果，在排序的时候保证左边的数据和右边的数据分别是有序的，
        // 然后依次比较左右两边的数据将相对较小的数据放入final中
        $final = [];
        {
   
   mathJaxContainer[61]}data) - 1;
        {
   
   mathJaxContainer[62]}r/2);
        $i = 0;
        {
   
   mathJaxContainer[63]}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({
   
   mathJaxContainer[64]}k <= {
   
   mathJaxContainer[65]}k++ ) {
   
   
            // 1. 如果右边位置j对应的数据更小，将j对应的值放到final的位置，然后j位置后移等待下一次考察
            // 2. 如果$i > $mid 表示左边i位置已经遍历完了，就依次把右边的数放到final后面，因为数组本身就是有序的
            // 3. $j <= $r表示如果j已经到了右边的末尾了，则把左边数据依次放到final后面，因为数组本身就是有序的，else其他情况移动i，和1 2中逻辑相同
            if(
                ({
   
   mathJaxContainer[68]}j] < {
   
   mathJaxContainer[69]}i] || {
   
   mathJaxContainer[70]}mid)
                &&
                {
   
   mathJaxContainer[71]}r
            ) {
   
   
                {
   
   mathJaxContainer[72]}k] = {
   
   mathJaxContainer[73]}j];
                $j++;
            }else {
   
   
                {
   
   mathJaxContainer[74]}k] = {
   
   mathJaxContainer[75]}i];
                $i++;
            }
        }
        return $final;
    }

    /**
     *
     * @param $data
     * @return array
     */
    private function getBisect($data)
    {
   
   
        {
   
   mathJaxContainer[76]}right = [];
        {
   
   mathJaxContainer[77]}data) - 1)/2);
        for ({
   
   mathJaxContainer[78]}i < count({
   
   mathJaxContainer[79]}i ++) {
   
   
            {
   
   mathJaxContainer[80]}mid ? {
   
   mathJaxContainer[81]}data[{
   
   mathJaxContainer[82]}right[] = {
   
   mathJaxContainer[83]}i];
        }
        return [{
   
   mathJaxContainer[84]}right];
    }


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

        list({
   
   mathJaxContainer[85]}right) = {
   
   mathJaxContainer[86]}data);

        return $this->_sort(
            array_merge(
                {
   
   mathJaxContainer[87]}left),
                {
   
   mathJaxContainer[88]}right)
            )
        );
    }
}
$res = (new MergeSort())->run((new Generate(100))->randNumberArray());
echo json_encode($res);

总结

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