十大经典排序算法

发表于 更新于 分类于 阅读次数：

十大经典排序算法学习记录

基于PHP实现十大经典排序算法，并分析其复杂度

冒泡排序

思路1

如图每次比较相邻两个，循环到某次没有改变为止.

PHP实现代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
$arr = [9,8,6,7,2,1,5,11,12,98,12,455,145,1557,54,475,15,488,4521,4754,85,5455,45554,565,45,45,4,5];
echo implode(",",$arr).'<br>';
$status = TRUE;
// while ($status){
function bubble_sort($arr,$i,$status=0){
    $length = count($arr);
    if ($arr[$i] > $arr[$i+1]){
        $a = $arr[$i];
        $arr[$i] = $arr[$i+1];
        $arr[$i+1] = $a;
        $status = 1;
    }

    if($i < $length -2){
        return bubble_sort($arr,$i+1,$status);
    }else{
        return [$arr,$status];
    }
}
$status = 1;
$n = 1;
while ($status == 1) {
    echo 'n等于'.$n.'<br>';
    $res = bubble_sort($arr,0);
    $arr = $res[0];
    $status = $res[1];
    $n = $n + 1;
}
echo implode(",",$res[0]).'<br>';

该思路实现排序时间复杂度为$O(n^2)$

思路2

循环记录最小值，计入结果集，计入后从原序列中删除，依次递推 时间复杂度仍为$O(n^2)$ ，该思路实际时选择排序

思路3

在思路1的基础上，每次执行一次循环后，我们实际已经知道了最大值，因此第二次循环时可以减少一次循环次数 循环次数为 n!

该思路实际也是为选择排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
<?php
echo "<pre>";
$arr = [9,8,6,7,2,1,5,11,12,98,12,455,145,1557,54,475,15,488,4521,4754,85,5455,45554,565,45,45,4,5];
echo implode(",",$arr).'<br>';

// 递归执行一次排序
function bubble_sort($arr,$i=0,$status=0){
    $length = count($arr);
    if ($arr[$i] > $arr[$i+1]){
        $a = $arr[$i];
        $arr[$i] = $arr[$i+1];
        $arr[$i+1] = $a;
        $status = 1;
    }

    if($i < $length -2){
        return bubble_sort($arr,$i+1,$status);
    }else{
        return $arr;
    }
}
// 计算数组长度
$length = count($arr);
$res_arr = [];
while ($length > 1){
    $arr = bubble_sort($arr);
    $res_arr[] = $arr[$length-1];
    unset($arr[$length-1]);
    $length = $length -1;
}
$res_arr[] = $arr[0];
// 反转排序数组
$res = array_reverse($res_arr);
echo implode(",",$res).'<br>';

思路4 插入排序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 如果k等于0 遍历到第一个元素，第一个元素默认为初始有序序列
 * 如果本次遍历的值小于有序序列的最后一个元素 则将有序序列中的最后一个元素后移一位，并再次判断被移动的元素的前一位后是否需要后移 
 * 将元素插入有序序列中
 */
function insertSort2($arr)
{   
    foreach($arr as $k => $v){
        while ($k > 0  && $v < $arr[$k-1]){
            $arr[$k] = $arr[$k-1]; 
            $k--;
        }
        $arr[$k] = $v;
    }
    return $arr;
}

将序列中的第一个值看作初始的有序序列，然后第二个值到结尾的序列看作无序序列

从头到尾从无需序列中依次取值，在有序序列中从头到尾依次扫描判断需要插入的位置

这种方式在待排序序列为逆序时效率最高，

示例代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
echo "<pre>";
$arr = [9,8,6,7,2,1,5,11,12,98,12,455,145,1557,54,475,15,488,4521,4754,85,5455,45554,565,45,45,4,5];
echo implode(",",$arr).'<br>';

// 定义在有序数组中插入元素方法
function array_insert($arr,$value){
    $res = [];
    // 用于记录本次遍历是否执行了插入操作
    $insert_status = 0;
    foreach($arr as $v){
        if ($value <= $v && $insert_status == 0){
            $res[] = $value;
            $insert_status = 1;
        }
        $res[] = $v;
    }
    if ($insert_status == 0){
        $res[] = $value;
    }
    return $res;
}

//遍历数组进行选择排序
function insertSort($arr){
    $res = [];
    foreach($arr as $v){
        $res = array_insert($res,$v);
    }
    return $res;
}

echo implode(",",insertSort($arr)).'<br>';