冒泡排序
原理
冒泡排序是一种简单直观的排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢 "浮" 到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名 "冒泡排序"。
步骤
- 比较相邻的元素：如果第一个比第二个大，就把它们两个交换
- 对每一对相邻元素作同样的工作：从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数
- 针对所有的元素重复以上的步骤：除了最后一个
- 持续每次对越来越少的元素重复上面的步骤：直到没有任何一对数字需要比较
复杂度
时间复杂度
- 最坏情况：O(n^2)
- 平均情况：O(n^2)
- 最好情况：O(n)
空间复杂度
- 原地排序：O(1)
稳定性
- 稳定排序：冒泡排序在排序过程中，如果遇到相同的元素，不会改变它们的相对位置，所以是稳定的
适用场景
- 数据量较小
- 输入数据基本有序
- 对内存要求不高
代码
<?php
declare(strict_types=1);
class SortingComparison
{
public function bubbleSort(array $array): array
{
$count = count($array);
for ($i = 0; $i < $count - 1; $i++) {
$swapped = false;
for ($j = 0; $j < $count - $i - 1; $j++) {
if ($array[$j] > $array[$j + 1]) {
// 交换相邻元素
$temp = $array[$j];
$array[$j] = $array[$j + 1];
$array[$j + 1] = $temp;
$swapped = true;
echo "交换({$array[$j+1]},{$array[$j]}) ";
}
}
// 如果没有交换，说明已经排序完成
if (!$swapped) {
echo "没有交换发生，排序完成！\n";
break;
}
}
return $array;
}
}
选择排序
原理
选择排序是一种简单直观的排序算法。它的工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。
步骤
- 初始状态：无序区为
R[1..n]，有序区为空 - 第i趟排序（i=1,2,3...n-1）：
- 在无序区
R[i..n]中选出最小的元素，将其与无序区的第一个元素交换 - 使有序区增加一个元素，无序区减少一个元素
- 在无序区
- n-1趟结束：数组有序化了
复杂度
时间复杂度
- 最坏情况：O(n^2)
- 平均情况：O(n^2)
- 最好情况：O(n^2)
空间复杂度
- 原地排序：O(1)
稳定性
- 不稳定排序：选择排序在排序过程中，会改变相同元素的相对位置，所以是不稳定的
适用场景
- 对内存要求不高
- 数据量较小
- 对交换操作的次数比较少
代码
<?php
declare(strict_types=1);
class SortingComparison
{
public function selectionSort(array $array): array
{
$count = count($array);
for ($i = 0; $i < $count - 1; $i++) {
$minIndex = $i;
for ($j = $i + 1; $j < $count; $j++) {
if ($array[$j] < $array[$minIndex]) {
$minIndex = $j;
}
}
// 交换找到的最小值与当前位置
if ($minIndex != $i) {
$temp = $array[$i];
$array[$i] = $array[$minIndex];
$array[$minIndex] = $temp;
echo "交换位置 $i 和 $minIndex ({$array[$i]} 和 {$array[$minIndex]})";
} else {
echo "最小值已在正确位置";
}
echo " -> [" . implode(', ', $array) . "]\n";
}
return $array;
}
}
插入排序
原理
插入排序是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
步骤
- 初始状态：有序区为
R[1]，无序区为R[2..n] - 第i趟排序（i=2,3,4...n）：
- 从无序区
R[i]中取出元素，记为temp - 在有序区
R[1..i-1]中从后向前查找，找到第一个比temp小的元素 - 将有序区中大于
temp的元素都往后移动一位 - 将
temp插入到正确位置
- 从无序区
复杂度
时间复杂度
- 最坏情况：O(n^2)
- 平均情况：O(n^2)
- 最好情况：O(n)
空间复杂度
- 原地排序：O(1)
稳定性
- 稳定排序：插入排序在排序过程中，不会改变相同元素的相对位置，所以是稳定的
适用场景
- 对内存要求不高
- 数据量较小
- 对交换操作的次数比较少
代码
<?php
declare(strict_types=1);
class SortingComparison
{
public function insertionSort(RequestInterface $request):Result
{
$array = [3,5,36,75,57,78,1,6,4];
$count = count($array);
for ($i = 1; $i < $count ; $i++) {
$temp = $array[$i];
$j = $i - 1;
while ( $j>=0 && $array[$j] > $temp ) {
$array[$j+1] = $array[$j];
$j--;
}
$array[$j + 1] = $j;
}
return $this->success($array, '排序完成');
}
}
快速排序
原理
快速排序是一种高效的排序算法，它采用分治策略。它的基本思想是：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
步骤
- 选择基准：从数列中挑出一个元素，称为 “基准”（
pivot） - 分割：重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面（相同的数可以到任何一边）。在这个分割结束之后，对基准值的排序就已经完成
- 递归排序子序列：递归地将小于基准值元素的子数列和大于基准值元素的子数列排序
- 合并：递归的结束条件是数列的大小是零或一，此时该数列显然已经有序。
复杂度
时间复杂度
- 最坏情况：O(n^2)
- 平均情况：O(nlogn)
- 最好情况：O(nlogn)
空间复杂度
- 原地排序：O(logn)
稳定性
- 不稳定排序：快速排序在排序过程中，会改变相同元素的相对位置，所以是不稳定的
适用场景
- 对内存要求不高
- 数据量较大
- 对交换操作的次数比较少
代码
<?php
declare(strict_types=1);
class SortingComparison
{
/**
* 快速排序
* @param array $array
* @return array
*/
public function quickSort(array $array) :array
{
$count = count($array);
if( $count <= 1 ){
return $array;
}
//选择一个元素作为基准值
$pivotIndex = intdiv($count, 2);
//小于基准值放左边,大于基准值放右边
$pivot = $array[$pivotIndex];
$left = $right = [];
for ( $i = 0;$i < $count; $i++ ){
if( $i == $pivotIndex ){
continue;
}
if( $array[$i] <= $pivot ){
$left[] = $array[$i];
}else{
$right[] = $array[$i];
}
}
return array_merge($this->quickSort($left), [$pivot], $this->quickSort($right));
}
public function quickSortDemo()
{
$array = $this->quickSort([3,5,36,75,57,78,1,6,4]);
return $this->success($array, '排序完成');
}
}
希尔排序
原理
希尔排序是一种插入排序的改进版本。它通过比较相距一定间隔的元素来工作，各趟比较所用的距离随着算法的进行而减小，直到只比较相邻元素的最后一趟排序为止。
步骤
- 选择增量序列：选择一个增量序列，通常是按照
Knuth提出的增量序列进行选择 - 增量排序：根据增量序列，将待排序列分成多个子序列，分别进行插入排序
- 缩小增量：重复上述步骤，直到增量为1，此时整个序列已经基本有序，最后进行一次直接插入排序即可
复杂度
时间复杂度
- 最坏情况：O(n^2)
- 平均情况：O(nlogn)
- 最好情况：O(nlogn)
空间复杂度
- 原地排序：O(1)
稳定性
- 不稳定排序：希尔排序在排序过程中，会改变相同元素的相对位置，所以是不稳定的
适用场景
- 对内存要求不高
- 数据量较大
- 对交换操作的次数比较少
代码
<?php
declare(strict_types=1);
class SortingComparison
{
/**
* 希尔排序
* @param array $array
* @return array
*/
public function shellSort(array $array) :array
{
$count = count($array);
$gap = intdiv($count, 2);
while ( $gap > 0 ){
for ( $i = $gap; $i < $count; $i++ ){
$temp = $array[$i];
$j = $i - $gap;
while ( $j >= 0 && $array[$j] > $temp ){
$array[$j + $gap] = $array[$j];
$j -= $gap;
}
$array[$j + $gap] = $temp;
}
$gap = intdiv($gap, 2);
}
return $array;
}
}
归并排序
原理
归并排序是一种分治策略的排序算法，它将待排序列分成多个子序列，分别进行排序，最后将排好序的子序列合并起来。
步骤
- 划分：将待排序列分成多个子序列，每个子序列包含一个元素
- 合并：将相邻的子序列合并成有序的子序列，直到所有的子序列都合并成一个有序序列
复杂度
时间复杂度
- 最坏情况：O(nlogn)
- 平均情况：O(nlogn)
- 最好情况：O(nlogn)
空间复杂度
- 原地排序：O(n)
稳定性
- 稳定排序：归并排序在合并过程中，只有当左边的元素大于右边的元素时，才会交换位置，所以是稳定的
适用场景
- 对内存要求较高
- 数据量较大
- 对稳定性要求较高
代码
<?php
declare(strict_types=1);
class SortingComparison
{
/**
* 归并排序
* @param array $array
* @return array
*/
public function mergeSort(array $array) :array
{
$count = count($array);
if( $count <= 1 ){
return $array;
}
$mid = intdiv($count, 2);
$left = array_slice($array, 0, $mid);
$right = array_slice($array, $mid);
return $this->merge($this->mergeSort($left), $this->mergeSort($right));
}
/**
* 合并
* @param array $left
* @param array $right
* @return array
*/
public function merge(array $left, array $right) :array
{
$result = [];
$i = 0;
$j = 0;
while ( $i < count($left) && $j < count($right) ){
if( $left[$i] <= $right[$j] ){
$result[] = $left[$i];
$i++;
}else{
$result[] = $right[$j];
$j++;
}
}
$result = array_merge($result, array_slice($left, $i));
$result = array_merge($result, array_slice($right, $j));
return $result;
}
}
堆排序
原理
堆排序是一种选择排序的改进版本。它通过构建一个堆来实现排序，堆是一种完全二叉树，每个节点的值都大于等于（或小于等于）其子节点的值。
步骤
- 构建堆：将待排序列构建成一个堆
- 交换元素：将堆顶元素与最后一个元素交换位置，然后对堆顶元素进行下沉操作，直到所有的元素都被交换位置
复杂度
时间复杂度
- 最坏情况：O(nlogn)
- 平均情况：O(nlogn)
- 最好情况：O(nlogn)
空间复杂度
- 原地排序：O(1)
稳定性
- 不稳定排序：堆排序在交换元素的过程中，会改变相同元素的相对位置，所以是不稳定的
适用场景
- 对内存要求较高
- 数据量较大
- 对稳定性要求较高
代码
<?php
declare(strict_types=1);
class SortingComparison
{
/**
* 堆排序
* @param array $array
* @return array
*/
public function heapSort(array $array) :array
{
$count = count($array);
for ( $i = intdiv($count, 2); $i >= 0; $i-- ){
$this->heapify($array, $i, $count);
}
for ( $i = $count - 1; $i > 0; $i-- ){
$this->swap($array, 0, $i);
$this->heapify($array, 0, $i);
}
return $array;
}
/**
* 堆化
* @param array $array
* @param int $i
* @param int $count
* @return void
*/
private function heapify(array &$array, int $i, int $count) :void
{
$left = 2 * $i + 1;
$right = 2 * $i + 2;
$largest = $i;
if( $left < $count && $array[$left] > $array[$largest] ){
$largest = $left;
}
if( $right < $count && $array[$right] > $array[$largest] ){
$largest = $right;
}
if( $largest != $i ){
$this->swap($array, $i, $largest);
$this->heapify($array, $largest, $count);
}
}
/**
* 交换元素
* @param array $array
* @param int $i
* @param int $j
* @return void
*/
private function swap(array &$array, int $i, int $j) :void
{
$temp = $array[$i];
$array[$i] = $array[$j];
$array[$j] = $temp;
}
}
计数排序
原理
计数排序是一种非比较排序的算法，它的时间复杂度为O(n+k)，其中n是待排序列的长度，k是待排序列的最大值。
步骤
- 统计元素出现次数：遍历待排序列，统计每个元素出现的次数
- 计算元素位置：根据元素出现的次数，计算元素在有序序列中的位置
- 填充有序序列：根据元素出现的次数和位置，填充有序序列
复杂度
时间复杂度
- 最坏情况：O(n+k)
- 平均情况：O(n+k)
- 最好情况：O(n+k)
空间复杂度
- 非原地排序：O(n+k)
稳定性
- 稳定排序：计数排序在填充有序序列的过程中，会保持相同元素的相对位置，所以是稳定的
适用场景
- 对内存要求较高
- 数据量较大
- 对稳定性要求较高
代码
<?php
declare(strict_types=1);
class SortingComparison
{
/**
* 计数排序
* @param array $array
* @return array
*/
public function countingSort(array $array) :array
{
$count = count($array);
$max = max($array);
$min = min($array);
$countArray = array_fill($min, $max - $min + 1, 0);
for ( $i = 0; $i < $count; $i++ ){
$countArray[$array[$i]]++;
}
for ( $i = $min + 1; $i <= $max; $i++ ){
$countArray[$i] += $countArray[$i - 1];
}
for ( $i = $count - 1; $i >= 0; $i-- ){
$array[$countArray[$array[$i]] - 1] = $array[$i];
$countArray[$array[$i]]--;
}
return $array;
}
}