首页 » 后端 » 正文

冒泡排序、快速排、插入排序、选择排序、归并排序

| 后端 | | 暂无评论 | 2351 views

这两个算法是php中常用的 冒泡排序 两两比较待排序数据元素的大小，发现两个数据元素的次序相反时即进行交换，直到没有反序的数据元素为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function maopao($arr){
    $count = count($arr);
    if($count == 1){
        return $arr;
    }else if($count > 1){
        for($i=0; $i<$count; $i++){
            for($j=$count-1; $j<$i; $j--){
                if($arr[$j]<$arr[$j-1]){
                    $temp = $arr[$j];
                    $arr[$j] = $arr[$j-1];
                    $arr[$j-1] = $temp;
                }
            }
        }
        return $arr;
    }else{
        return false;
    }
}
$array = array(43,54,23,67,7,8,3);
var_dump(maopao($array));

快速排序 通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

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
function quikSort($arr){
    $count = count($arr);
    if($count<=1){
        return $arr;
    }elseif($count>1){
        $key = $arr[0];
        $left_arr = array();
        $right_arr = array();
 
        for($i=1; $i<$count; $i++){
            if($arr[$i]<=$key){
                $left_arr[] = $arr[$i];
            }else{
                $right_arr[] = $arr[$i];
            }
        }
        $left_arr = quikSort($left_arr);
        $right_arr = quikSort($right_arr);
        return array_merge($left_arr, array($key), $right_arr);
    }else{
        return false;
    }
}
 
$array = array(43,54,23,67,7,8,3);
 
var_dump(quikSort($array));

 插入排序 每次将一个待排序的数据元素插入到前面已经排好序的数列中，使数列依然有序，知道待排序数据元素全部插入完为止。

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 insertion_sort($arr) {
    $length = count($arr);
    //先默认第一个下标为0的数是排好的数
    for($i=1;$i<$length;$i++){
        //确定插入比较的数
        $insertVal=$arr[$i];
        //确定与前面比较的数比较
        $insertIndex=$i-1;
 
        //表示没有找到位置
        while($insertIndex>=0 && $insertVal<$arr[$insertIndex]){
 
            //把数后移
            $arr[$insertIndex+1]=$arr[$insertIndex];
            $insertIndex--;
        }
 
        //插入(给$insertval找到位置了)
        $arr[$insertIndex+1] = $insertVal;
    }
    return $arr;
}
// 初始化数组
$array = array(1, -1, 3, 3, 2, 9, -10, 7, 6, 5);
// 调用函数
var_dump(insertion_sort($array));

选择排序 每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function select_sort($arr){
    $count = count($arr);
    for($i=0; $i<$count; $i++){
        $k = $i; //循环指向
        for($j=$i+1; $j<$count; $j++){
            if ($arr[$k] > $arr[$j])
                $k = $j; //前者大于后者，调整查询指向
            if ($k != $i){ //如果指向更改了，就把循环指向的value跟循环指向的value（保证是最小值）
                $tmp = $arr[$i];
                $arr[$i] = $arr[$k];
                $arr[$k] = $tmp;
            }
            $k=$i; //重置循环指向
        }
    }
    return $arr;
}

 归并排序 归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个有序的子序列，再把有序的子序列合并为整体有序序列。

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
/**
* mergeSort 归并排序
* 是开始递归函数的一个驱动函数
* @param &$arr array 待排序的数组
*/
function mergeSort(&$arr) {
    $len = count($arr);//求得数组长度
 
    mSort($arr, 0, $len-1);
}
/**
* 实际实现归并排序的程序
* @param &$arr array 需要排序的数组
* @param $left int 子序列的左下标值
* @param $right int 子序列的右下标值
*/
function mSort(&$arr, $left, $right) {
 
    if($left &lt; $right) {
        //说明子序列内存在多余1个的元素，那么需要拆分，分别排序，合并
        //计算拆分的位置，长度/2 去整
        $center = floor(($left+$right) / 2);
        //递归调用对左边进行再次排序：
        mSort($arr, $left, $center);
        //递归调用对右边进行再次排序
        mSort($arr, $center+1, $right);
        //合并排序结果
        mergeArray($arr, $left, $center, $right);
    }
}
 
/**
* 将两个有序数组合并成一个有序数组
* @param &$arr, 待排序的所有元素
* @param $left, 排序子数组A的开始下标
* @param $center, 排序子数组A与排序子数组B的中间下标，也就是数组A的结束下标
* @param $right, 排序子数组B的结束下标（开始为$center+1)
*/
function mergeArray(&$arr, $left, $center, $right) {
    //设置两个起始位置标记
    $a_i = $left;
    $b_i = $center+1;
    while($a_i&lt;=$center && $b_i&lt;=$right) {
        //当数组A和数组B都没有越界时
        if($arr[$a_i] &lt; $arr[$b_i]) {
            $temp[] = $arr[$a_i++];
        } else {
            $temp[] = $arr[$b_i++];
        }
    }
    //判断 数组A内的元素是否都用完了，没有的话将其全部插入到C数组内：
    while($a_i <= $center) {
        $temp[] = $arr[$a_i++];
    }
    //判断 数组B内的元素是否都用完了，没有的话将其全部插入到C数组内：
    while($b_i <= $right) {
        $temp[] = $arr[$b_i++];
    }
//将$arrC内排序好的部分，写入到$arr内：
    for($i=0, $len=count($temp); $i<$len; $i++) {
        $arr[$left+$i] = $temp[$i];
    }
 
}
 
//do some test:
$arr = array(4, 7, 6, 3, 9, 5, 8);
mergeSort($arr);
print_r($arr);

来源： http://blog.csdn.net/ppiao1970hank/article/details/6449479

http://blog.phpha.com/archives/1683.html

发表评论