冒泡排序

原理

对一组数据，比较相邻数据的大小，向值较小的数据放在前面，值大的放在后面。（升序排列）

对于一个长度为N的数组，我们需要排序 N-1 轮，每 i 轮 要比较 N-i 次。对此我们可以用双重循环语句，外层循环控制循环轮次，内层循环控制每轮的比较次数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
　function order($arr){
   　　$count = count($arr);
   　　$temp = 0; 
  　　 //外层控制排序轮次
   　　for($i=0; $i<$count-1; $i++){
       　　//内层控制每轮比较次数
       　　for($j=0; $j< $count-1-$i; $j++){
             　　if($arr[$j] > $arr[$j+1]){
                 　　$temp        = $arr[$j];
                 　　$arr[$j]     = $arr[$j+1];
                 　　$arr[$j+1]   = $temp;
            　　}
      　　 }
   　　} 
　　    return $arr;
    }     


$arr= array(6,3,8,2,9,1);
$res =  order($arr);
var_dump($res);

选择排序

原理

在一组数据中，选出最小的一个数与第一个位置交换；然后在剩下的数据中找出最小的数与第二个位置交换，循环到倒数第二个数与最后一个数比较为止

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
function selectSort($arr) {
	//双重循环完成，外层控制轮数，内层控制比较次数
	$len=count($arr);
    for($i=0; $i<$len-1; $i++) {
        //先假设最小的值的位置
        $p = $i;
        for($j=$i+1; $j<$len; $j++) {
            //$arr[$p] 是当前已知的最小值
            if($arr[$p] > $arr[$j]) {
            //比较，发现更小的,记录下最小值的位置；并且在下次比较时采用已知的最小值进行比较。
                $p = $j;
            }
        }
        //已经确定了当前的最小值的位置，保存到$p中。如果发现最小值的位置与当前假设的位置$i不同，则位置互换即可。
        if($p != $i) {
            $tmp = $arr[$p];
            $arr[$p] = $arr[$i];
            $arr[$i] = $tmp;
        }
    }
    //返回最终结果
    return $arr;
}

插入排序

原理

在一组数据中，假设前面的数是已经排好顺序的，现在要把第n个数插入到前面的有序数据中，使得这第n个数也是排好顺序的。将这个数据和前面最后一个数据比较，如果小于最后一个数据则交换位置，如此反复循环，知道全部排好顺序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
function insert_sort($arr) {
    //获取数组单元个数
    $count = count($arr);
    //外层循环用于从未排序区域中取出待排序元素
    for ($i=1; $i < $count; $i++) {
        //获取当前需要插入已排序区域的元素值
        $temp = $arr[$i];
        //内层循环用于从已排序区域寻找待排序元素的插入位置
        for ($j=$i-1; $j >= 0; $j--) {
            //如果$arr[$i]比已排序区域的$arr[$j]小，就后移$arr[$j]
            if ($temp < $arr[$j]) {        
                $arr[$j+1] = $arr[$j];   
                $arr[$j] = $temp;
            } else {
                //如果$arr[$i]不小于$arr[$j]，则对已排序区无需再排序
                break;
            }
        }
    }
    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
function quickSort($arr) {
    //先判断是否需要继续进行
    $length = count($arr);
    if($length <= 1) {
        return $arr;
    }
    //选择第一个元素作为基准
    $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);
}

顺序查找

原理

从数组的第一个元素开始一个一个向下查找，如果有和目标一致的元素，查找成功；如果到最后一个元素仍没有目标元素，则查找失败。

1
2
3
4
5
6
7
8
9
function search($arr,$k){
　　　　 $n = count($arr);
    for($i=0; $i<$n; $i++){
        if($arr[$i]==$k){
        	return $i;
        }
    }
    return -1;
}

二分查找法

前提条件

  1. 必须采用顺序存储结构。
  2. 必须按关键字大小有序排列。

原理

先取数组中间的值floor((low+top)/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
51
52
53
54
55
56
57
58
59
// 非递归
/**
 * 二分查找算法
 * @param array $arr 待查找区间
 * @param int $number 查找数
 * @return int        返回找到的键
 */
function binary_search($arr, $number) {
    // 非数组或者数组为空，直接返回-1
    if (!is_array($arr) || empty($arr)) {
        return -1;
    }
    // 初始变量值
    $len = count($arr);
    $lower = 0;
    $high = $len - 1;
    // 最低点比最高点大就退出
    while ($lower <= $high) {
        // 以中间点作为参照点比较
        $middle = intval(($lower + $high) / 2);
        if ($arr[$middle] > $number) {
            // 查找数比参照点小，舍去右边
            $high = $middle - 1;
        } else if ($arr[$middle] < $number) {
            // 查找数比参照点大，舍去左边
            $lower = $middle + 1;
        } else {
            // 查找数与参照点相等，则找到返回
            return $middle;
        }
    }
    // 未找到，返回-1
    return -1;
}
// 递归
/**
 * @param array $arr 待查找区间
 * @param int $number 查找数
 * @param int $lower 区间最低点
 * @param int $high 区间最高点
 * @return int
 */
function binary_search_recursion(&$arr, $number, $lower, $high) {
    // 以区间的中间点作为参照点比较
    $middle = intval(($lower + $high) / 2);
    // 最低点比最高点大就退出
    if ($lower > $high) {
        return -1;
    }
    if ($number > $arr[$middle]) {
        // 查找数比参照点大，舍去左边继续查找
        return binary_search_recursion($arr, $number, $middle + 1, $high);
    } elseif ($number < $arr[$middle]) {
        // 查找数比参照点小，舍去右边继续查找
        return binary_search_recursion($arr, $number, $lower, $middle - 1);
    } else {
        return $middle;
    }
}

遍历文件夹下的所有文件和子文件夹

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function my_scandir($dir){
    $files = array();
    if($handle = opendir($dir)) {
        while (($file = readdir($handle))!== false) {
            if($file != '..' && $file != '.') {
                if(is_dir($dir."/".$file)){
                    $files[$file]=my_scandir($dir."/".$file);
                }else{
                    $files[] = $file;
                }
            }
        }

        closedir($handle);
        return $files;
    }
}