本帖最后由 小鲁哥哥 于 2017-5-22 21:21 编辑
【济南中心】PHP课程同步笔记day14:算法 冒泡排序算法 冒泡排序思想 $arr = array(9,8,7,6,5) --> array(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;
}
|