一、前言
排序算法是一种将一组无序的数据元素按照某个规则(大小、字母序等)排列成有序的序列的算法。常见的排序算法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。
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种排序算法，喜欢点个收藏关注吧。
