Tools

算法（三）冒泡排序、插入排序、选择排序、归并排序、快速排序

阅读：772 发布：2018-11-17 作者：lypeng

## 原理图
冒泡排序
![](/uploads/lypeng/2018111701.jpg)

插入排序
![](/uploads/lypeng/2018111702.jpg)

选择排序
![](/uploads/lypeng/2018111703.jpg)

## 上代码
```php
<?php
// 初始化数据
$list = array(1,3,58,34,22,99,6);
$count = count($list);

// 冒泡排序
function bubble_sort($list,$count){
    for ($i=0; $i < $count-1; $i++) { 
        for ($j=0; $j < $count-1-$i; $j++) { 
            if($list[$j]>$list[$j+1]){
                $kong = $list[$j+1];
                $list[$j+1]=$list[$j];
                $list[$j]=$kong;
            }
        }
    }
    return $list;
}
// $list = bubble_sort($list,$count);
// var_dump($list);

// 有序队列插入排序
function insert_sort($list,$val,$count){
    // 先冒个泡，变为有序队列
    $list = bubble_sort($list,$count);
    for ($i=0; $i < $count; $i++) { 
        if($val<$list[$i]){
            // 大于$val的值全部往后移一位
            for($j=$count;$j>$i;$j--){
                $list[$j]=$list[$j-1];
            }
            $list[$i]=$val; // 把插入的值赋给要插入的位置
            break;
        }
    }
    return $list;
}
// $res = insert_sort($list,8,$count);
// var_dump($res);

// 无序队列插入排序（真正的插入排序）
// 从第二个元素开始，与左边的元素比较然后插入
// 5 3 1 8 7  //初始数据
// 3 5 1 8 7  //3<5,5向后移，3往前移
// 1 3 5 8 7  //1<3,把1插入到最前面
// 1 3 5 8 7  //8>5 保持不动
// 1 3 5 7 8  //7>5 7<8,把7插入到7与8中间
// 文字描述好理解，代码我调试半天，最后还是看了答案，表示大脑不够用啊~
function insert_sort2($list,$count){
    for ($i=1; $i < $count; $i++) {
        $val = $list[$i];
        $j = $i - 1;
        for(;$j>=0;$j--){
            if($list[$j]>$val){
                $list[$j+1]=$list[$j];
            } else {
                break;
            }
        }
        $list[$j+1]=$val; // 把插入的值赋给要插入的位置
    }
    return $list;
}
// var_dump(insert_sort2($list,$count));

// 选择排序
// count=7
//               0 1 2  3  4  5  6
// $list = array(1,3,58,34,22,99,6);  //初始数据
// 选择排序算法的实现思路有点类似插入排序，也分已排序区间和未排序区间。
// 但是选择排序每次会从未排序区间中找到最小的元素，将其放到已排序区间的末尾。
function select_sort($list,$count){
    for ($k=0; $k < $count; $k++) {
        // 从后往前找最小值
        $i = $count-1; //这句必须放到外面，保证每次都是从最后一个元素开始往前找最小值
        for (; $i > 0; $i--) {
            if($list[$i]<$list[$i-1]){
                $val = $list[$i];
                break; //找到最小值，跳出
            }
        }
        // 从前往后对调位置插入
        for ($j=0; $j < $i; $j++) {
            if($val<$list[$j]){
                $list[$i] = $list[$j];
                $list[$j] = $val;
                break; //对调位置插入后，跳出循环，继续开始找最小值
            }
        }
        // if($k == 2){ //测试用
        //     break;
        // }
    }
    return $list;
}
// var_dump(select_sort($list,$count));

/*
 * 选择排序2(两个for，最小值从前往后找)
 * swap函数在数组$arr之前加了&, 代表其地址,这样可以省去return来返回值,代码更加简洁
 * 原理见:http://blog.csdn.net/baidu_30000217/article/details/53071856
 * 作者：martinhacker
 * 原文：https://blog.csdn.net/martinhacker/article/details/61616141
 */
function swap(array &$arr, $a, $b){
    $temp = $arr[$a];
    $arr[$a] = $arr[$b];
    $arr[$b] = $temp;
}
function selectSort(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 != $j){
            swap($arr, $min, $i);
        }
    }
}
// $arr = array(9, 1, 5, 8, 3, 7, 4, 6, 2);
// selectSort($arr);
// print_r($arr);

// 效率测试
// 对10000个数进行排序
for ($i=0; $i < 10000; $i++) { 
    $list[] = $i+1; //1-10000数组
}
shuffle($list); //打乱顺序
// var_dump($list);
// exit();

$t1 = time();
select_sort($list,10000); //1
$t2 = time();
selectSort($list,10000); //4
// insert_sort2($list,100000); //3
$t3 = time();
// bubble_sort($list,100000); //8

// echo time() - $t3;
// echo "\r\n";
echo $t3 - $t2;
echo "\r\n";
echo $t2 - $t1;

?>
```
## 效率总结（快-慢）

选择排序 > 插入排序 > 冒泡排序

我的三个for循环 > 操作地址的两个for，哈哈哈~
1万数据还好，要是有10万数据，电脑直接不动了，等待很久才出结果，冒泡排序花费快20分钟（1068秒），而选择排序只需2分钟（111秒）~

附效率测试图

![](/uploads/lypeng/20181117002140.jpg)

![](/uploads/lypeng/2018112102.jpg)

![](/uploads/lypeng/2018112101.jpg)

## 上代码

```php
<?php
// 归并排序
// 一半一半的分下去，最后比较两个元素的大小，在合并
// array_chunk(array,size,preserve_key); 函数把数组分割为新的数组块。
// 其中每个数组的单元数目由 size 参数决定。
// 最后一个数组的单元数目可能会少几个。
// 可选参数 preserve_key 是一个布尔值，它指定新数组的元素是否有和原数组相同的键（用于关联数组），还是从 0 开始的新数字键（用于索引数组）。默认是分配新的键。
// from: https://www.jb51.net/article/132134.htm
function merge_sort($arr){
    $length=count($arr);
    if($length<=1){
        return $arr;
    }
    //分解数组，递归排序
    $half=ceil($length/2);
    $arr2=array_chunk($arr,$half);
    $left=merge_sort($arr2[0]);
    $right=merge_sort($arr2[1]);
    while(count($left)&&count($right)){
        if($left[0]<$right[0]){
            $reg[]=array_shift($left);
        }else{
            $reg[]=array_shift($right);
        }
    }
    return array_merge($reg,$left,$right);
}

// 快速排序
// 从队尾取出一个元素，剩下的跟它比较，大于的放右边，小于的放左边，不断进行此操作，最后合并
function quick_sort($arr){
    $length=count($arr);
    if($length<=1){
        return $arr;
    }
    $end = array_pop($arr);
    $left = $right = array();
    foreach ($arr as $k => $v) {
        if($v <= $end){
            $left[]=$v;
        }else{
            $right[]=$v;
        }
    }
    $l = quick_sort($left);
    $r = quick_sort($right);
    return array_merge($l,array($end),$r);
}
$arr = array(5,6,8,9,12,35,4);
var_dump(quick_sort($arr));

?>
```

------本文结束感谢阅读------

上一篇：算法（二）复杂度分析

下一篇：算法（四）归并排序、快速排序