算法

求1到10000之间所有的质数

/** * @desc 求1到10000之间的所有质数 * 质数：只能被1和它本身整除的数。 2 3 5 7 11 13 17 .... * 技巧：如果不能被比自己小的质数整除，那这个数一定是质数 */ public function prime() { $_arr = []; for ($i = 2; $i < 10000; $i++) { // 是否质数 $isPrime = true; $sqrt = sqrt($i); foreach ($_arr as $n) { // 如果能被比自己小的质数整除则说明非质数 if ($i % $n == 0) { $isPrime = false; break; } // 判断数值是否质数仅判断到平方根即可 if ($n > $sqrt) { break; } } if ($isPrime) { $_arr[] = $i; } } return $_arr; }

冒泡排序

从左向右依次排序。通过依次比对临近2个值的大小。确认是否调换位置。可以找出最大/最小的值。然后再继续查找第二大/小的值。直到排序完毕，每一次比对次数比上一次少一次。

/** * @desc 冒泡排序:从左向右依次排序。通过依次比对临近2个值的大小。确认是否调换位置。可以找出最大/最小的值。然后再继续查找第二大/小的值。直到排序完毕，每一次比对次数比上一次少一次。 * @param $arr * @return mixed */ public function bubblingSort($arr) { for($i=0; $i < count($arr); $i++) { for ($j=0; $j < count($arr) - 1 - $i; $j++) { // 从小到大排序 > 从大到小排序 < if ($arr[$j] > $arr[$j + 1]) { $tmp = $arr[$j]; $arr[$j] = $arr[$j + 1]; $arr[$j + 1] = $tmp; } } } return $arr; }

快速排序

使用递归，以其中一个元素为基准。循环其它元素与基准元素比对。并按照大于基准元素/小于基准元素分为2个数组。再递归拆分直到所有元素都排序完。最后合并左侧和右侧数据

/** * @desc 快速排序法 * @param $arr */ public function quickSort($arr) { // 剩余最后1个结束排序 if (count($arr) <= 1) { return $arr; } // 取中间值 $middle = $arr[0]; // 左侧数组 $left_arr = []; // 右侧数组 $right_arr = []; for ($i = 1; $i < count($arr); $i++) { // 从大到小排序 < 从小到大排序 > if ($middle < $arr[$i]) { $left_arr[] = $arr[$i]; } else { $right_arr[] = $arr[$i]; } } // 递归排序左右2侧的数组 $left_arr = $this->quickSort($left_arr); $right_arr = $this->quickSort($right_arr); // 合并数组 左侧 中间值 右侧 return array_merge($left_arr, [$middle], $right_arr); }