五种常见数组排序算法

2020-04-19

一、冒泡排序

冒泡排序算法思路

比较相邻的两个数组元素，如果第一个比第二个大，则交换两个的值
对每一对相邻元素做同样的工作，从开始第一对比较到最后一对，最后的元素应该是最大值
针对所有元素重复以上步骤，除了最后一个
针对越来越少的元素重复以上步骤，直至没有任何一对数字比较

代码实现：

<?php
//冒泡排序
$arr = array(4, 2, 76, 2, 7, 1, 9, 45);
  //控制循环次数
for ($i = 0; $len = count($arr), $i < $len; $i++) {    
    //控制最大值
    for ($j = 0; $j < $len - 1 - $i; $j++) {      
        //交换值
        if ($arr[$j] > $arr[$j + 1]) {         
            $arr[$j] = $arr[$j] + $arr[$j + 1];
            $arr[$j + 1] = $arr[$j] - $arr[$j + 1];
            $arr[$j] = $arr[$j] - $arr[$j + 1];
        }
    }
}
print_r($arr);

二、选择排序

选择排序算法思路：

假设第一个元素为最小值，记下其下标
寻找右侧剩下的元素，若有更小的，记录其下标
如果有新的最小值，交换元素
往右重复以上步骤，直至元素是最后一个

代码实现：

<?php
//选择排序
$arr = array(2, 6, 34, 2, 67, 33, 9);
//确定交换多少次，一次找到一个最小值
for ($i = 0; $len = count($arr), $i < $len; $i++) {   
    //假定第一个元素为最小值
    $min = $i;                             
     //拿最小值比较比较剩下的元素         
    for ($j = $i + 1; $j < $len; $j++) {          
        //比较当前元素与选定的最小元素
        if ($arr[$j] < $arr[$min]) {            
            //不符合交换下标
            $min = $j;                          
        }
    }
    //交换当前选定的最小值与实际最小值
    if ($min != $i) {                      
        $arr[$min] = $arr[$min] + $arr[$i];
        $arr[$i] = $arr[$min] - $arr[$i];
        $arr[$min] = $arr[$min] - $arr[$i];
    }
}
print_r($arr);

三、插入排序

插入排序算法思路：

假设第一个元素已经排好
取出第二个元素，作为待插入元素
与已经排好序的最右侧元素比较
如果后面的元素大于前面的元素，说明前面的元素不在正确的位置上，则往后退一个位置，然后让新的元素填充进去，继续向前比
重复以上步骤，直到元素插入正确位置
重复以上步骤，直至所有元素插入正确位置

代码实现：

<?php
//插入排序
$arr=array(6,3,8,9,5,3,7,10);
//确定插入多少回（假设一个数组一次插入到正确位置，同时第一个位置是对的）
for ($i=1;$len=count($arr),$i<$len;$i++){   
    //取出当前要插入的值
    $temp=$arr[$i];           
    //让该元素与前面已经排好序的元素比较
    for ($j=$i-1;$j>=0;$j--){    
        if ($arr[$j]>$temp){
            $arr[$j+1]=$arr[$j];
            $arr[$j]=$temp;
        }
        else{
            //比前一个元素大，所以不用比较在往前的，直接退出循环
            break;    
        }
    }
}
print_r($arr);

四、快速排序

快速排序算法思路:

假设将第一个元素作为比较元素
定义两个数组($left,$right),然后从第二个元素开始跟比较元素相比，小的放大$left数组里，大的放到$right数组里
这是中间的元素位置肯定是对的
用递归实现$left和$right元素的排序

代码实现：

<?php
//快速排序
$arr = array(2, 0, 1, 7, 3, 5, 6);
function quick_sort($arr)
{
    $len = count($arr);
    //如果数组长度小于等于1，直接返回该数组
    if ($len <= 1) {
        return $arr;
    }

    $left = $right = array();
    //取出第一个元素作为比较元素，剩下的元素比他小放到left,大的放到right
    for ($i = 1; $i < $len; $i++) {  
        if ($arr[$i] < $arr[0]) {
            $left[] = $arr[$i];
        } else {
            $right [] = $arr[$i];
        }
    }
    //递归排好左右两个数组元素
    $left = quick_sort($left);    
    $right = quick_sort($right);
     //合并三个数组
    return array_merge($left, (array)$arr[0], $right); 
}

print_r(quick_sort($arr));

五、归并排序

归并排序算法思路：

分而治之的思想
将要排序的数组从中间元素分开成两个数组，然后在定义一个新数组用来放归并的元素
把两个数组挨个比较，较小的先放进新定义的归并数组
直至两个数组都比较完，这时有一个数组只剩一个最大的元素，然后将归并完的数组与这个元素合并
注意左右两个数组递归排序内部元素

代码实现：

<?php
$arr = array(4, 7, 2, 1, 5, 9, 3);
function merge_sort($arr)
{
    $len = count($arr);
    if ($len <= 1) {
        return $arr;
    }
    //拆分
    $middle = round($len / 2);   
    $left = array_slice($arr, 0, $middle);
    $right = array_slice($arr, $middle);
     //递归左右两个数组
    $left = merge_sort($left);  
    $right = merge_sort($right);
    //两个数组里都有元素才比较
    while (count($left) && count($right)) {      
        //取出两个数组中第一个元素比较，小的放到$m
        $m[] = $left[0] < $right[0] ? array_shift($left) : array_shift($right);   

    }
    return array_merge($m, $left, $right);
}

print_r(merge_sort($arr));

本文作者： nowfitness
本文链接： https://www.nowfitness.top/archives/83965cd0.html
版权声明： 本作品采用知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。转载请注明出处！