以PHP语言为例 分析常见排序算法 冒泡排序 二分法(快速排序) 归并排序 选择排序 插入排序

排序是数据处理中一种很重要也很常用的运算,一般情况下,排序操作在数据处理过程中要花费许多时间,为了提高计算机的运行效率,我们提出并不断改进各种各样的排序算法,这些算法也从不同角度展示了算法设计的重要原则和技巧。

排序就是对一组杂乱无章的数据进行各种各样的排序,使其从无序的数据变成有序的数据,排序的目的就是为了方便查找,让我们一起愉快的GET新技能。

GET新技能1:冒泡排序

步骤:

    • 比较相邻的元素。如果第一个比第二个大,就交换他们两个。

    • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。

    • 针对所有的元素重复以上的步骤,除了最后一个。

    • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

效果图:


0.gif

<?php 
    function maopao($arr){
        $len = count($arr);
        for ($i=0; $i < $len-1; $i++) { 
            for ($j=0; $j < $len-1-$i; $j++) { 
                if($arr[$j]>$arr[$j+1]){
                    $tmp = $arr[$j];
                    $arr[$j] = $arr[$j+1];
                    $arr[$j+1] = $tmp;
                }
            }
        }
        return $arr;
    }
    $arr = array(2,5,27,4,67);
    $aa = maopao($arr);
    print_r($aa);


GET新技能2:二分法(快速排序)

步骤:

    • 从数列中挑出一个元素,称为 "基准"(pivot),

    • 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

    • 递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序。

效果图:


0 (1).gif

function qsort($arr){ // 1.判断是否是数组 且 数组是否为空 
    if(!is_array($arr) || empty($arr)){ 
        return array(); 
    } 
    // 2.计算数组长度若长度等于1不进行排序直接输出即可 
    $len = count($arr); 
    if($len <= 1){ return $arr; } 
    // 3.选出一个参考数 
    $key[0] = $arr[0]; 
    $left = array(); 
    $right = array(); 
    // 4.进行比较 
    for($i = 1; $i < $len; $i++){ 
        if($arr[$i] <= $key[0]){ 
            $left[] = $arr[$i]; 
        }else{ 
            $right[] = $arr[$i]; 
        } 
    } 
    // 进行排序 
    $left = qsort($left); 
    $right = qsort($right); 
    return array_merge($left,$key,$right); //合并成一个数组 
    } 
$arr = array(25,89,52,7,12,46,2,5,9,23,1); 
echo "<pre>"; 
print_r($arr); 
print_r(qsort($arr))


GET新技能3:归并排序

步骤:

    • 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列

    • 设定两个指针,最初位置分别为两个已经排序序列的起始位置

    • 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置

    • 重复步骤3直到某一指针达到序列尾

    • 将另一序列剩下的所有元素直接复制到合并序列尾

效果图:


0 (2).gif

$a = [1, 4, 6, 8, 10, 14, 16];
$b = [2, 3, 5, 8, 9, 11];
function merge_sort($a, $b){ 
    $a_i = $b_i = 0; 
    $count_a = count($a); 
    $count_b = count($b); 
    $ret = []; 
    while ($a_i < $count_a && $b_i < $count_b) { 
        if ($a[$a_i] > $b[$b_i]) { 
            array_push($ret, $b[$b_i]); 
            $b_i++; 
        } else { 
            array_push($ret, $a[$a_i]); 
            $a_i++; 
        } 
   } 
   if ($a_i < $count_a) { 
       $ret = array_merge($ret, array_slice($a, $a_i)); 
   } 
   if ($b_i < $count_b) { 
       $ret = array_merge($ret, array_slice($b, $b_i)); 
   } 
   return $ret;
}
    $ret = merge_sort($a, $b);
    echo implode(',', $ret);


GET新技能4:选择排序

步骤:

    • 首先在未排序序列中找到最小元素,存放到排序序列的起始位置

    • 然后,再从剩余未排序元素中继续寻找最小元素,然后放到排序序列末尾

    • 以此类推,直到所有元素均排序完毕。

效果图:


0 (3).gif

$arr = [1, 5, 2, 7, 97, 23, 1, 4];
function select_sort(array $arr){ 
    $count = count($arr); 
    if ($count < 2) return $arr; 
    for ($i = 0; $i < $count; $i++) { 
        $min = $arr[$i]; 
        $min_i = $i; 
        for ($j = $i; $j < $count; $j++) { 
            if ($arr[$j] < $min) { 
                $min = $arr[$j]; $min_i = $j; 
            } 
        } 
        $arr[$min_i] = $arr[$i]; 
        $arr[$i] = $min; 
   } 
   return $arr;
}
    $ret = select_sort($arr);
    echo implode(',', $ret);


GET新技能:插入排序

步骤:

    • 从第一个元素开始,该元素可以认为已经被排序

    • 取出下一个元素,在已经排序的元素序列中从后向前扫描

    • 如果该元素(已排序)大于新元素,将该元素移到下一位置

    • 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置

    • 将新元素插入到该位置中

    • 重复步骤2

效果图:


0 (4).gif

$arr = [1, 5, 2, 7, 97, 23, 1, 4];
function insert_sort($arr){ 
    $count = count($arr); 
    if ($count < 2) return $arr; 
    for ($i = 0; $i < $count; $i++) { 
        for ($j = $i; $j > 0; $j--) { 
            if ($arr[$j] < $arr[$j - 1]) { 
                $tmp = $arr[$j - 1]; 
                $arr[$j - 1] = $arr[$j]; 
                $arr[$j] = $tmp; 
                } 
            } 
        } 
    return $arr;
}
    $ret = insert_sort($arr);
    echo implode(',', $ret);





评论

纳兰性急:期待你的更新
06月25日 10:16
你撤回了一条消息:之前也看过不少有关此类的文章,但还是很迷糊。LZ的文章写得真好,对于吾等理解能力缺陷的程序员来说,就喜欢这类通俗易懂的文章,哈哈。
06月25日 10:30
窗帘:好文章,难得的好。
06月25日 10:35
柳丝刀:看起来不错~~
06月25日 15:23
06月25日 16:43
大犬座VY:好文章,要顶
06月25日 18:12
唐尸三摆手:文章写的真棒!
06月25日 18:46
鸭梨劈两半:感谢感谢!看完茅塞顿悟!
06月25日 20:00
海绵体大战括约肌:非常好的文章!感谢~
06月25日 21:30
匿名用户:受教了!非常感谢楼主!
06月25日 22:29

赞助商

12321