Php常见排序算法

发表于 | 更新于: | 分类于
字数统计: 2.8k | 阅读时长 ≈ 11

前言：

所谓排序，就是对一组数据，按照某个顺序排列的过程，这里列出冒泡，快速，简单选择，堆，直接插入，希尔，归并排序排序方法，不要死记硬背，没用，理解就好。

内置排序函数：

  • sort() - 以升序对数组排序
  • rsort() - 以降序对数组排序
  • asort() - 根据值，以升序对关联数组进行排序
  • ksort() - 根据键，以升序对关联数组进行排序
  • arsort() - 根据值，以降序对关联数组进行排序
  • krsort() - 根据键，以降序对关联数组进行排序

冒泡排序（Bubble sort）：

基本思想：将一组数据看作一排竖着的气泡，然后让最后一个数与倒数第二个数进行比较，大的就往前移。然后用相同的方法，将倒数第二个数与倒数第三个进行比较，大的往前移，依次类推，最后本轮循环结束后，第一个元素就是最大的了，然后继续循环，得到第二个，第三个……

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
/**
 * 冒泡排序
 */
function bubble_sort($array){
    //计算数组长度
    $len=count($array);
    // 判断是否需要运行，因下面已拿出一个中间值，这里<=1
    if ($len <= 1) {
        return $array;
    }
    //第一层循环，把$i看为$array的键名，因为键名是从0开始的，所以我们需要$len-1
    for($i=0;$i<$len-1;$i++){
        //第二层循环，把$j看为$array的键名，因为键名是从0开始的，所以我们需要$len-1
        for($j=0;$j<$len-1;$j++){
            //$k是$array数组中键名为$j后的一个键名，也就是相邻的两个键名
            $k=$j+1;
            //比较两数，如果前一个数比后一个大，则交换两个数的顺序，如果不大于，就进行下一轮比较
            if($array[$j]>$array[$k]){
                //交换开始
                $t=$array[$j]; //把$array中键名为$j的值临时存到一个变量里面
                $array[$j]=$array[$k]; //此刻$array中键名为$j的值就要变更为比他小的$k的值
                $array[$k]=$t;	//再把刚刚保存的$j的值存到数组$k的位置
                //交换结束，进行下一轮比较
            }
        }
    }
    return ($array);
}
$array=array(5,45,22,11,32,28,35,56,17,21,92);
print_r(bubble_sort($array));

快速排序（Quick sort）：

基本思想：假设当前需要从小到大进行排序，快速排序的核心思路是，从当前数组中，找到一个元素作为基准比较值（key），分别从两个方向进行比较。从后往前找，比key小元素放在数组前面。然后从前往后找，比key大的元素放在数组后面。最终两个方向交汇到中间，让key交换到数组的中间位置。

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
35
/**
 * 快速排序
 */
function quick_sort($array)
{
    //计算数组长度
    $len=count($array);
    // 判断是否需要运行，因下面已拿出一个中间值，这里<=1
    if ($len <= 1) {
        return $array;
    }
    // 把数组中第一个值作为中间值
    $middle = $array[0];
    // 定义接收小于中间值数组变量
    $left = array();
    // 定义接收大于中间值数组变量
    $right = array();
    // 循环比较，因为数组中的第一个值是中间值，所以从第二个值开始循环
    for ($i=1; $i < $len; $i++) {
        if ($middle < $array[$i]) {
            // 大于中间值
            $right[] = $array[$i];
        } else {
            // 小于或等于中间值
            $left[] = $array[$i];
        }
    }
    // 递归排序划分好的2边
    $left = quick_sort($left);
    $right = quick_sort($right);
    // 合并排序后的数据，别忘了合并中间值
    return array_merge($left, array($middle), $right);
}
$array=array(5,45,22,11,32,28,35,56,17,21,92);
print_r(quick_sort($array));

PHP简单选择排序（Simple Selection Sort）：

基本思想：通过 n - i 次关键字间的比较，从 n - i + 1 个记录中选出关键字最小的记录，并和第 i （1 <= i <= n） 个记录交换，执行n-1趟 后就完成了记录序列的排序。

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
/**
 * 简单选择排序
 */
function SelectSort($array){
    //计算数组长度
    $len=count($array);
    // 判断是否需要运行，因下面已拿出一个中间值，这里<=1
    if ($len <= 1) {
        return $array;
    }
    //第一层循环，把$i看为$array的键名，因为键名是从0开始的，所以我们需要$len-1
    for($i = 0;$i < $len - 1;$i ++){
        //记录第$i个元素后的所有元素最小值下标
        $min = $i;
        //第二层循环
        for($j = $i + 1;$j < $len;$j ++){
            if($array[$j] < $array[$min]){
                $min = $j;
            }
        }
        if($min != $i){
            //交换开始
            $temp = $array[$min];
            $array[$min] = $array[$i];
            $array[$i] = $temp;
            //交换结束，进行下一轮比较
        }
    }
    return $array;
}
$array=array(5,45,22,11,32,28,35,56,17,21,92);
print_r(SelectSort($array));

堆排序（Heap Sort）：

基本思想：堆排序就对简单选择排序的改进，将待排序的序列构造成一个大根堆。此时，整个序列的最大值就是堆顶的根节点。将它移走（其实就是将其与堆数组的末尾元素交换，此时末尾元素就是最大值），然后将剩余的 n - 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
35
36
37
38
39
40
41
42
/**
 * 堆排序
 */
function HeapSort(array &$arr){
    $count = count($arr);
    //先将数组构造成大根堆（由于是完全二叉树，所以这里用floor($count/2)-1，下标小于或等于这数的节点都是有孩子的节点)
    for($i = floor($count / 2) - 1;$i >= 0;$i --){
        HeapAdjust($arr,$i,$count);
    }
    for($i = $count - 1;$i >= 0;$i --){
        //将堆顶元素与最后一个元素交换，获取到最大元素（交换后的最后一个元素），将最大元素放到数组末尾
        $temp = $arr[0];
        $arr[0] = $arr[$i];
        $arr[$i] = $temp;
        //经过交换，将最后一个元素（最大元素）脱离大根堆，并将未经排序的新树($arr[0...$i-1])重新调整为大根堆
        HeapAdjust($arr,0,$i - 1);
    }
}
//调整 $arr[$start]的关键字，使$arr[$start]、$arr[$start+1]、、、$arr[$end]成为一个大根堆（根节点最大的完全二叉树）
//注意这里节点 s 的左右孩子是 2*s + 1 和 2*s+2 （数组开始下标为 0 时）
function HeapAdjust(array &$arr,$start,$end){
    $temp = $arr[$start];
    //沿关键字较大的孩子节点向下筛选
    //左右孩子计算（我这里数组开始下标识 0）
    //左孩子2 * $start + 1，右孩子2 * $start + 2
    for($j = 2 * $start + 1;$j <= $end;$j = 2 * $j + 1){
        if($j != $end && $arr[$j] < $arr[$j + 1]){
            $j ++; //转化为右孩子
        }
        if($temp >= $arr[$j]){
            break;  //已经满足大根堆
        }
        //将根节点设置为子节点的较大值
        $arr[$start] = $arr[$j];
        //继续往下
        $start = $j;
    }
    $arr[$start] = $temp;
}
$arr = array(9,1,5,8,3,7,4,6,2);
HeapSort($arr);
var_dump($arr);

直接插入排序(Straight Insertion Sort)：

基本思想：直接插入排序的基本思想是 ： 每次从无序表中取出第一个元素，把它插入到有序表的合适位置，使有序表仍然有序。第一趟比较前两个数，然后把第二个数按大小插入到有序表中； 第二趟把第三个数据与前两个数从后向前扫描，把第三个数按大小插入到有序表中；依次进行下去，进行了(n-1)趟扫描以后就完成了整个排序过程。直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。插入排序的基本方法是：每步将一个待排序的记录按其关键字的大小插到前面已经排序的序列中的适当位置，直到全部记录插入完毕为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * 直接插入排序
 */
function InsertSort(array &$arr){
    $count = count($arr);
    //数组中第一个元素作为一个已经存在的有序表
    for($i = 1;$i < $count;$i ++){
        $temp = $arr[$i];   //设置哨兵
        for($j = $i - 1;$j >= 0 && $arr[$j] > $temp;$j --){
            $arr[$j + 1] = $arr[$j];    //记录后移
        }
        $arr[$j + 1] = $temp;   //插入到正确的位置
    }
}
$arr = array(49,38,65,97,76,13,27,49,55,04);
InsertSort($arr);
var_dump($arr);

希尔排序（Shell Sort）：

基本思想：希尔排序是指记录按下标的一定增量分组，对每一组使用 直接插入排序 ，随着增量逐渐减少，每组包含的关键字越来越多，当增量减少至 1 时，整个序列恰好被分成一组，算法便终止。

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
/**
 * 希尔排序
 */
function ShellSort(array &$arr)
{
    $count = count($arr);
    $inc = $count;    //增量
    do {
        //计算增量
        //$inc = floor($inc / 3) + 1;
        $inc = ceil($inc / 2);
        for ($i = $inc; $i < $count; $i++) {
            $temp = $arr[$i];    //设置哨兵
            //需将$temp插入有序增量子表
            for ($j = $i - $inc; $j >= 0 && $arr[$j + $inc] < $arr[$j]; $j -= $inc) {
                $arr[$j + $inc] = $arr[$j]; //记录后移
            }
            //插入
            $arr[$j + $inc] = $temp;
        }
        //增量为1时停止循环
    } while ($inc > 1);
}
$arr = array(49,38,65,97,76,13,27,49,55,04);
ShellSort($arr);
var_dump($arr);

归并排序（Merging Sort）：

基本思想：归并排序：就是利用归并（合并）的思想实现的排序方法。它的原理是假设初始序列含有 n 个元素，则可以看成是 n 个有序的子序列，每个子序列的长度为 1，然后两两归并，得到 ⌈ n / 2⌉ （⌈ x ⌉ 表示不小于 x 的最小整数）个长度为 2 或 1 的有序序列；再两两归并，······，如此重复，直至得到一个长度为 n 的有序序列为止，这种排序方法就成为 2 路归并排序。

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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
/**
 * 归并排序
 */
//归并算法总函数
function MergeSort(array &$arr){
    $start = 0;
    $end = count($arr) - 1;
    MSort($arr,$start,$end);
}
function MSort(array &$arr,$start,$end){
    //当子序列长度为1时，$start == $end，不用再分组
    if($start < $end){
        $mid = floor(($start + $end) / 2);	//将 $arr 平分为 $arr[$start - $mid] 和 $arr[$mid+1 - $end]
        MSort($arr,$start,$mid);			//将 $arr[$start - $mid] 归并为有序的$arr[$start - $mid]
        MSort($arr,$mid + 1,$end);			//将 $arr[$mid+1 - $end] 归并为有序的 $arr[$mid+1 - $end]
        Merge($arr,$start,$mid,$end);       //将$arr[$start - $mid]部分和$arr[$mid+1 - $end]部分合并起来成为有序的$arr[$start - $end]
    }
}
//归并操作
function Merge(array &$arr,$start,$mid,$end){
    $i = $start;
    $j=$mid + 1;
    $k = $start;
    $temparr = array();

    while($i!=$mid+1 && $j!=$end+1)
    {
        if($arr[$i] >= $arr[$j]){
            $temparr[$k++] = $arr[$j++];
        }
        else{
            $temparr[$k++] = $arr[$i++];
        }
    }

    //将第一个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($i != $mid+1){
        $temparr[$k++] = $arr[$i++];
    }
    //将第二个子序列的剩余部分添加到已经排好序的 $temparr 数组中
    while($j != $end+1){
        $temparr[$k++] = $arr[$j++];
    }
    for($i=$start; $i<=$end; $i++){
        $arr[$i] = $temparr[$i];
    }
}
$arr = array(9,1,5,8,3,7,4,6,2);
MergeSort($arr);
var_dump($arr);