常见的排序算法
冒泡排序
将数组中的相邻元素的比较和交换来把小的数交换到最前面
//冒泡排序
function maopao($num)
{
for ($i = 0; $i < count($num); $i++) {
for ($j = 0; $j < count($num) - $i - 1; $j++) {
if ($num[$j] > $num[$j + 1]) {
list($num[$j],$num[$j+1]) = [$num[$j+1],$num[$j]];
//$tmp = $num[$j + 1];
//$num[$j + 1] = $num[$j];
//$num[$j] = $tmp;
}
}
}
return $num;
}选择排序
先找出最小的一个数。放到最前面.
选择排序的思想其实和冒泡排序有点类似，都是在一次排序后把最小的元素放到最前面。但是过程不同，冒泡排序是通过相邻的比较和交换。而选择排序是通过对整体的选择。举个栗子，对5,3,8,6,4这个无序序列进行简单选择排序，首先要选择5以外的最小数来和5交换，也就是选择3和5交换，一次排序后就变成了3,5,8,6,4.对剩下的序列一次进行选择和交换，最终就会得到一个有序序列。其实选择排序可以看成冒泡排序的优化，因为其目的相同，只是选择排序只有在确定了最小数的前提下才进行交换，大大减少了交换的次数。选择排序的时间复杂度为O(n^2)
function check_array($arr)
{
$count = count($arr);
for ($i = 0; $i < $count; $i++) {
$min = $i;
for ($j = $i + 1; $j < $count; $j++) {
if ($arr[$min] > $arr[$j]) {
$min = $j;
}
}
if ($min != $i) {
list($arr[$min], $arr[$i]) = [$arr[$i],$arr[$min]];
//$tem = $arr[$min];
//$arr[$min] = $arr[$i];
//$arr[$i] = $tem;
}
}
return $arr;
}插入排序
插入排序类似玩儿扑克牌时候的理牌，将拿到的牌插入到正确的位置中去
function insertSort($arr)
{
$count = count($arr);
for ($i = 1; $i < $count; $i++) {
$key = $i-1;
$val = $arr[$i];
while ($val >= 0 && $arr[$key] > $val) {
$arr[$key + 1] = $arr[$key];
$key--;
}
$arr[$key + 1] = $val;
}
return $arr;
}快速排序
快速排序是比较和交换小数和大数，这样一来不仅把小数冒泡到上面同时也把大数沉到下面。选择一个数，将小于这个数的数放入左边数组、大于这个数的放入右边数组。
//简易排序排序、不是正确的快速排序！！
function qsort($arr)
{
$count = count($arr);
//这一步不能少!!!!
if($count <= 1)
{
return $arr;
}
$midlle = $arr[0];
$left = $right = [];
for ($i = 1; $i < $count; $i++) {
($arr[$i] < $midlle) ? $left[] = $arr[$i] : $right[] = $arr[$i];
}
$left = qsort($left);
$right = qsort($right);
return array_merge($left, [$midlle], $right);
}
快速排序:
通过数组引用改变数组内元素值、返回原数组
function swap(array &$arr,$a,$b){
$temp = $arr[$a];
$arr[$a] = $arr[$b];
$arr[$b] = $temp;
}
function Partition(array &$arr,$low,$high){
$pivot = $arr[$low]; //选取子数组第一个元素作为枢轴
while($low < $high){ //从数组的两端交替向中间扫描
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
}
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
function QSort(array &$arr,$low,$high){
if($low < $high){
$pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值
QSort($arr,$low,$pivot - 1); //对低子表进行递归排序
QSort($arr,$pivot + 1,$high); //对高子表进行递归排序
}
}
//快速排序入口
function QuickSort(array &$arr){
$low = 0;
$high = count($arr) - 1;
QSort($arr,$low,$high);
}参考资料
https://blog.csdn.net/baidu_30000217/article/details/53311840