四大基本經典排序算法
性能 ： 快速排序 > 選擇排序 > 冒泡排序 > 直接排序
時間復雜度：nlogn > O（n2）
<?php
/**
* 【 四大基本經典排序算法 】
* 性能 ： 快速排序 > 選擇排序 > 冒泡排序 > 直接排序
*/
$arr = array(9, 1, 5, 8, 3, 7, 4, 6, 2);
/**
* 快速排序
* @param $arr
* @return array
*/
function quickSort($arr)
{
//先判斷是否需要繼續(xù)進行
$length = count($arr);
if ($length <= 1) {
return $arr;
}
//選擇第一個元素作為基準
$base_num = $arr[0];
//遍歷除了標尺外的所有元素，按照大小關系放入兩個數(shù)組內
//初始化兩個數(shù)組
$left_array = array(); //小于基準的
$right_array = array(); //大于基準的
for ($i = 1; $i < $length; $i++) {
if ($base_num > $arr[$i]) {
//放入左邊數(shù)組
$left_array[] = $arr[$i];
} else {
//放入右邊
$right_array[] = $arr[$i];
}
}
//再分別對左邊和右邊的數(shù)組進行相同的排序處理方式遞歸調用這個函數(shù)
$left_array = quickSort($left_array);
$right_array = quickSort($right_array);
//合并
return array_merge($left_array, array($base_num), $right_array);
}
/**
* 插入排序 O（n2）
* @param $arr
* @return mixed
*/
function insertSort($arr)
{
$len = count($arr);
//假設第一個已經放好哗讥，后面的其實就是插入到它的左側還是右側
for ($i = 1; $i < $len; $i++) {
$tmp = $arr[$i]; //設置哨兵
//內層循環(huán)控制眉尸，比較并插入
for ($j = $i - 1; $j >= 0; $j--) {
if ($arr[$j] > $tmp) {
//發(fā)現(xiàn)插入的元素要小簿寂，交換位置，將后邊的元素與前面的元素互換
$arr[$j + 1] = $arr[$j];
$arr[$j] = $tmp;
} else {
//如果碰到不需要移動的元素鸣剪，由于是已經排序好是數(shù)組，則前面的就不需要再次比較了。
break;
}
}
}
return $arr;
}
/**
* 選擇排序 O（n2）
* @param $arr
* @return mixed
*/
function selectSort($arr)
{
//雙重循環(huán)完成慷嗜，外層控制輪數(shù)淀弹，內層控制比較次數(shù)
$len = count($arr);
for ($i = 0; $i < $len - 1; $i++) {
//先假設最小的值的位置
$min = $i;
for ($j = $i + 1; $j < $len; $j++) {
//$arr[$p] 是當前已知的最小值
if ($arr[$min] > $arr[$j]) {
//比較，發(fā)現(xiàn)更小的,記錄下最小值的位置庆械；并且在下次比較時采用已知的最小值進行比較薇溃。
$min = $j;
}
}
//已經確定了當前的最小值的位置，保存到$p中缭乘。如果發(fā)現(xiàn)最小值的位置與當前假設的位置$i不同沐序，則位置互換即可。
if ($min != $i) {
swap($arr, $min, $i);
}
}
//返回最終結果
return $arr;
}
/**
* 冒泡排序優(yōu)化 O(n2)
* @param $arr
* @return mixed
*/
function bubbleSortEX($arr)
{
$len = count($arr);
$flag = true;
//該層循環(huán)控制 需要冒泡的輪數(shù)
for ($i = 0; $i < $len-1 && $flag; $i++) { //該層循環(huán)用來控制每輪 冒出一個數(shù) 需要比較的次數(shù)
$flag = false;
for ($j = $len - 1; $j > $i; $j--) {
if ($arr[$j - 1] > $arr[$j]) {
swap($arr, $j - 1, $j);
$flag = true;
}
}
}
return $arr;
}
/**
* 冒泡排序 O(n2)
* @param $arr
* @return mixed
*/
function bubbleSort($arr)
{
$len = count($arr);
//該層循環(huán)控制 需要冒泡的輪數(shù)
for ($i = 0; $i < $len-1; $i++) { //該層循環(huán)用來控制每輪 冒出一個數(shù) 需要比較的次數(shù)
for ($j = $len - 1; $j > $i; $j--) {
if ($arr[$j - 1] > $arr[$j]) {
swap($arr, $j - 1, $j);
}
}
}
return $arr;
}
/**
* 簡單的直接排序
* @param $arr
* @return mixed
*/
function mySort($arr)
{
$len = count($arr);
//該層循環(huán)控制 需要比較的輪數(shù)
for ($i = 0; $i < $len - 1; $i++) {
for ($j = $i + 1; $j < $len; $j++) {
if ($arr[$i] > $arr[$j]) {
swap($arr, $i, $j);
}
}
}
return $arr;
}
/**
* 交換數(shù)組arr下表為i和j的值
* @param array $arr
* @param $i
* @param $j
*/
function swap(array &$arr, $i, $j)
{
$tmp = $arr[$i];
$arr[$i] = $arr[$j];
$arr[$j] = $tmp;
}
