PHP常用的排序和查找算法

时间:2022-02-19 15:48:32

本文汇总了常见的php排序算法和查找,在进行算法设计的时候有不错的借鉴价值。现分享给大家供参考之用。具体如下:

?
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
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
<?php
/**
 * PHP最常用的四个排序方法及二种查找方法
 * 下面的排序方法全部都通过测试
 * auther : soulence
 * date : 2015/06/20
 */
 
//PHP冒泡排序法
function bubbleSort(&$arr){
 //这是一个中间变量
 $temp=0;
 //我们要把数组,从小到大排序
 //外层循环
 $flag=false;//这个优化之后效率会很高,一般够用
 for($i=0;$i<count($arr)-1;$i++){
  
   for($j=0;$j<count($arr)-1-$i;$j++){
     //说明前面的数比后面的数大,就要交换
     if($arr[$j]>$arr[$j+1]){
        $temp=$arr[$j];
        $arr[$j]=$arr[$j+1];
        $arr[$j+1]=$temp;
        $flag=true;
     }
   }
   if(!$flag){
    //已经是有序了
    break;
   }
   $flag=false;
  }
}
 
//PHP选择排序法  效率比冒泡要高
function selectSort(&$arr){
  $temp=0;
  for($i=0;$i<count($arr)-1;$i++){
    //假设$i就是最小的数
    $minVal=$arr[$i];
    //记录我认为的最小数的下标
    $minIndex=$i;
    for($j=$i+1;$j<count($arr);$j++){
      //说明我们认为的最小值,不是最小
      if($minVal>$arr[$j]){
         $minVal=$arr[$j];
         $minIndex=$j;
      }
    }
    //最后交换
    $temp=$arr[$i];
    $arr[$i]=$arr[$minIndex];
    $arr[$minIndex]=$temp;
  }
}
 
//插入排序法(小到大排序)  效率又比 选择排序法要高一些
function insertSort(&$arr){
  //先默认下标为0的这个数已经是有序
  for($i=1;$i<count($arr);$i++){
    //$insertVal是准备插入的数
    $insertVal=$arr[$i];
    //准备先和谁下标为$inserIndex的比较
    $inserIndex=$i-1;
    //如果这个条件满足,说明我们还没有找到适当的位置
    while($inserIndex >= 0 && $insertVal < $arr[$inserIndex]){
    //同时把数后移
      $arr[$inserIndex+1] = $arr[$inserIndex];
      $inserIndex--;
    }
    //插入(这时就给$inserIndex找到适当的位置)
    $arr[$inserIndex+1] = $insertVal;
  }
}
 
  
//快速排序法 第一种写法 不是我实现的
function quickSort($left,$right,&$arr){
   $l=$left;
   $r=$right;
   $pivot= $arr[($left+$right)/2];
   while($l<$r){
     while($arr[$l]<$pivot){
      $l++;
     }
     while($arr[$r]>$pivot){
      $r--;
     }
     if($l>=$r){
      break;
     }
     
     $temp=$arr[$l];
     $arr[$l]=$arr[$r];
     $arr[$r]=$temp;
     if($arr[$l]==$pivot){
      --$r;
     }
     if($arr[$r]==$pivot){
      ++$l;
     }
   }
   if($l==$r){
    $l++;
    $r--;
   }
   if($left<$r) quickSort($left,$r,$arr);
   if($right>$l) quickSort($l,$right,$arr);
}
 
/**
 * 快速排序方法 第二种实现方法 自己实现的
 * PHP快速排序方法
 * $order asc 小到大 desc大到小 默认是asc
 * $order 的值只能为 asc desc 如果乱写一个值也是按asc排序的
 */
function quickSort2($arr,$order = 'asc')
{
 if(count($arr) <= 1)
  return $arr;
 
 $arr_left = $arr_right = array();
 
 $val = $arr[0];unset($arr[0]);
 
 foreach ($arr as $v) {
  if(strtolower($order) == 'desc'){
   if($v < $val)
    $arr_right[] = $v;
   else
    $arr_left[] = $v;
  }else{
   if($v > $val)
    $arr_right[] = $v;
   else
    $arr_left[] = $v;
  }
 }
 
 $arr_left = quickSort($arr_left,$order);
 $arr_right = quickSort($arr_right,$order);
 
 return array_merge($arr_left,array($val),$arr_right);
}
 
 
//下面是查找
$arr=array(46,90,900,0,-1);
//这是按顺序查询
function search(&$arr,$findVal){  
  $flag=false;
  for($i=0;$i<count($arr);$i++){
    if($findVal==$arr[$i]){
      echo "找到了,下标为=$i";
      $flag=true;
      //查询一次,如果多次就不要这个 break;
    }
  }
  if(!$flag){
    echo "查无此数";
  }
}
 
//调用二分查找
$arr=array(0,90,900,99990);//注意,一定要是有序的
binarySwarch($arr,90,0,count($arr)-1);
 
//二分查找函数,它有一个前提,查找的数组必须是有序的
function binarySearch(&$arr,$findVal,$leftIndex,$rightIndex){
  //如果$rightIndex < $leftIndex条件成立,说明没有这个数,则退出
  if($rightIndex < $leftIndex){
    echo "找不到该数";
    return;
  }
  //首先找到中间这个数 round是出于如果出现小数,四舍五入
  $middleIndex=round(($rightIndex+$leftIndex)/2);
  //如果大于则向后面找
  if($findVal > $arr[$middleIndex]){
    binarySearch($arr,$findVal,$middleIndex+1,$rightIndex);
    //如果小于中间数,则向前面找
  }else if($findVal < $arr[$middleIndex]){
    binarySearch($arr,$findVal,$leftIndex,$middleIndex-1);
  }else{
    echo "找到这个数。下标是$middleIndex";
  }
}
?>

希望本文所述排序算法和查找算法实例对大家的php程序设计有所帮助。