冒泡，选择，插入，快速

发表于

冒泡，选择，插入，快速，四种常用的排序方法

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
<!DOCTYPE html>
<html lang="zh-cn">
<head>
	<meta charset="UTF-8">
	<title>冒泡排序法</title>
</head>
<body>
<?php 
	
	
	function bubbleSort($arr){
	//利用双重循环完成
	//外层循环控制 比较的轮数，每轮会将一个最大的气泡（数）浮到水面
	//如果数组的元素个数为N 则需要N-1轮完成
		for ($i=0,$len = count($arr); $i < $len-1; $i++) { 
			//内层循环控制 的比较的次数，
			////第一轮需要比较 N-1次
			//第二轮需要比较 N-2次
			for ($j=0; $j < $len-1-$i; $j++) { 
				if ($arr[$j]>$arr[$j+1]) {
					$temp = $arr[$j];
					$arr[$j]=$arr[$j+1];
					$arr[$j+1]=$temp;
				}
			}
		}
		return $arr;
	}

	function selectSort($arr){
		//实现思路
		//双重循环完成，外层控制轮数，当前的最小值。
		//内层 控制的比较次数
		//$i 当前最小值的位置， 需要参与比较的元素
		for ($i=0,$len=count($arr); $i < $len-1; $i++) { 
			$p=$i;
			for ($j=$i+1; $j < $len; $j++) { 
				if($arr[$j]<$arr[$p]){
					$p=$j;
				}
			}
			if ($p!=$i) {
				$temp = $arr[$i];
				$arr[$i]=$arr[$p];
				$arr[$p]=$temp;
			}
			
		}
		return $arr;
	}
	function insertSort($arr){
		//利用双重循环，外层控制要进行插入判断的数
		//内层是已经排好的数与外层的数进行比较交换
		for ($i=1,$len=count($arr); $i < $len; $i++) { 
			$temp=$arr[$i];
			for ($j=$i-1; $j >= 0; $j--) { 
				if ($temp<$arr[$j]) {
					$arr[$j+1]=$arr[$j];
					$arr[$j]=$temp;
				}else{
					break;
				}
			}
		}
		return $arr;
	}
/**
*快速排序
*
* @param array $arr 需要排序的数组
*
* @return array 排序好的数组
*/
function quick_sort($arr) {
    //先判断是否需要继续进行
    $length = count($arr);
    if($length <= 1) {
        return $arr;
    }
    //如果没有返回，说明数组内的元素个数 多余1个，需要排序
    //选择一个标尺
    //选择第一个元素
    $base_num = $arr[0];
    //遍历 除了标尺外的所有元素，按照大小关系放入两个数组内
    //初始化两个数组
    $left_array = array();//小于标尺的
    $right_array = array();//大于标尺的
    for($i=1; $i<$length; $i++) {
        if($base_num > $arr[$i]) {
            //放入左边数组
            $left_array[] = $arr[$i];
        } else {
            //放入右边
            $right_array[] = $arr[$i];
        }
    }
    //再分别对 左边 和 右边的数组进行相同的排序处理方式
    //递归调用这个函数,并记录结果
    $left_array = quick_sort($left_array);
    $right_array = quick_sort($right_array);
    //合并左边 标尺 右边
    return array_merge($left_array, array($base_num), $right_array);
}

	$myarr=array(23,45,64,21,5,75);
	print_r(bubbleSort($myarr));
	echo "<br/>";
	print_r(selectSort($myarr));
	echo "<br/>";
	print_r(insertSort($myarr));
	echo "<br/>";
	print_r(quick_sort($myarr));

 ?>
</body>
</html>