排序方法 | 时间复杂度(平均) | 时间复杂度(最坏) | 时间复杂度(最好) | 空间复杂度 |
冒泡排序 | O(n2) | O(n2) | O(n) | O(1) |
选择排序 | O(n2) | O(n2) | O(n2) | O(1) |
插入排序 | O(n2) | O(n2) | O(n) | O(1) |
快速排序 | O(nlog2n) | O(n2) | O(nlog2n) | O(nlog2n) |
归并排序 | O(nlog2n) | O(nlog2n) | O(nlog2n) | O(n) |
1、冒泡排序
/**
* 冒泡排序
* @param $arr
* @return void
*/
public function bubbleSort(&$arr): void
{
$length = count($arr);
for ($i = 0; $i < $length; $i++) {
for ($j = $length - 1; $j > $i; $j--) {
if ($arr[$j] < $arr[$j - 1]) {
[$arr[$j], $arr[$j - 1]] = [$arr[$j - 1], $arr[$j]];
}
}
}
}
2、选择排序
/**
* 选择排序
* @param array $arr
* @return void
*/
function selectionSort(array &$arr): void
{
$length = count($arr);
// 外层循环,从数组首部开始,每完成一次循环,可确定一个元素的位置
for ($i = 0; $i < $length - 1; $i++) {
// 选定的最小值的索引
$minIdx = $i;
// 从 $i + 1 位开始循环,判断当前选定的元素是否是当次循环的最小值
for ($j = $i + 1; $j < $length; $j++) {
// 若出现比选定的值还小的值,则替换最小值的索引
if ($arr[$minIdx] > $arr[$j]) {
$minIdx = $j;
}
}
// 互换数组两个位置的值
[$arr[$i], $arr[$minIdx]] = [$arr[$minIdx], $arr[$i]];
}
}
/**
* 选择排序
* @param array $arr
* @return void
*/
function selectionSort2(array &$arr): void
{
$length = count($arr);
// 外层循环,从数组首部开始,每完成一次循环,依次确定数组元素的位置
for ($i = 0; $i < $length; $i++) {
// 从 $i + 1 位开始循环,依次判定 $arr[$i] 与 $arr[$j] 的大小
for ($j = $i + 1; $j < $length; $j++) {
// 若 $arr[$i] 比 $arr[$j] 大,则互换两个元素的位置
if ($arr[$i] > $arr[$j]) {
// 互换数组两个位置的值
[$arr[$j], $arr[$i]] = [$arr[$i], $arr[$j]];
}
}
}
}
3、插入排序
4、快速排序/** * 插入排序 * @param array $arr * @return void */ public function insertSort(array &$arr): void { $length = count($arr); // 从数组首部开始排序,每完成一次循环,可确定一个元素的位置 for ($i = 0; $i < $length - 1; $i++) { // 内层循环从 $i + 1 个元素开始,一位一位向前比较 // 若前面的值比自己大,则替换,直到前面的值比自己小了,停止循环 for ($j = $i + 1; $j > 0; $j--) { if ($arr[$j] >= $arr[$j - 1]) { break; } [[$arr[$j], $arr[$j - 1]]] = [[$arr[$j - 1], $arr[$j]]]; } }
}
/** * 插入排序 * @param array $arr * @return void */ function insertionSort2(array &$arr): void { $length = count($arr); // 从数组首部开始排序,每完成一次循环,可确定一个元素的位置 for ($i = 0; $i < $length - 1; $i++) { // 从第二个元素开始,选择固定位置的值作为基准值 $currentVal = $arr[$i + 1]; // 初始键位于选定值的前一个位置 $preIdx = $i; // 拿基准值一步一步向前比较,直到基准值比前面的值小,则两值互换位置 while ($preIdx >= 0 && $currentVal < $arr[$preIdx]) { $arr[$preIdx + 1] = $arr[$preIdx]; $arr[$preIdx] = $currentVal; $preIdx--; } } }
/**
* 快速排序
* @param $arr
* @return void
*/
public function quickSort1(&$arr)
{
$length = count($arr);
if ($length <= 1) {
return $arr;
}
$mid = $arr[0];
$leftArr = [];
$rightArr = [];
for ($i = 1; $i < $length; $i++) {
if ($arr[$i] < $mid) {
$leftArr[] = $arr[$i];
} else {
$rightArr[] = $arr[$i];
}
}
self::quickSort($leftArr);
self::quickSort($rightArr);
$arr = array_merge($leftArr, [$mid], $rightArr);
}
5、归并排序
发表评论 取消回复