黑马程序员技术交流社区

标题: 【济南中心】PHP课程同步笔记day14：算法 [打印本页]
作者: 小鲁哥哥    时间: 2017-5-22 21:17
标题: 【济南中心】PHP课程同步笔记day14：算法
本帖最后由 小鲁哥哥 于 2017-5-22 21:21 编辑

【济南中心】PHP课程同步笔记day14：算法
冒泡排序算法
冒泡排序思想
       $arr = array(9,8,7,6,5)  --> array(5,6,7,8,9)
       每一趟只找一个最大值，并把最大值移到最右边。
       如果将最大值移动最右边，只需要将两个数组元素，两两交换。
       交换的原则：左边数大于右边数时，才进行交换。如果左边数小于右边数，则不用交换。
       冒泡排序是稳定的一种排序方法。
冒泡排序工作原理
原始数组
9
8
7
6
5
第0趟
8
7
6
5
9
第1趟
7
6
5
8
9
第2趟
6
5
7
8
9
第3趟
5
6
7
8
9
冒泡排序注意事项
       数组的总个数：$n
       当前趟数(第几趟)：$i
       共需要跑多少趟(总趟数)：$n-1
       每一趟要比较多少次？$j = $n-1-$i
       改数组必须是枚举数组，且下标必须是0开始的正整数，下标必须是连续的。

实例：数组冒泡排序
[PHP] 纯文本查看 复制代码
Function bubbleSort($arr){

//数组总个数(总长度)

$n = count($arr);

//循环趟数($i)

For($i = 0;$i<$n-1;$i++){

//循环比较($j)

For($j=0;$j<$n-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(9,8,7,1,5,11);

Var_dump(bubbleSort($arr));

选择排序
选择排序思路：
       每一趟在n-i+1(i=1,2,...,n-1)个记录中选择关键字最小的记录作为有序序列中的第i个记录，其中最简单的是简单选择排序，其过程如下：通过n-i次关键字间的比较，从n-i+1个记录中选择出关键字最小的记录，并和第i个记录交换。
选择排序工作原理：
       每一次从待排序的数据元素中选出最小(或最大)的一个元素，存放在序列的起始位置，直到全部待排序的数据元素拍完。选择排序是不稳定的排序方法。
案例：选择排序法
[PHP] 纯文本查看 复制代码
Function select_sort($arr){

//实现思路双重循环完成，外层控制轮数，当前的最小值。内层控制的比较次数

//$i当前最小值的位置，需要参与比较的元素

For($i=0,$len=count($arr);$i<$len-1;$i++){

//先假设最小的值的位置

$p = $i;

//$j当前都需要和哪些元素比较，$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;

}

作者: comebas    时间: 2017-11-8 20:25
不错不错，能有更多的更新就好
作者: 闲乐    时间: 2018-5-31 18:24
很好很强大



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2