冒泡排序
- 时间复杂度:O(N^2)
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16function bubbleSort($arr){
$n = count($arr);
for ($i=0; $i<$n-1; $i++){
for ($j=$i+1; $j<$n; $j++){
if ($arr[$j] < $arr[$i]){
[$arr[$i], $arr[$j]] = [$arr[$j], $arr[$i]];
}
}
}
return $arr;
}
$arr = [45,2,5,54,3,23];
print_r(bubbleSort($arr));
// Array ( [0] => 2 [1] => 3 [2] => 5 [3] => 23 [4] => 45 [5] => 54 )
快速排序
1 | function quickSort($arr){ |
选择排序
- 时间复杂度:O(N^2)
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20function selectSort($arr){
$n = count($arr);
for ($i=0; $i<$n-1; $i++){
$k = $i;
for ($j=$i+1; $j<$n; $j++){
if ($arr[$k] > $arr[$j]){
$k = $j;
}
}
if ($k != $i){
[$arr[$k],$arr[$i]] = [$arr[$i],$arr[$k]];
}
}
return $arr;
}
$arr = [1,45,2,5,54,3,23];
print_r(selectSort($arr));
// Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 5 [4] => 23 [5] => 45 [6] => 54 )
插入排序
- 流程
将一个待排序的无序的数组看作是两个列表,一个有序的列表,一个无序的列表,从无序的列表每次拿出一个待插入的元素,插入到有序的列表中,直到无序列表为空,排序完毕. - 实例
- 有一个无序的一维数组是这次需要排序的数组,数组是:[36,12,96,-1]
- 首先把数组的第一个元素 [36] 看作是一个独立的有序的列表,把剩下的元素 [12, 96, -1] 看作是一个无序的列表
- 第一个待插入的元素就是 12,要把 12 插入到有序的列表中,首先需要 12 和 36 比较,如果带插入的元素 12 小于 36, 就需要把 12 插入到 36前面,也就是 36 要后移一位。
- 插入排序实际是需要比较数组元素的总数减一轮,因为第一个元素不需要比较。
- 时间复杂度:O(N^2)
- 代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22function insertSort($arr){
if (!is_array($arr)) return null;
$count = count($arr);
if ($count <= 1){
return $arr;
}
for ($i=1; $i<$count; $i++){
$insertValue = $arr[$i];
$insertIndex = $i-1;
while($insertIndex >= 0 && $insertValue < $arr[$insertIndex]){
$arr[$insertIndex+1] = $arr[$insertIndex];
$insertIndex--;
}
$arr[$insertIndex+1] = $insertValue;
}
return $arr;
}
$arr = [1,45,2,5,54,3,23];
print_r(insertSort($arr));
// Array ( [0] => 1 [1] => 2 [2] => 3 [3] => 5 [4] => 23 [5] => 45 [6] => 54 )归并排序
二分查找法
- 概念
二分查找也称折半查找(Binary Search),它是一种效率较高的查找方法。但是,折半查找要求线性表必须采用顺序存储结构,而且表中元素按关键字有序排列。
首先,假设表中元素是按升序排列,将表中间位置记录的关键字与查找关键字比较,如果两者相等,则查找成功;否则利用中间位置记录将表分成前、后两个子表,如果中间位置记录的关键字大于查找关键字,则进一步查找前一子表,否则进一步查找后一子表。重复以上过程,直到找到满足条件的记录,使查找成功,或直到子表不存在为止,此时查找不成功。 - 代码实例
- 循环二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21function binarySearch($array,$findVal){
if (!is_array($array) || empty($array)) return -1;
$start = 0;
$end = count($array) - 1;
while ($start <= $end){
$middle = intval(($start+$end)/2);
if ($array[$middle] > $findVal){
$end = $middle - 1;
}elseif ($array[$middle] < $findVal){
$start = $middle + 1;
}else{
return $middle;
}
}
return -1;
}
$array = [3,54,67,124,542,642,843];
echo binarySearch($array, 542); // 4 - 递归二分查找
1
2
3
4
5
6
7
8
9
10
11
12
13
14function binarySearch($array,$findVal,$start,$end){
$middle = intval(($start+$end)/2);
if($start>$end) return -1;
if ($array[$middle] > $findVal){
return binarySearch($array,$findVal,$start,$middle-1);
}elseif ($array[$middle] < $findVal){
return binarySearch($array,$findVal,$middle+1,$end);
}else{
return $middle;
}
}
$array = [3,54,67,124,542,642,843];
echo binarySearch($array, 542,0,count($array)-1); // 4
- 循环二分查找